希尔排序

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

void shellsort(int a[],int n)
{
    int i,j,k,gap,tmp;
    for(gap=n/2;gap>0;gap/=2)//gap循环到0结束
      for(i=0;i<gap;i++)//每一个gap对应多少分组
       for(j=i+gap;j<n;j+=gap)//每组数据进行插入排序
        if(a[j]<a[j-gap])
        {
            for(k=j-gap;k>=0 && a[k]>a[k+gap];k-=gap)
                 swap1(a[k],a[k+gap]);
        }
}

希尔排序的效率受分组的gap影响，希尔排序算法复杂度为 O(n^2)

已知的最好步长串行是由Sedgewick提出的 (1, 5, 19, 41, 109,...)，该串行的项来自 9 * 4^i - 9 * 2^i + 1 和 4^i - 3 * 2^i + 1 这两个算式[1]。这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长串行的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
另一个在大数组中表现优异的步长串行是(斐波那契数列除去0和1将剩余的数以黄金分区比的两倍的幂进行运算得到的数列)：（1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713, …）[2]

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例
第一次 gap = 10 / 2 = 5
49   38   65   97   26   13   27   49   55   4
1A                       1B
     2A                       2B
          3A                       3B
               4A                       4B
                     5A                      5B
1A,1B，2A,2B等为分组标记，数字相同的表示在同一组
大写字母表示是该组的第几个元素每次对同一组的数据进行直接插入排序
即分成了五组(49, 13) (38, 27) (65, 49)  (97, 55)  (26, 4)
这样每组排序后就变成了(13, 49)  (27, 38)  (49, 65)  (55, 97)  (4, 26)

第二次 gap = 5 / 2 = 2
排序后
13   27   49   55   4    49   38   65   97   26
1A        1B        1C        1D        1E
     2A        2B        2C        2D        2E
第三次 gap = 2 / 2 = 1
4   26   13   27   38    49   49   55   97   65
1A  1B   1C   1D   1E    1F   1G   1H   1I   1J
第四次 gap = 1 / 2 = 0 排序完成得到数组：
4   13   26   27   38    49   49   55   65   97

归并排序

思路：归并排序是采用分治法的典型应用。归并排序的思想就是先递归分解数组，再合并数组。重点在于合并，由于两部分均有序，就是谁大取谁，不过很有可能需要引入一个临时的存储空间，在分配空间的时候有可能导致运行时间增加。

1.归并排序需要一个额外的数组（与待排序数组一样的大小），因此首先要检查是否可以额外申请内存而不出错，最后还要释放掉这个内存空间。

bool mysort(int a[],int n)
{
    int *p = new int[n];
    if(p==NULL)
        return false;
    mergesort(a,0,n-1,p);
    delete[] p;
    return true;
}

2.分解数组直到把数组中每一个元素都单独的视为一个数组为止，总共需要O(log n)。之后再进行合并，每一次合并需要O(n)。因此总的复杂度是O(n log n)，注意合并到临时数组之后，最后要把这个临时数组的数据复制回a数组中，即要复制回a[first]~a[last]当中..

    for(i=0;i<k;i++)
        a[first+i]=c[i];

完整的代码如下：

#include <stdio.h>
void merge_array(int a[],int first,int mid,int last,int c[])
{
    int i=first,j=mid+1,k=0;
    while(i<=mid && j<=last)
    {
        if(a[i]<=a[j])
            c[k++]=a[i++];
        else
            c[k++]=a[j++];
    }
    while(i<=mid)
        c[k++]=a[i++];
    while(j<=last)
        c[k++]=a[j++];

    for(i=0;i<k;i++)
        a[first+i]=c[i];

}
void mergesort(int a[],int first,int last,int tmp[])
{
    if(first<last)
    {
        int mid=(first+last)/2;
        mergesort(a,first,mid,tmp);
        mergesort(a,mid+1,last,tmp);
        merge_array(a,first,mid,last,tmp);
    }


}
bool mysort(int a[],int n)
{
    int *p = new int[n];
    if(p==NULL)
        return false;
    mergesort(a,0,n-1,p);
    delete[] p;
    return true;
}
int main()
{
    int a[10]={6,4,5,2,3,8,1,7,9,10};
    if(!mysort(a,10)) printf("Wrong!");
    for(int i=0;i<10;i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}

快速排序

该方法的基本思想是：分治法

1. 先从数列中取出一个数作为基准数。
   2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
   3．再对左右区间重复第二步，直到各区间只有一个数。

问题是如何选择基准数并且进行大小分区

1、从序列中选择一个数M，将该数与序列中第一个数交换；
2、从右边开始寻找一个比M大的数，将该数交换到左边存储M的位置，左边位置+1；
3、从左边开始寻找一个不大于M的数，将该数交换到右边存储M的位置，右边位置-1；
4、重复2-3，知道左右相遇，假设相遇位置为n。
5、把n左右两边两个子序列{begin,i-1}   {i+1,end}重复1-5直达左右两边只有一个数。

简单来说就是挖坑之后从右边开始找比基准大的数填坑，再从左边开始找比基准小的数来填坑，知道前后相遇。

void quick_sort(int a[],int l,int r)
{
    if(l<r)
    {
        int i=l,j=r;
        int x=a[l];//作为基准数
        while(i<j)
        {
            while(i<j&&a[j]>=x) j--;
            if(i<j)//如果右侧有小于x的数
             a[i++]=a[j];

            while(i<j&&a[i]<x) i++;
            if(i<j)
             a[j--]=a[i];
        }
            a[i]=x;
            quick_sort(a,l,i-1);
            quick_sort(a,i+1,r);
    }
}

堆排序

思路：堆排序是采用堆，即近似完全二叉树 。将待排序的数组{0到n-1}构成大根堆（或者小跟堆），将堆首和堆尾交换，重新调整剩下的{0到n-2}重新构成大根堆（或者小跟堆），继续上述步骤知道数组首位

二叉堆具有以下性质：
1.父节点值总是大于或等于（小于或等于）任何一个子节点值。
2.每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）。

需解决两个问题
1.如何由一个无序序列构成一个小，大根堆。从n/2-1开始（即从最后一个有叶子节点的结点开始），调整当前的结点位置，使其满足最小堆.

首先一个节点在数组中位置为i，其子节点的位置为2*i+1，2 *i+2。
也就是说对一个根节点为0的完全二叉树，其n/2及其之后的结点都是叶子结点
因为n/2的叶子节点为n+1超出了n。

//从无序数组建立堆
for(int i=n/2-1;i>=0;i--)
    heap_down(a,i,n);

2.调整剩余元素为小，大根堆。每一次把堆首和堆末尾的元素交换，移动到堆末尾的元素组成已排序区。

    for(i=n-1;i>=0;i--)//i表示当前的堆还剩余的元素
    {
        swap(a[i],a[0]);
        heap_down(a,0,i);
    }

完整的程序如下：注意在堆的调整顺序时实际就是插入排序..

#include <stdio.h>
void swap(int &a, int &b)
{
    if(a==b) return;
    a ^=b;
    b ^=a;
    a ^=b;
}

void heap_down(int a[],int i,int n)
{
    int j,tmp;
    tmp = a[i];
    j=2*i+1;
    while(j<n)//从i开始向其子节点中找看是否比i小的
    {
      if(j+1<n && a[j+1]<a[j]) j++; //左右孩子中最小的
      if(a[j]>=tmp) break;//如果子节点均大于a[i]则不需要调整

       a[i]=a[j];
       i=j;
       j=2*i+1;
    }
    a[i]=tmp;//最后i会是合适位置
}


int main()
{
    int a[10]={6,4,5,2,3,8,1,7,9,10};
    int n=10;
    for(int i=n/2-1;i>=0;i--)
        heap_down(a,i,n);

    for(i=n-1;i>=0;i--)
    {
        swap(a[i],a[0]);
        heap_down(a,0,i);
    }
    for(i=0;i<10;i++)
        printf("%d ",a[i]);
    printf("\n");
    return 0;
}

总结

简单排序有：bubble排序、直接选择排序、直接插入排序
复杂排序有：shell排序（性能略差）、归并排序、快排、堆排序

46850-cac909f239e6917d.png

从最好的角度看，冒泡和直接插入排序较好，因此在数据较少时，且整体有序时候，可以考虑冒泡或者直接插入排序
在最坏的情形下，堆排序和归并排序较好。其实从另外一个角度说明是逆序的情形下，是否可以考虑先逆转在进行排序。
递归角度考虑，采用递归实现的包括：归并排序和快排，需要考虑递归深度问题。