练习

2.3-2 重写MERGE

  1. public void merge(int[] A,int p,int q,int r,int[] temp) { 
  2.     // 传入temp数组，避免在运行过程中反复创建数组temp
  3.     int len_1 = q-p+1,len_2 =r-q;
  4.     int i=0, j=0;
  5.     int t=0;
  6.     while(i<len_1 && j<len_2) {
  7.         if (A[p+i] < A[q+j+1]) {
  8.             temp[t++] = A[p+i];
  9.             i++;
  10.         }else {
  11.             temp[t++] = A[q+j+1];
  12.             j++;
  13.         }
  14.     }
  15.     while( i<len_1) {
  16.         temp[t++] = A[p+i];
  17.         i++;
  18.     }
  19.     while( j<len_2) {
  20.         temp[t++] = A[q+j+1];
  21.         j++;
  22.     }
  23. }
  25. public void merge_sort(int[] A,int p,int r,int[] temp) {
  26.     if (p<r) {
  27.         int q = (p+r)/2;
  28.         merge_sort(A,p,q);
  29.         merge_sort(A,q+1,r);
  30.         merge(A,p,q,r);
  31.     }
  32. }

2.3-3 证明归并排序的时间为nlogn
证明：
因为T(n) = 2T(n/2) + n = 2 ( 2T(n/2^2) + n/2 ) + n = 2^2 T(n / 2^2) + 2n = … =2^k T(n / 2^k) + kn;
当 n = 2^k时，上式为 n T( 1 ) + n logn;舍去低阶项得T(n) = Theta( nlogn );

2.3-4 给插入排序最坏情况写一个递归式
T(n) = T(n-1) + n;

2.3-5 二分查找最坏时间为什么为logn
二分查找最坏为logn，即每次取中点值都不是，例如[1,2,3,4,5,6,7,8]中查找5或7,则需要进行log8 = 3 次的查找；

2.3-6 插入排序中引入了二分查找，可以将时间减少到nlogn吗？
不可以，因为即使降低了查找插入位置的时间，移动元素的时间依然存在，插入排序的时间依然为Θ（n^2）。

2.3-7 描述一个时间为nlogn的算法，给定n个整数的集合S和另一个数x，以确定S中是否存在两个数的和为x。
首先需要一个排序时间为nlogn的算法，即采用快排的方式进行排序，然后使用双指针进行查找，这样只需要过一遍全部数据，时间为n，代码如下：

  1. // 此代码未经编译运行，仅供复习参考，全记事本手打。
  2. public boolean judge(int[] nums ,int target) {
  3.     quickSort(nums);
  4.     int i=0,j=nums.length-1;
  5.     while (i<j && nums[i]+nums[j] != target) {
  6.         if (nums[i] + nums[j] < target) i++;
  7.         if (nums[i] + nums[j] > target) j--;
  8.     }
  9.     return (nums[i] + nums[j]) == x
  10. }
  12. public void quickSort(int[] nums) {
  13.     int len = nums.length;
  14.     sort(nums,0,len-1);
  15. }
  17. public void sort(int[] nums,int p,int r) {
  18.      if (p < r) {
  19.          int q = partition(nums,p,r);
  20.         sort(nums,p,q-1);
  21.         sort(nums,q,r);
  22.     }
  23. }
  25. public int partition(int nums,int p,int r) {
  26.      int x = nums[r];
  27.     int i = p - 1;
  28.     for (int j = p;j<r-1;j++) {
  29.          if (nums[j] < x) {
  30.             i++;
  31.             swap(nums,i,j);
  32.         }
  33.     }
  34.     swap(i+1,r);
  35.     return i+1;
  36. }
  38. public void swap(int[] nums,int a,int b) {
  39.      int temp = nums[a];
  40.     nums[a] = nums[b];
  41.     nums[b] = temp;
  42. }

思考题

2-1
a.插入排序在最坏情况下为n^2，即长度为k的子表所需时间为k*k,然后一共有n/k个子表，所以所需时间为nk。
b.因为已经做了一部分子表的合并，目前树高即为lg(n/k),每层需要n，所以为nlg(n/k).
c.nk+nlg(n/k) = nk + nlgn - nlogk;要使与归并排序有相同的时间nlgn,则k的最大值应为lgn，这时为2n
lgn + nlg(lgn),去掉常数项则为nlgn.
d.在实际应用中，应该选择k为lgn这样在理论上时间相等，但是在机器实际操作中可以使得性能达到最优。（个人意见不一定正确）

2-4 逆序对，对应LeetCode里面的题目，题目链接
代码实现：根据插入排序中得到的规律有，有多少个逆序对就需要进行多少次移动，于是改写归并排序，在时间上时间为nlgn。

  1. class Solution {
  3.     private int ans = 0;
  5.     public int reversePairs(int[] nums) {
  6.         int len = nums.length;
  7.         int[] temp = new int[len];
  8.         mergeSort(nums,0,len-1,temp);
  9.         return ans;
  10.     }
  12.     public void mergeSort(int[] nums,int p,int r,int[] temp) {
  13.         if (p < r) {
  14.             int q = (p+r)/2;
  15.             mergeSort(nums,p,q,temp);
  16.             mergeSort(nums,q+1,r,temp);
  17.             merge(nums,p,q,r,temp);
  18.         }
  19.     }
  21.     public void merge(int[] nums,int p,int q,int r,int[] temp) {
  22.         int len1 = q - p + 1;
  23.         int len2 = r - q; 
  24.         for (int i=p;i<=r;i++) {
  25.             temp[i-p] = nums[i];
  26.         }
  27.         int i = 0;
  28.         int j = 0;
  29.         int k = p;
  30.         for (k=p;k<=r&&i<len1&&j<len2;k++) {
  31.             if (temp[j+len1] < temp[i]) {
  32.                 ans = ans + len1 - i;
  33.                 // System.out.print(temp[j+len1]+":"+(len1)+" ");
  34.                 nums[k] = temp[j+len1];
  35.                 j++;
  36.             }else {
  37.                 nums[k] = temp[i];
  38.                 i++;
  39.             }
  40.         }
  41.         if (i!=len1) {
  42.             while (k<=r) {
  43.                 nums[k++] = temp[i++];
  44.             }
  45.         }
  46.         if (j!=len2) {
  47.             while (k<=r) {
  48.                 nums[k++] = temp[j+len1];
  49.                 j++;
  50.             }
  51.         }
  52.     }
  53. }