数据结构_排序总结

文件从逻辑上可分为排序顺序文件、一般（即非排序）顺序文件；从物理储上可分为连续文件、链接文件。（参考文件及查找-MarchOn）

定义

将文件的记录按记录关键字值递增或递减顺序重新组织，得到有序的文件记录。通常指的是连续顺序文件的排序，当然链接顺序文件也可；当记录只包含关键字时即为元素的排序。

分类

分类法1：内排序、外排序：排序是否完全在内存进行。（外排序用于数据量大而无法一次全装入内存的数据文件的排序，通常用多路归并法）。

分类法2：连续顺序文件排序、链接顺序文件排序

分类法3：稳定排序、不稳定排序：关键字值一样的文件记录在排序前后相对位置保持不变的排序是稳定排序。

时间效率

排序过程的基本动作包括元素比较和元素移动

衡量：排序算法的时间效率主要用排序过程中元素间的比较次数来衡量。

几个下界：

1、基于元素交换进行排序的算法的平均时间复杂度下限为Ω(nlgn)，可用决策树证明（n个元素有n!种排列，每确定两个数的大小关系进入一棵子树，故复杂度为 O( ln(n!) ) =O(nlgn)）。显然，桶排序、基数排序不是基于元素交换的排序，故不适用此结论；

2、基于相邻元素交换进行排序的算法平均时间复杂度下限为Ω(n²)（此下界比上述的下界更紧），且是稳定的。基于相邻元素交换或顺序移动（顺序移动本质上就是相邻元素交换）的排序算法是稳定的，如冒泡、插入（插入排序插入时本质上也是相邻元素交换）。

该下界的证明：基于交换的排序实际上就是消除序列中的逆序偶的过程，每次相邻交换最多消除一个逆序使总逆序数减1（相邻交换不会使逆序数增加，若不是相邻交换则可能会增加），而一个序列的平均逆序数为n(n-1)/4（因为一个序列L和其反序列L_r的逆序数和为n(n-1)/2），故此时为消除逆序最少要进行O(n²)次交换，即为一个下界。当然此下界对有些算法可能不够紧。

内排序

以下n为元素个数。

1、插入排序

思路：依次将未排序序列的第一个元素插入到前面的已排序序列中，也称简单插入排序或直接插入排序。是稳定排序。分为顺序插入、折半插入，后者与前者相比减少了比较次数（寻找插入位置）但移动次数不变。

复杂度：时间平均O(n²)、最好O(n)、最坏O(n²)；空间O(1)。

趟数：n-1。

比较次数（对顺序插入而言）：序列递增时最少，为n-1；递减时最多，为n(n-1)/2。（这里从后往前找该元素在前面已排序序列的插入位置，若从前往后找则结论相反即递减时最少）

代码（顺序插入与折半插入）：（由于当前待插入元素前的序列已经有序，因此可以通过复制来实现元素后移从而避免交换，减少操作步骤）

 1 //插入排序，依次将元素插入到元素前面的已排序序列中。 n-1趟 
 2 void insertSort1(int k[],int n)
 3 {//顺序插入
 4     int i,j,tmp;
 5     for(i=1;i<n;i++)
 6     {
 7         tmp=k[i];
 8         for(j=i-1;j>=0 && k[j]>tmp;j--)//若为≥则非稳定
 9         {
10             k[j+1]=k[j];
11         }
12         k[j+1]=tmp;
13     }
14 }
15 
16 void insertSort2(int k[],int n)
17 {//折半插入，采用折半查找应插入的位置。移动元素的次数不变，但比较次数（找元素应在的位置）少了 
18     int i,j,tmp;
19     int low,mid,high; 
20     for(i=1;i<n;i++)
21     {
22         tmp=k[i];
23         
24         low=0,high=i-1;
25         while(low<=high)
26         {
27             mid=low+(high-low)/2;
28             if(k[mid]>tmp) high=mid-1;//若为≥则非稳定
29             else low=mid+1;
30         }
31         
32         for(j=i-1;j>=low;j--)
33         {
34             k[j+1]=k[j];
35         }
36         k[j+1]=tmp;
37     }
38 }
39 
40 insertSort

View Code

2、冒泡排序

思路：通过可能的相邻元素交换来将未排序序列的最大值交换到该序列的末尾，重复此过程直到没有发生元素交换。是稳定排序。移动元素频繁，效率低。

复杂度：时间平均O(n²)、最好O(n)、最坏O(n²)；空间O(1)。

趟数：不定，[1,n-1]。

比较次数：初始序列递增时最少，为n-1，一趟完事；最小元素在末尾时最多，为n(n-1)/2，走n-1趟。

代码：

//冒泡排序，通过可能的相邻元素交换 将 未排序序列中的最大值交换到该未排序序列的末尾，直到没有发生元素交换。 序列升序时1趟、最小值在末尾时n-1趟。 
void bubbleSort(int k[],int n)
{
    int i,j,tmp;
    int flag=1;//可以简单暴力地进行n-1趟冒泡完成排序，但实际上若一趟冒泡下来没有相邻元素交换，则说明已有序，没必要继续后续趟的冒泡了。flag即用来达到此目的，用于标记上趟是否有相邻元素交换。 
    
    for(j=n-1; j>0; j--){//j为未排序序列的末元素位置
        if(!flag) { break; }
        flag=0;
        for(i=0;i<j;i++)
        {
            if(k[i]>k[i+1])//若为≥则非稳定
            {
                flag=1;
                
                tmp=k[i];
                k[i]=k[i+1];
                k[i+1]=tmp;
            }
        }
    }
}

View Code

3、选择排序

思路：依次从未排序序列选出最大元素放到该序列末尾。非稳定排序。

复杂度：时间平均O(n²)、最好(n²)、最坏O(n²)，即与序列初始状态无关；空间O(1)。

趟数：n-1。

比较次数：n(n-1)/2。

代码：

 1 //选择排序，依次从未排序序列中选择最大元素放到该未排序序列的末尾。n-1趟 
 2 void selectSort(int k[],int n)
 3 {
 4     int i,j,tmp;
 5     int d;//标记未排序序列中最大值元素的位置
 6     for(j=n-1;j>0;j--)//j为未排序序列末元素位置 
 7     {
 8         d=0;
 9         for(i=1;i<=j;i++)
10         {
11             if(k[i]>k[d]) d=i;
12         }
13         if(d!=j)
14         {
15             tmp=k[d];
16             k[d]=k[j];
17             k[j]=tmp;
18         }
19     }
20 }
21 
22 selectSort

View Code

4、希尔排序

思路：对直接插入排序的改进。也叫缩小增量排序法。是非稳定排序。希尔排序算法实现简单且性能又比上述一般算法好，因此很适用于适当大量输入数据的排序。

gap为一个递减的增量序列：h_t、h_t-1、...、h₂、h₁、1。每趟以gap值h_k为间距将序列分为h_k个独立子序列(相距h_k的元素属同一个子序列)，该趟的排序效果为使得每个子序列内有序即对于每个i有k[i]≤k[i+h_k]，子序列的排序可以选用插入排序、泡排序等。在很多情况下，gap为1时序列几乎已经有序，使得不需要进行较多元素的移动就能达到排序目的。

复杂度：时间平均O(nlgn)、最好O(nlgn)、最坏O(n²)；空间O(1)。

选择不同增量序列时，最坏时间复杂度可能有所改善：为折半gap序列时最坏时间复杂度为O(n²)；为奇数gap序列时最坏时间复杂度为O(n^1.5)；目前最好的Sedgewick序列为O(n^7/6)。

趟数：增量序列的长度，具体取决于增量序列的选择。因此是不定的。若采用折半gap序列则趟数为ceil(lg₂n)趟。

代码（这里子序列的排序分别用泡排序、插入排序，推荐用后者）：

 1 //希尔排序，对直接插入排序的改进。每趟以gap为间距将序列分为gap个独立子序列(相距gap的元素属同一个子序列)，该趟的排序效果为使得每个子序列内有序。gap从大到小，最后为1；子序列的排序可以选用 泡排序、选择排序等 
 2 void shellSort(int k[],int n)
 3 {
 4     int i,j,tmp,flag;
 5     int gap;
 6     for(gap=n/2;gap>0;gap/=2)
 7     {
 8         do//这里子序列内的排序采用泡排序 
 9         {
10             flag=0;
11             for(i=0;i<n-gap;i++)
12             {
13                 if(k[i]>k[i+gap])
14                 {
15                     flag=1;
16                     
17                     tmp=k[i];
18                     k[i]=k[i+gap];
19                     k[i+gap]=tmp;
20                 }
21             }
22         }while(flag==1);
23     }
24 }
25 
26 void shellSort(int k[],int n)
27 {
28     int i,j,tmp;
29     int gap;
30     for(gap=n/2;gap>0;gap/=2)
31     {//这里子序列内的排序采用插入排序 
32         for(i=gap;i<n;i++)
33         {
34             tmp=k[i];
35             for(j=i-gap;j>=0 && k[j]>tmp;j-=gap)
36             {
37                 k[j+gap]=k[j];
38             }
39             k[j+gap]=tmp;
40         }
41     }
42 }

shellSort

5、快速排序

思路：对冒泡排序的改进。选个枢纽元，将小于该元素的元素移到左边、大于的移到右边，此过程为一次划分；然后以枢纽元为界对两个子序列递归快排。非稳定排序。

复杂度：

平均时间复杂度：O(nlgn)，只要每次枢纽元的选取原则一样（如都取首元素或者都取中间元素），平均时间复杂度都为此。

最好时间复杂度：O(nlgn)。

最坏时间复杂度：与划分的结果有关，而划分的结果与枢纽元的选取原则有关。

若每次划分后长子序列的规模都缩小为原来的α倍（0<α<1，每次值可不一样），则最坏时间复杂度为O(nlgn)。如每次都取序列的中位数作为枢纽元，此时子序列均为原序列的一半规模。

最坏情形下每次划分都使得两个子序列规模分别为1、n-1，则最坏时间复杂度为O(n²)。如序列初始有序时此时退化为冒泡排序，时间复杂度为O(n²)。

空间复杂度：O(lgn)，一次划分时空间复杂度为O(1)，递归使得增长到O(lgn)。

枢纽元的选择：（只要每次划分时枢纽元的选取原则一样（如都取首元素或都取中间元素），平均复杂度都为O(nlgn)，但最坏复杂度则与枢纽元的选取有关，如选首元素最坏O(n²)而选中位数最坏O(nlgn)；除非题特别说明，否则一般指的是以首元素为枢纽元）。

首元素或随机选择方案（随机选一个元素并交换到首元素，然后按首元素为枢纽元的情况处理）均不好，前者在序列初始有序时恶化成O(n²)、后者随机法耗时且不能保证总是划分成对称大小的两个子序列因此最坏也为O(n²)；

选中位数总能将元素划分成两半，可以在O(n)时间内完成（相当于选第n/2大），因此整个排序复杂度最坏也为O(nlgn)，但选中位数较麻烦；

实际应用中一般用 首、末、中心 三元素的中值。

趟数：不定。

代码（两种实现方法，如果要求用链表来实现快排，则第二种可以改造成链表版本）：（可用宏定义实现交换两元素，避免函数调用实现方法的开销： #define swap(T, a, b) { T c=a; a=b; b=c;} ）

//快排，对冒泡排序的改进 。选择一个枢纽元，然后将小于枢纽元的元素整理到其左边、大于的整理到右边。
void quickSort1(int k[],int s,int t)//s、t分别为起点、终点元素的下标 
{//这里以首元素作枢纽元 
    if(s>=t)return ;
    int i,j;
    i=s-1;//以扫描所有元素。这里也可以初始为s，但为了与可指定pivot的对应，这里为s-1
    j=t+1;//初始指向末元素的后一个位置
    while(1)
    {
        do{i++;}while(!(i==t || k[i]>=k[s]));
//        while( k[++i]<k[s] && i<t);//与上句等价。由于到这里s肯定小于t所以while里的两个表达式谁前谁后没影响，下同。
        
        do{j--;}while(!(j==s || k[j]<=k[s]));
//        while(k[--j]>k[s] && j>s);//与上句等价
        
        if(i<j)
        {
            swapForQuickSort(&k[j],&k[i]);
        }
        else break;        
    }
    swapForQuickSort(&k[j],&k[s]);
    quickSort1(k,s,j-1);
    quickSort1(k,j+1,t);
}

void quickSort2(int k[],int s,int t)
{//这里以首元素作为枢纽元 
    if(s>=t) return;
    int i=s,j=s;
    while(++i <=t)//小于枢纽元的放到枢纽元的后面 
    {
        if(k[i]<k[s])
        {
            swapForQuickSort(&k[i],&k[++j]);
        }
    }
    swapForQuickSort(&k[j],&k[s]);
    quickSort2(k,s,j-1);
    quickSort2(k,j+1,t);
}

quickSort

quickSort

quickSort

可以指定枢纽元选取原则的实现方法（与上面的两种对应）：

 1 void quickSort1_pivot(int k[],int s,int t)
 2 {//可以自定义枢纽元 
 3     if(s>=t) return;
 4     
 5     int pivot=s+(t-s+1)/3;//指定枢纽元 
 6     int i=s-1;//初始化使得遍历所有元素 
 7     int j=t+1;
 8     while(1)
 9     {
10         do {i++;} while(!(i==t || k[i]>=k[pivot]));
11 //        while(k[++i]<k[pivot] && i<t);//与上句等价
12 
13         do {j--;} while(!(j==s || k[j]<=k[pivot]));
14 //        while(k[--j]>k[pivot] && j>s);//与上句等价
15 
16         if(i<j)
17         {
18             swapForQuickSort(&k[j],&k[i]);
19             if(i==pivot) pivot=j;
20             else if(j==pivot) pivot=i;
21         }
22         else break;
23     }
24     //循环结束后i=j+1,pivot所在元素应该与i、j离pivot近者交换
25     //因为若pivot≥i，由于k[i]是从前往后k[s,...,i]中第一个≥k[pivot]的，则k[s,...,i-1]＜k[pivot]，故交换k[i]、k[pivot]；
26     //若pivot＜i即pivot≤j ，由于k[j]是从后往前k[t,...,j]中第一个≤k[pivot]的，则k[j+1,...,t]＞k[pivot]，故交换k[j]、k[pivot] 
27     if(pivot>=i)
28     {
29         j=i;
30     }
31 
32     swapForQuickSort(&k[pivot],&k[j]);
33     quickSort1_pivot(k,s,j-1);
34     quickSort1_pivot(k,j+1,t);
35 }
36 
37 void quickSort2_pivot(int k[],int s,int t)
38 {//可以自定义枢纽元 
39     if(s>=t) return;
40     
41     int pivot=s+(t-s+1)/3;//指定枢纽元 
42     int i=s-1;//初始化使得遍历所有元素 
43     int j=s-1;
44     while(++i <=t)//小于枢纽元的放到数组前部分 
45     {
46         if(k[i]<k[pivot])
47         {
48             swapForQuickSort(&k[i],&k[++j]);
49             if(pivot==j)pivot=i;//由于比k[pivot]小的才会交换，故被交换的k[i]不会是k[pivot] 
50         }
51     }
52     swapForQuickSort(&k[pivot],&k[++j]);
53     
54     quickSort2_pivot(k,s,j-1);
55     quickSort2_pivot(k,j+1,t);
56 }

quickSort_pivot

模板：关键在于划分函数Partition的实现。

1 void quickSort(int *data,int p,int r)
2 {
3     //调用者应该确保p<r
4     if(p>=r) return;
5     int q=Partition(data,p,r);//Partition选一个基准元将data划分为左右两部分。不同的Partition实现可以实现不同的快排，如随机快排等 
6     quickSort(data,p,q-1);//对左部分排序 
7     quickSort(data,q+1,r);//对右部分排序 
8 }

以下是几种Partition实现：

 1 //Partition的一种实现。以首元素为枢纽元
 2 int Partition(int *data,int p,int r)
 3 {
 4     int i=p,j=r+1;
 5     while(1)
 6     {
 7         while(data[++i]<data[p] && i<r);
 8         while(data[--j]>data[p] && j>p);
 9         if(i<j) swapForQuickSort(&data[i],&data[j]);
10         else break;
11     }
12     swapForQuickSort(&data[p],&data[j]);
13     return j;
14 }
15 
16 //Partition的一种实现。随机划分算法  
17 int RandomPartition(int *data,int p,int r)
18 {
19     int i=Random(p,r);//随机选一个元素作为枢纽元
20     swapForQuickSort(&data[p],&data[i]);//交换到首位
21     return Partition(data,p,r);
22 }

Partition

拓展：基于此划分思想可以解决很多问题，如从序列选第k小元素，按此方法其平均复杂度为O(n)，关键也在于Partition方法——只有保证每次划分出的两个子序列的规模至少为原来的α倍（0<α<1）才能保证最坏也为T(n)=T(αn)+O(n)=O(n)。

6、堆排序

思路：对选择排序的改进。（与选择排序类似，依次从未排序序列选出最大元素放到该序列末尾，只不过这里选择最大元素是通过堆来选择的）元素用完全二叉树的数组形式存储，走n-1趟。升序排用大顶堆、降序排用小顶堆，以大顶堆为例第i趟排序就是把前n+1-i个元素组成大顶堆并把堆的首末元素交换。非稳定排序。

复杂度：时间平均O(nlgn)，最好、最坏均为此；空间O(1)。

趟数：n-1。

代码：建初始堆（复杂度O(n)）；然后将堆顶元素与堆尾元素交换并维护堆的性质（维护的复杂度O(lgn)），如此往复n-1次即可（复杂度为 n*O(lgn)=O(nlgn) ）。P344

 1 //堆排序，对选择排序的改进。n-1趟，以大顶堆为例，第i趟将前n+1-i个元素组成大顶堆并把堆顶元素与末元素交换。 
 2 void adjust(int k[],int n,int i)//元素采用完全二叉树形式存储在k[]。调整以i为堆顶的大顶堆。时间复杂度O(lgn) 
 3 {
 4     int tmp=k[i];
 5     int j;//j指向左右孩子较大者
 6     
 7     j=2*i+1;
 8     while(j<n)
 9     {
10         if(j<n-1 && k[j]<k[j+1]) j++;
11         if(tmp<k[j])
12         {
13             k[(j-1)/2]=k[j];
14             j=2*j+1;
15         }
16         else
17         {
18             break;
19         }
20     }
21     k[(j-1)/2]=tmp;//上面的循环有可能因为j>=n而退出而非因else而退出，所以此句不能放else里 
22 }
23 void heapSort(int k[],int n)
24 {
25     int i,tmp;
26     for(i=(n-1)/2;i>=0;i--)//建立初始堆：从完全二叉树的最后一个分支节点开始，从下往上从右往左调整以该分支节点为根节点的堆。 时间复杂度O(n) 
27     {
28         adjust(k,n,i);
29     }
30     for(i=n-1;i>=1;i--)//进行n-1趟，每趟将首元素交换到未排序序列末尾i，然后序列长度减1并调整堆。 数据复杂度O(nlgn) 
31     {
32         tmp=k[0];
33         k[0]=k[i];
34         k[i]=tmp;
35         adjust(k,i,0);
36     }
37 }
38 
39 heapSort

View Code

时间复杂度分析：堆维护一次的复杂度为元素最大可能移动次数，即树高，所以为O(lgn)。建初堆复杂度为调整以每个分支节点为根节点的子树时的最大可能移动次数的和，可以假定完全二叉树是满的，则易求出和为O(n)。

其他：上面提到了堆的建立和维护，其实质是堆顶元素的“下沉”，除之外，堆的操作还有删除、插入操作：删除（即删除堆顶元素）通常是直接将堆末元素放到堆顶然后对之维护，也是“下沉”；插入通常是将元素插入到序列末尾然后将该元素“上浮”。

删除后进行下沉、插入后进行上浮的示例（https://www.cnblogs.com/CarpenterLee/p/5488070.html）：

//java code

//siftDown()
private void siftDown(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
        //首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
        int child = (k << 1) + 1;//leftNo = parentNo*2+1
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c;//然后用c取代原来的值
        k = child;
    }
    queue[k] = x;
}


//siftUp()
private void siftUp(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)//调用比较器的比较方法
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

View Code

其他：堆的应用

优先队列

从n个元素里选m个最小的元素：建m个元素的大顶堆，对于后面到来的元素，若小于堆顶元素则替换堆顶元素然后维护大顶堆性质、否则忽略该元素。（若选m个最大，则建小顶堆）。

排序：升序大顶堆、降序小顶堆。

7、二路归并排序

也叫合并排序。

思路：每趟依次将相邻的一对子序列归并为一个更大的子序列，子序列的长度从1开始每趟逐渐加倍，进行ceil(lgn)趟。稳定排序。

复杂度：时间平均O(nlgn)，最好、最坏均为此；空间O(n)。空间复杂度最高，所以主要用于外部排序而很难用于内排序。

趟数：ceil(lgn)

代码：

递归版：

 1 //合并排序的子函数，用于将连个排好序的序列合并成一个有序序列 
 2 void merge(int from[],int to[],int s,int m,int e)
 3 {
 4     int i=s,j=m+1,k=s;
 5     while(i<=m && j<=e)
 6     {
 7         if(from[i]<=from[j]) to[k++]=from[i++];
 8         else to[k++]=from[j++];
 9     }
10     while(i<=m) to[k++]=from[i++];
11     while(j<=e) to[k++]=from[j++];
12 }
13 
14 
15 //合并排序递归版 
16 void mergeSort_recursive(int *data,int *tmp,int s,int e)//tmp为合并时临时使用的辅助空间 
17 {
18     if(s>=e) return;
19     int m=s+(e-s)/2;
20     mergeSort_recursive(data,tmp,s,m);
21     mergeSort_recursive(data,tmp,m+1,e);
22     
23     merge(data,tmp,s,m,e);//合并到数组tmp
24     int i=s;
25     while(i<=e) {data[i]=tmp[i];i++;} //复制回数组a 
26 }

View Code

非递归版：

 1 //合并排序的子函数，用于将连个排好序的序列合并成一个有序序列 
 2 void merge(int from[],int to[],int s,int m,int e)
 3 {
 4     int i=s,j=m+1,k=s;
 5     while(i<=m && j<=e)
 6     {
 7         if(from[i]<=from[j]) to[k++]=from[i++];
 8         else to[k++]=from[j++];
 9     }
10     while(i<=m) to[k++]=from[i++];
11     while(j<=e) to[k++]=from[j++];
12 }
13 
14 
15 //data中有一系列已排好序的大小为size的相邻子数组。将每相邻的两个合并为一个，存入tmp 
16 void mergePass(int *data,int *tmp,int size,int n)
17 {
18     int i=0;
19     while(i <= n-2*size)
20     {
21         merge(data,tmp,i,i+size-1,i+2*size-1);//合并大小为size的相邻2个有序子数组到tmp 
22         i+= 2*size;
23     }
24     //剩下元素个数少于2*size
25     if(i<n-size)  merge(data,tmp,i,i+size-1,n-1);
26     else for(;i<n;i++) tmp[i]=data[i];//merge(data,tmp,i,n-1,n-1);
27 }
28 //合并排序非递归版
29 void mergeSort(int *data,int n) 
30 {
31     int tmp[n];
32     int size=1;//子数组大小
33     while(size<n) 
34     {
35         mergePass(data,tmp,size,n);
36         size+=size;
37         mergePass(tmp,data,size,n);
38         size+=size;
39     }
40 }

View Code

其他：自然合并排序：扫描一趟得到初始有序的各子序列，然后对之进行若干次合并，与上述归并排序相比能够减少合并次数。在初始有序时时间复杂度为O(n)，而上述方法仍需要O(nlgn)。

采用链式存储时的二路归并排序：与顺序存储类似，难点在于找链表中间节点——可以用快慢指针：每次分别移动2、1步，则快者为null时慢者即为中间节点。

8、基数排序（类似桶排序）

思路：一个数的序列，每个数为d位r进制数，从末位到首位每次以该位数为关键字进行排序，进行d趟。稳定排序。

复杂度：时间平均O(d(r+n))，最好、最坏均如是；空间O(r+n)。实际上复杂度与实现有关，这里对P349的实现而言。

趟数：d

是桶排序的扩展，桶排序：设m个桶（m≥n），采用相同原则将每个元素对应到某个桶（如对应到元素值与桶下标值相等的桶中），然后顺序遍历桶即得到排序序列。时间复杂度为O(m+n)、空间复杂度为O(m)。

以上的所有代码：

  1 #include<stdio.h>
  2 
  3 
  4 
  5 //插入排序，依次将元素插入到元素前面的已排序序列中。通过复制实现元素后移以避免明显地使用交换。 n-1趟 
  6 void insertSort1(int k[],int n)
  7 {//顺序插入
  8     int i,j,tmp;
  9     for(i=1;i<n;i++)
 10     {
 11         tmp=k[i];
 12         for(j=i-1;j>=0 && k[j]>tmp;j--)
 13         {
 14             k[j+1]=k[j];
 15         }
 16         k[j+1]=tmp;
 17     }
 18 }
 19 void insertSort2(int k[],int n)
 20 {//折半插入，采用折半查找应插入的位置。移动元素的次数不变，但比较次数（找元素应在的位置）少了 
 21     int i,j,tmp;
 22     int low,mid,high; 
 23     for(i=1;i<n;i++)
 24     {
 25         tmp=k[i];
 26         
 27         low=0,high=i-1;
 28         while(low<=high)
 29         {
 30             mid=low+(high-low)/2;
 31             if(k[mid]>tmp) high=mid-1;
 32             else low=mid+1;
 33         }
 34         
 35         for(j=i-1;j>=low;j--)
 36         {
 37             k[j+1]=k[j];
 38         }
 39         k[j+1]=tmp;
 40     }
 41 }
 42 
 43 
 44 //冒泡排序，通过可能的相邻元素交换 将 未排序序列中的最大值交换到该未排序序列的末尾，直到没有发生元素交换。 序列升序时1趟、最小值在末尾时n-1趟。 
 45 void bubbleSort(int k[],int n)
 46 {
 47     int i,j,tmp;
 48     int flag;//可以简单暴力地进行n-1趟冒泡完成排序，但实际上若一趟冒泡下来没有相邻元素交换，则说明已有序，没必要继续后续趟的冒泡了。flag即用来达到此目的，用于标记上趟是否有相邻元素交换。 
 49     
 50     j=n-1;//j为未排序序列的末元素位置
 51     do
 52     {
 53         flag=0;
 54         for(i=0;i<j;i++)
 55         {
 56             if(k[i]>k[i+1])
 57             {
 58                 flag=1;
 59                 
 60                 tmp=k[i];
 61                 k[i]=k[i+1];
 62                 k[i+1]=tmp;
 63             }
 64         }
 65         j--;
 66     }while(flag==1);
 67 } 
 68 
 69 //选择排序，依次从未排序序列中选择最大元素放到该未排序序列的末尾。n-1趟 
 70 void selectSort(int k[],int n)
 71 {
 72     int i,j,tmp;
 73     int d;//标记未排序序列中最大值元素的位置
 74     for(j=n-1;j>=0;j--)//j为未排序序列末元素位置 
 75     {
 76         d=0;
 77         for(i=1;i<=j;i++)
 78         {
 79             if(k[i]>k[d]) d=i;
 80         }
 81         if(d!=j)
 82         {
 83             tmp=k[d];
 84             k[d]=k[j];
 85             k[j]=tmp;
 86         }
 87     }
 88 }
 89 
 90 
 91 void swapForQuickSort(int *a,int *b)
 92 {
 93     int tmp=*a;
 94     *a=*b;
 95     *b=tmp;
 96 }
 97 //希尔排序，对直接插入排序的改进。每趟以gap为间距将序列分为gap个独立子序列(相距gap的元素属同一个子序列)，该趟的排序效果为使得每个子序列内有序。gap从大到小，最后为1；子序列的排序可以选用 泡排序、选择排序等 
 98 void shellSort(int k[],int n)
 99 {
100     int i,j,tmp,flag;
101     int gap;
102     for(gap=n/2;gap>0;gap/=2)
103     {
104         do//这里子序列内的排序采用泡排序 
105         {
106             flag=0;
107             for(i=0;i<n-gap;i++)
108             {
109                 if(k[i]>k[i+gap])
110                 {
111                     flag=1;
112                     
113                     tmp=k[i];
114                     k[i]=k[i+gap];
115                     k[i+gap]=tmp;
116                 }
117             }
118         }while(flag==1);
119     }
120 }
121 
122 void shellSort2(int k[],int n)
123 {
124     int i,j,tmp;
125     int gap;
126     for(gap=n/2;gap>0;gap/=2)
127     {//这里子序列内的排序采用插入排序 
128         for(i=gap;i<n;i++)
129         {
130             tmp=k[i];
131             for(j=i-gap;j>=0 && k[j]>tmp;j-=gap)
132             {
133                 k[j+gap]=k[j];
134             }
135             k[j+gap]=tmp;
136         }
137     }
138 }
139 
140 
141 void quickSort(int *data,int p,int r)
142 {
143     if(p>=r) return;
144     int q=Partition(data,p,r);//Partition选一个基准元将data划分为左右两部分。不同的Partition实现可以实现不同的快排，如随机快排等 
145     quickSort(data,p,q-1);//对左部分排序 
146     quickSort(data,q+1,r);//对右部分排序 
147 }
148 
149 //Partition的一种实现。不同的Partition实现可以实现不同的快排，如随机快排等  
150 int Partition(int *data,int p,int r)
151 {
152     //调用者应该确保p<r 
153     int i=p,j=r+1;
154     while(1)
155     {
156         while(data[++i]<data[p] && i<r);
157         while(data[--j]>data[p] && j>p);
158         if(i<j) swapForQuickSort(&data[i],&data[j]);
159         else break;
160     }
161     swapForQuickSort(&data[p],&data[j]);
162     return j;
163 }
164 
165 
166 //快排，对冒泡排序的改进 。选择一个枢纽元，然后将小于枢纽元的元素整理到其左边、大于的整理到右边。
167 void quickSort1(int k[],int s,int t)//s、t分别为起点、终点元素的下标 
168 {//这里以首元素作枢纽元 
169     if(s>=t)return ;
170     int i,j;
171     i=s;//初始指向第一个元素
172     j=t+1;//初始指向末元素的后一个位置
173     while(1)
174     {
175         do{i++;}while(!(i==t || k[i]>=k[s]));
176 //        while( k[++i]<k[s] && i<t);//与上句等价.由于到这里s肯定小于t，所以两个表达式谁前谁后没影响。但最好先检查边界以免越界: while(++i<t && k[i]<k[s])
177         
178         do{j--;}while(!(j==s || k[j]<=k[s]));
179 //        while(k[--j]>k[s] && j>s);//与上句等价
180         
181         if(i<j)
182         {
183             swapForQuickSort(&k[j],&k[i]);
184         }
185         else break;        
186     }
187     swapForQuickSort(&k[j],&k[s]);
188     quickSort1(k,s,j-1);
189     quickSort1(k,j+1,t);
190 }
191 void quickSort1_pivot(int k[],int s,int t)
192 {//可以自定义枢纽元 
193     if(s>=t) return;
194     
195     int pivot=s+(t-s+1)/3;//指定枢纽元 
196     int i=s-1;//初始化使得遍历所有元素 
197     int j=t+1;
198     while(1)
199     {
200         do {i++;} while(!(i==t || k[i]>=k[pivot]));
201 //        while(k[++i]<k[pivot] && i<t);//与上句等价
202 
203         do {j--;} while(!(j==s || k[j]<=k[pivot]));
204 //        while(k[--j]>k[pivot] && j>s);//与上句等价
205 
206         if(i<j)
207         {
208             swapForQuickSort(&k[j],&k[i]);
209             if(i==pivot) pivot=j;
210             else if(j==pivot) pivot=i;
211         }
212         else break;
213     }
214     //循环结束后i=j+1,pivot所在元素应该与i、j离pivot近者交换 
215     //因为若pivot≥i，由于k[i]是从前往后k[s,...,i]中第一个≥k[pivot]的，则k[s,...,i-1]＜k[pivot]，故交换k[i]、k[pivot]；
216     //若pivot＜i即pivot≤j ，由于k[j]是从后往前k[t,...,j]中第一个≤k[pivot]的，则k[j+1,...,t]＞k[pivot]，故交换k[j]、k[pivot] 
217     if(pivot>=i)
218     {
219         j=i;
220     }
221 
222     swapForQuickSort(&k[pivot],&k[j]);
223     quickSort1_pivot(k,s,j-1);
224     quickSort1_pivot(k,j+1,t);
225 }
226 
227 
228 void quickSort2(int k[],int s,int t)
229 {//这里以首元素作为枢纽元 
230     if(s>=t) return;
231     int i=s,j=s;
232     while(++i <=t)//小于枢纽元的放到枢纽元的后面 
233     {
234         if(k[i]<k[s])
235         {
236             swapForQuickSort(&k[i],&k[++j]);
237         }
238     }
239     swapForQuickSort(&k[j],&k[s]);
240     quickSort2(k,s,j-1);
241     quickSort2(k,j+1,t);
242 }
243 void quickSort2_pivot(int k[],int s,int t)
244 {//可以自定义枢纽元 
245     if(s>=t) return;
246     
247     int pivot=s+(t-s+1)/3;//指定枢纽元 
248     int i=s-1;//初始化使得遍历所有元素 
249     int j=s-1;
250     while(++i <=t)//小于枢纽元的放到数组前部分 
251     {
252         if(k[i]<k[pivot])
253         {
254             swapForQuickSort(&k[i],&k[++j]);
255             if(pivot==j)pivot=i;//由于比k[pivot]小的才会交换，故被交换的k[i]不会是k[pivot] 
256         }
257     }
258     swapForQuickSort(&k[pivot],&k[++j]);
259     
260     quickSort2_pivot(k,s,j-1);
261     quickSort2_pivot(k,j+1,t);
262 }
263 
264 
265 
266 //堆排序，对选择排序的改进。n-1趟，以大顶堆为例，第i趟将前n+1-i个元素组成大顶堆并把堆顶元素与末元素交换。 
267 void adjust(int k[],int n,int i)//元素采用完全二叉树存储在k[]。调整以i为堆顶的大顶堆。时间复杂度O(lgn) 
268 {
269     int tmp=k[i];
270     int j;//j指向左右孩子较大者
271     
272     j=2*i+1;
273     while(j<n)
274     {
275         if(j<n-1 && k[j]<k[j+1]) j++;
276         if(tmp<k[j])
277         {
278             k[(j-1)/2]=k[j];
279             j=2*j+1;
280         }
281         else
282         {
283             break;
284         }
285     }
286     k[(j-1)/2]=tmp;//上面的循环有可能因为j>=n而退出而非因else而退出，所以此句不能放else里 
287 }
288 void heapSort(int k[],int n)
289 {
290     int i,tmp;
291     for(i=(n-2)/2;i>=0;i--)//建立初始堆：从完全二叉树的最后一个分支节点开始，从下往上从右往左调整以该分支节点为根节点的堆。 时间复杂度O(n) 
292     {
293         adjust(k,n,i);
294     }
295     for(i=n-1;i>=1;i--)//进行n-1趟，每趟将首元素交换到未排序序列末尾i，然后序列长度减1并调整堆。 数据复杂度O(nlgn) 
296     {
297         tmp=k[0];
298         k[0]=k[i];
299         k[i]=tmp;
300         adjust(k,i,0);
301     }
302 }
303 
304 
305 //合并排序的子函数，用于将连个排好序的序列合并成一个有序序列 
306 void merge(int from[],int to[],int s,int m,int e)
307 {
308     int i=s,j=m+1,k=s;
309     while(i<=m && j<=e)
310     {
311         if(from[i]<=from[j]) to[k++]=from[i++];
312         else to[k++]=from[j++];
313     }
314     while(i<=m) to[k++]=from[i++];
315     while(j<=e) to[k++]=from[j++];
316 }
317 
318 
319 //合并排序递归版 
320 void mergeSort_recursive(int *data,int *tmp,int s,int e)//tmp为合并时临时使用的辅助空间 
321 {
322     if(s>=e) return;
323     int m=s+(e-s)/2;
324     mergeSort_recursive(data,tmp,s,m);
325     mergeSort_recursive(data,tmp,m+1,e);
326     
327     merge(data,tmp,s,m,e);//合并到数组tmp
328     int i=s;
329     while(i<=e) {data[i]=tmp[i];i++;} //复制回数组a 
330 }
331 
332 //data中有一系列已排好序的大小为size的相邻子数组。将每相邻的两个合并为一个，存入tmp 
333 void mergePass(int *data,int *tmp,int size,int n)
334 {
335     int i=0;
336     while(i <= n-2*size)
337     {
338         merge(data,tmp,i,i+size-1,i+2*size-1);//合并大小为size的相邻2个有序子数组到tmp 
339         i+= 2*size;
340     }
341     //剩下元素个数少于2*size
342     if(i<n-size)  merge(data,tmp,i,i+size-1,n-1);
343     else
344     {
345 //        for(;i<n;i++) tmp[i]=data[i];
346         merge(data,tmp,i,n-1,n-1);
347     }
348 }
349 //合并排序非递归版
350 void mergeSort(int *data,int n) 
351 {
352     int tmp[n];
353     int size=1;//子数组大小
354     while(size<n) 
355     {
356         mergePass(data,tmp,size,n);
357         size+=size;
358         mergePass(tmp,data,size,n);
359         size+=size;
360     }
361 }
362 
363 
364 
365 //将奇数移到左边，偶数移到右边
366 void arrangeOf2Sets(int k[],int n,int isStable)
367 {//约定i为当前元素位置，s之前的元素为奇数（不包括s） 
368     int i,s,tmp;
369     s=0;
370     if(isStable)
371     {//稳定的排序 
372         int t;
373         for(i=0;i<n;i++)
374         {
375             if(k[i] & 1==1)
376             {//后移为k[i] 腾出位置 
377                 for(tmp=k[i],t=i;t>s;t--)
378                 {
379                     k[t]=k[t-1];
380                 }
381                 k[s]=tmp;
382                 ++s;
383             }
384         }
385     }
386     else
387     {//非稳定排序 
388         for(i=0;i<n;i++)
389         {
390             if(k[i] & 1==1)
391             {//直接交换 
392                 tmp=k[s];
393                 k[s]=k[i];
394                 k[i]=tmp;
395                 ++s;
396             }
397         }
398     }
399 } 
400 
401 void arrangeOf3Sets(int k[],int n)
402 {//约定s之前的元素均为正数，e之后的元素均为负数，i为当前元素位置 
403     int s,e,i,tmp;
404     s=0;
405     e=n-1;
406     
407     i=s;
408     while(i<=e)
409     {
410         if(k[i]>0)
411         {
412             tmp=k[i];
413             k[i]=k[s];
414             k[s]=tmp;
415             s++;
416         }
417         else if(k[i]==0)
418         {
419             i++;
420         }
421         else
422         {
423             tmp=k[i];
424             k[i]=k[e];
425             k[e]=tmp;
426             e--;
427         }
428     }
429 }
430 
431 void printAry(int k[],int n)
432 {
433     int i;
434     for(i=0;i<n;i++)
435     {
436         printf("%d ",k[i]);
437     }
438     printf("
");
439 }
440 
441 
442 
443 
444 int main()
445 {
446     int k1[]={1,2,3,4,5};
447     int k2[]={5,4,3,2,1};
448     int k3[]={5,1,4,3,2};
449     int k4[]={1};
450     int n=sizeof(k1)/sizeof(int);
451     
452     
453     //插入排序 
454 //    insertSort1(k1,n);
455 //    insertSort1(k2,n);
456 //    insertSort1(k3,n);
457 //    insertSort1(k4,1);
458 
459 //    insertSort2(k1,n);
460 //    insertSort2(k2,n);
461 //    insertSort2(k3,n);
462 //    insertSort2(k4,1);
463 
464 
465 
466     //冒泡排序
467 //    bubbleSort(k1,n);
468 //    bubbleSort(k2,n);
469 //    bubbleSort(k3,n);
470 //    bubbleSort(k4,1);
471 
472 
473 
474     //选择排序 
475 //    selectSort(k1,n);
476 //    selectSort(k2,n);
477 //    selectSort(k3,n);
478 //    selectSort(k4,1);
479 
480 
481 
482     //希尔排序 
483 //    shellSort(k1,n);
484 //    shellSort(k2,n);
485 //    shellSort(k3,n);
486 //    shellSort(k4,1);
487 
488 //    shellSort2(k1,n);
489 //    shellSort2(k2,n);
490 //    shellSort2(k3,n);
491 //    shellSort2(k4,1);
492 
493 
494 
495     //快排 
496 
497 //    quickSort1(k1,0,n-1);
498 //    quickSort1(k2,0,n-1);
499 //    quickSort1(k3,0,n-1);
500 //    quickSort1(k4,0,0);
501 
502 //    quickSort2(k1,0,n-1);
503 //    quickSort2(k2,0,n-1);
504 //    quickSort2(k3,0,n-1);
505 //    quickSort2(k4,0,0);
506     
507 //    quickSort1_pivot(k1,0,n-1);
508 //    quickSort1_pivot(k2,0,n-1);
509 //    quickSort1_pivot(k3,0,n-1);
510 //    quickSort1_pivot(k4,0,0);
511 
512 //    quickSort2_pivot(k1,0,n-1);
513 //    quickSort2_pivot(k2,0,n-1);
514 //    quickSort2_pivot(k3,0,n-1);
515 //    quickSort2_pivot(k4,0,0);
516     
517     
518     
519     //堆排序 
520 //    heapSort(k1,n);
521 //    heapSort(k2,n);
522 //    heapSort(k3,n);
523 //    heapSort(k4,1);
524 
525 
526     //归并排序
527 //    int tmp[n];
528 //    mergeSort_recursive(k1,tmp,0,n-1);
529 //    mergeSort_recursive(k2,tmp,0,n-1);
530 //    mergeSort_recursive(k3,tmp,0,n-1);
531 //    mergeSort_recursive(k4,tmp,0,0);
532     
533     mergeSort(k1,n);
534     mergeSort(k2,n);
535     mergeSort(k3,n);
536     mergeSort(k4,1);
537 
538     
539     //奇数左边偶数右边 
540 //    arrangeOf2Sets(k3,n,0);
541 
542     //正数左边、0中间、负数右边
543 //    int d[]={-1,0,2,-2,4,-5,9,0};
544 //    arrangeOf3Sets(d,8);
545 //    printAry(d,8);
546 
547     
548     printAry(k1,n);
549     printAry(k2,n);
550     printAry(k3,n);
551     printAry(k4,1);
552     return 0;
553 }

sorts

9、计数排序（枚举排序、秩排序）

思路：对每一个要排序的元素，统计小于它的所有元素的个数，从而得到该元素在整个序列中的位置。n趟。稳定排序（跟实现有关）。

复杂度：时间平均O(n²)、最好均如是；空间O(n)。

趟数：n

10、耐心排序（Patience Sorting）

参阅：MarchOn-最长递增子序列-Patience Game、Princeton-Course-LIS

总结

（主要是前六种）

————————————————————————————————————————————————————————————————————————————

| 排序方法　　平均时间复杂度　　最坏时间复杂度　最好时间复杂度　　　　空间复杂度　　　　　　　是否稳定　　　　　　趟数　　　　　说明

|————————————————————————————————————————————————————————————————————————————

| 插入　　　　O(n²)　　　　　　O(n²)　　　　　　O(n)　　　　　　　　　O(1)　　　　　　　　　　√（顺序移动）　 n-1

| 冒泡　　　　O(n²)　　　　　　O(n²)　　　　　　O(n)　　　　　　　　　O(1)　　　　　　　　　　√（相邻元素交换）　 [1,n-1]

| 选择　　　　O(n²)　　　　　　O(n²)　　　　　　O(n²)　　　　　　　　 O(1)　　　　　　　　　　 ×　　　　　　　　　 n-1

| 希尔　　　　O(nlgn)　　　　　O(n²)　　　　　　O(nlgn)　　　　　　　　O(1)　　　　　　　　　　×　　　　　　　　　不定　　　　对插入排序的改进

| 快速　　　　O(nlgn)　　　　　O(n²)　　　　　　O(nlgn)　　　　　　　　O(lgn)，递归导致　　　　 ×　　　　　　　　　不定　　　　对冒泡排序的改进

| 堆排序　　　O(nlgn)　　　　　O(nlgn)　　　　　O(nlgn)　　　　　　　　O(1)　　　　　　　　　　 ×　　　　　　　　　 n-1　　　　对选择排序的改进

| 二路归并　　O(nlgn)　　　　　O(nlgn)　　　　　O(nlgn)　　　　　　　　O(n)，创建辅助数组导致　 √　　　　　　　　　 ceil(lgn)　　主要用于外部排序

| 基数排序　　O(d(n+r))　　　 O(d(n+r))　　　 O(d(n+r))　　　　　　　　O(n+r)　　　　　　　　　 √　　　　　　　　　　d　　　　　（d位r进制）桶排序的扩展

| 桶排序　　　O(m+n)　　　　 O(m+n)　　　　 O(m+n)　　　　　　　　　O(m)　　　　　　　　　　 ×　　　　　　　　　　1　　　　　 m为桶大小

| 计数排序　　O(n²)　　　　　　O(n²)　　　　　　O(n²)　　　　　　　　　O(n)　　　　　　　　　　 √　　　　　　　　　 n

note：

基于相邻元素交换或顺序移动的排序算法是稳定的。

前7中是基于元素比较的排序，后两种不是。

希尔排序是对插入排序的改进、快排是对冒泡排序的改进、堆排序是对选择排序的改进。

归类

插入类：直接插入排序、希尔排序

交换类：冒泡排序、快速排序

选择类：选择排序、堆排序

归并类：二路归并

分配排序：桶排序、基数排序、计数排序、耐心排序等。

外排序

通常用多路归并排序。

其他

arrangeOf2Sets

将元素奇数组织到左边、偶数组织到右边，稳定O(n²) 或非稳定算法O(n)：

 1 //将奇数移到左边，偶数移到右边
 2 void arrangeOf2Sets(int k[],int n,int isStable)
 3 {//约定i为当前元素位置，s之前的元素为奇数（不包括s） 
 4     int i,s,tmp;
 5     s=0;
 6     if(isStable)
 7     {//稳定的排序 
 8         int t;
 9         for(i=0;i<n;i++)
10         {
11             if(k[i] & 1==1)
12             {//后移为k[i] 腾出位置 
13                 for(tmp=k[i],t=i;t>s;t--)
14                 {
15                     k[t]=k[t-1];
16                 }
17                 k[s]=tmp;
18                 ++s;
19             }
20         }
21     }
22     else
23     {//非稳定排序 
24         for(i=0;i<n;i++)
25         {
26             if(k[i] & 1==1)
27             {//直接交换 
28                 tmp=k[s];
29                 k[s]=k[i];
30                 k[i]=tmp;
31                 ++s;
32             }
33         }
34     }
35 }

arrangeOf2Sets

这其实就是快排划分的一种实现法，从前往后搜索；也可用快排划分的另一种实现法，分别从两边往中间搜索。非稳定时O(n)、稳定时O(n²)。

此外，可用插入排序的思想，从前往后，遇到奇数时就往前找插入到找到的第一个奇数后面。O(n²)

还可空间换时间，新建个数组，然后扫描输入的数组两遍分别把奇数和偶数存入新数组，然后存回原数组覆盖。O(n)　　（别学排序学傻了-_-!）

arrangeOf3Sets

O(n)复杂度将正数组织到左边，0组织到中间、负数组织到右边（与上类似），非稳定算法：

 1 void arrangeOf3Sets(int k[],int n)
 2 {//约定s之前的元素均为正数，e之后的元素均为负数，i为当前元素位置 
 3     int s,e,i,tmp;
 4     s=0;
 5     e=n-1;
 6     
 7     i=s;
 8     while(i<=e)
 9     {
10         if(k[i]>0)
11         {
12             tmp=k[i];
13             k[i]=k[s];
14             k[s]=tmp;
15             s++;
16         }
17         else if(k[i]==0)
18         {
19             i++;
20         }
21         else
22         {
23             tmp=k[i];
24             k[i]=k[e];
25             k[e]=tmp;
26             e--;
27         }
28     }
29 }

arrangeOf3Sets

随机置乱算法（洗牌算法）

与排序相反，其将一个序列打“乱”（打乱的结果可能有n!种的才算“乱”），具体可参阅：洗牌算法-MarchOn

参考资料

《数据结构与教程第二版》（北航出版社）