插入排序和归并排序的实现代码（C++）

浏览数：25 / 时间：2015年06月08日

插入排序和归并排序是算法导论先讲到的两中排序方法。

插入排序的思路是对于一个已经排好序的数组，现在新插入一个元素并且保持其有序。那么该如何插入呢，从数组最后一个元素开始进行比较，直到遇到比小于等于自己的元素，然后插入到该元素的后面（所以插入是稳定的）。循环不变式：子数组一直保持有序（使用循环不变式来证明算法正确性的方法类似于高中经常用的数学归纳法）。

归并排序的思想就是很有名的分治思想（divide and conquer）。从较小的多个有序数组得到较大的有序数组即合并，归并排序采用二路归并。多路归并可以使用败者数，或者链表。归并排序也是稳定的，这由合并的细节决定。

插入排序的时间复杂度Θ(n²),归并是Θ(nlgn)，归并需要额外Θ(n)的空间，而插入不需要(这里的空间不考虑保存的栈底指针，局部变量等)。

下面是实现：

//插入排序  (先部分有序逐渐扩大有序的数组至全部有序) stable
    /* 伪代码INSERTION-SORT(A)
    1 for j=2 to A.length
    2     key = A[j]
    3     i=j-1
    4     while(i>0 and A[i]>key)
    5           A[i+1]=A[i]
    6           i=i-1
    7     A[i+1]=key
    */

    void insertion_sort(int a[], int n){
        if (n < 2)
            return;
        int i, j;
        int key;
        for (j = 1; j < n; ++j){
            key = a[j];
            i = j - 1;
            while (i >= 0 && a[i] > key){
                a[i + 1] = a[i];
                --i;
            }
            a[i + 1] = key;
        }
        return;
    }

//归并排序
    /* MERGE_SORT(A,p,r)
      if p==r
      return
      mid=(p+r)/2           向下取整
      MERGE_SORT(A,p,mid)
      MERGE_SORT(A,mid+1,r)
      MERGE(A,p,mid,r)


      MERGE(A,p,mid,r)
      L1(1,n1)=A(p,mid)
      L2(1,n2）=A(mid,r)  放置哨兵值，即末尾是无穷大
      i=1
      j=1
      m=1
      while(!(L1[i]==MAX&&L2[j]==MAX))
      if(L1[i]<L2[j])
      A[m]=L1[i]
      ++i
      else
      A[m]=L2[i]
      ++j
      ++m
      */


    //指针加偏移量是个不错的选择
    void Merge(int *a, int p, int mid, int r)
    {
        int n1 = mid - p + 1;
        int n2 = r - mid;
        int *L = new int[n1 + 1];
        int *R = new int[n2 + 1];
        int i, j, k;

        for (i = 0; i < n1; i++){
            L[i] = a[p + i];
        }
        for (j = 0; j < n2; j++){
            R[j] = a[mid + j + 1];
        }
        L[n1] = INT_MAX;
        R[n2] = INT_MAX;

        for (i = 0, j = 0, k = p; k <= r; k++)
        {
            if (L[i] <= R[j])
            {
                a[k] = L[i];
                i++;
            }
            else{
                a[k] = R[j];
                j++;
            }
        }

        delete []L;
        delete []R;
    }

    void Merge_Sort(int *a, int p, int r)
    {
        if (p < r)
        {
            int mid = (p + r) / 2;
            Merge_Sort(a, p, mid);
            Merge_Sort(a, mid + 1, r);
            Merge(a, p, mid, r);
        }
    }