插入排序

每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

直接插入排序

算法思想

待排序序列被人为的分为两部分：有序区和无序区。起始时刻第一个元素自成一个有序区，其他的n-1个元素组成无序区(n为待排序数据个数)。每趟循环从无序区取出一个元素，然后插入到有序区中，并且插入后仍然保持有序区的有序。这样的话，每次循环过后，有序曲的数据量加一，无序区的数据量减一，经过n-1次循环后，有序曲的数据量为n,无序区的数据量为０，排序也就完成了。

插入排序与打扑克时整理手上的牌非常类似。摸来的第 1 张牌无须整理，此后每次从桌上的牌(无序区)中摸最上面的 1 张并插入左手的牌(有序区)中正确的位置上。为了找到这个正确的位置，须自左向右(或自右向左)将摸来的牌与左手中已有的牌逐一比较。

具体实现

就将一个数组a按照从小到大排列作为例子吧！首先，取无序区的第一个数据作为待插入的数据(由于是起始时刻，这里取得是a[1])，然后找到该数据在无序区中该插入的位置，进行插入即可。这里可以充分利用有序曲的数据已经有序的特点：如果取到的待插入的数据比有序区的最右边的数据大(这里即为有序曲中最大的数据)，则该数据当前所在的位置即为它该插入的位置，也就是说，此时什么也不用做，直接取下一个数据；如果取到的待插入数据比有序曲的最右边的那个数据小，则说明该数据的插入位置在它当前位置的左边，此时就需要找到这个位置。怎么找呢？我们可以首先把有序曲的最右边的数据(即最大的那个数据)右移一位(在右移之前要先用一个辅助变量保存我们的待插入数据，以防右移时覆盖了它)，然后比较有序区右边第二个数据与待插入数据的大小，如果这个数仍然大于待插入数据，则依然将这个数右移一位。重复上述过程，直到出现了下面两种情况之一：在有序区中找到了一个小于等于待插入数据的数据或者找到头都没有找到这么一个数据。待插入数据的位置也就找到了。

代码

未引入哨兵：

#include <cstdlib>
#include <cstring>
using namespace std;
int main(void){
   int a[9]={100,5,2,3,4,65,8,9,1};
   int length=9;
   for(int i=1;i<length;i++)
   {
       //变量temp用于保存取到的数据，防止后面的移动而被覆盖
       int temp=a[i];//待插入的数据(无序区左边的第一个元素)
       int j=i-1;//有序取右边的第一个元素
       if(a[j]>temp){
           //如果a[j]<=temp则说明temp插入的位置就是当前所在的位置，直接取下一个数，进入下一轮循环.
           //这里a[j]>temp,说明temp插入的位置不在当前位置，而在更低位，下面就是要寻找这样的位置
           do{
               a[j+1]=a[j];
               j--;
           }while(a[j]>temp&&j>=0);
           //找到了头或者找到了一个小于等于temp的位置
           //找到了temp该插入的位置，插入temp
           a[j+1]=temp;
       }   
   }
    //打印输出
    for(int k=0;k<9;k++){
        cout<<a[k]<<" ";
    }
    cout<<endl;
    return 0;
}

引入哨兵:

void lnsertSort(SeqList R)  
 { //对顺序表R中的记录R[1..n]按递增序进行插入排序  
  int i，j；  
  for(i=2;i<=n；i++){ //依次插入R[2]，…，R[n]  
    if(R[i].key<R[i-1].key){//若R[i].key大于等于有序区中所有的keys，则R[i]  
                            //应在原有位置上  
      R[0]=R[i];j=i-1; //R[0]是哨兵，且是R[i]的副本  
      do{ //从右向左在有序区R[1．．i-1]中查找R[i]的插入位置  
       R[j+1]=R[j]； //将关键字大于R[i].key的记录后移  
       j-- ；  
       }while(R[0].key<R[j].key)； //有了哨兵，这里无需判断数组越界
      R[j+1]=R[0]； //R[i]插入到正确的位置上  
     }//endif  
 }//endfor
 }//InsertSort

算法分析

关于哨兵

2．哨兵的作用
算法中引进的附加记录 R[0]称监视哨或哨兵(Sentinel)。相比于未引入哨兵的代码，引入哨兵的代码中do-while循环中不需要检查每次j是否越界，这对于程序速度的提升作用巨大，特别是在数据量很大的情况之下。
这里哨兵有两个作用：

进入查找(插入位置)循环之前，它保存了 R[i]的副本，使不致于因记录后移而丢失 R[i]的内容；
它的主要作用是：在查找循环中”监视”下标变量j是否越界。一旦越界(即 j=0)，因为 R[0].key和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件”j>=1”)

效率分析

时间复杂度：O(n)-O(n^2)
空间复杂度：O(n)
辅助空间复杂度：O(1)
是一个就地排序，稳定的排序方法

希尔排序

希尔排序(Shell Sort)是插入排序的一种。因 D.L.Shell 于 1959 年提出而得名.相对直接排序有较大的改进。希尔排序又叫缩小增量排序

算法思想

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

具体实现

选择一个增量序列t1，t2，…，tk，其中ti>tj(i<j)，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子序列进行直接插入排序。仅增量因子为1时，整个序列作为一个序列来处理，序列长度即为整个序列的长度

我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 …..1} n为要排序数的个数
即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

代码

#include <iostream>
using namespace std;
void print(int a[], int n ,int i){
    cout<<i <<”:”;
    for(int j= 0; j<8; j++){
        cout<<a[j] <<” “;
    }
    cout<<endl;
}
/**
    直接插入排序的一般形式
*
    @param int dk 缩小增量，如果是直接插入排序，dk=1
*
*/
void ShellInsertSort(int a[], int n, int dk)
{
    for(int i= dk; i<n; ++i){
        if(a[i] < a[i-dk]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
            int j = i-dk;
            int x = a[i]; //复制为哨兵，即存储待排序元素
            a[i] = a[i-dk]; //首先后移一个元素
            while(x < a[j]){ //查找在有序表的插入位置
                a[j+dk] = a[j];
                j -= dk; //元素后移
            }
            a[j+dk] = x; //插入到正确位置
        }
        print(a, n,i );
    }
}
/**
    先按增量d（n/2,n为要排序数的个数进行希尔排序
*/
void shellSort(int a[], int n){
    int dk = n/2;
    while( dk >= 1 ){
        ShellInsertSort(a, n, dk);
        dk = dk/2;
    }
}
int main(){
    int a[8] = {3,1,5,7,2,4,9,6};
    //ShellInsertSort(a,8,1); //直接插入排序
    shellSort(a,8); //希尔插入排序
    print(a,8,8);
}

算法分析

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法

交换排序

两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

冒泡排序

算法思想

将被排序的记录数组 R[1..n]垂直排列，每个记录 R[i]看作是重量为 R[i].key 的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组 R：凡扫描到违反本原则的轻气泡，就使其向上”飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

具体实现

假如现在需要对长度为n的数组a从小到大排序，从右向左两两比较，遇到不符合规则的就交换。这样经过一次扫描之后，最小的数就一定到了最前面，经过第二次扫描之后第二小的数就一定到了第二的位置，以此类推，经过n-1次扫描之后，排序就完成了。

代码

改进前：

#include <iostream>
using namespace std;
int main(void){
    int a[10]={1,5,2,3,4,0,5,9,6,3};
    int length=10;
    //外循环控制扫描的次数，只需要扫描n-1次
    for(int i=1;i<length;i++){
        for(int j=length-1;j>=i;j--){//从底部扫描起，有不符合规则的则交换
            if(a[j]<a[j-1]){
                int temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
            }
        }
    }
    //打印
    for(int k=0;k<length;k++){
        cout<<a[k]<<" ";
    }
    cout<<endl;
    return 0;
}

在经过n-1次外层循环之后，我们就保证一定可以达到序列有序的目标。但是，序列也有可能在中间的某层循环中就已经达到了有序，这时后面的剩下的循环就是做无用功。一个比较极端的例子，我们需要排序的数组已经就是从小到大排列的，那么会发生什么呢？这时里层循环中的判断条件a[j]<a[j-1]永远不会成立，if语句内的内容永远不会执行。也就是说，在这种情况下，一次外层循环过后，就应该停止。我们可以基于这一点来做优化。

改进后：

#include <iostream>
using namespace std;
int main(void){
    int a[10]={1,5,2,3,4,0,5,9,6,3};
    int length=10;
    //外循环控制扫描的次数，只需要扫描n-1次
    for(int i=1;i<length;i++){
        bool flag=false;
        for(int j=length-1;j>=i;j--){//从底部扫描起，有不符合规则的则交换
            if(a[j]<a[j-1]){
                int temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
                flag=true;
            }
        }
        if(!flag){
            //说明此时数据已经有序，不必继续循环了。
            break;
        }
    }

    //打印
    for(int k=0;k<length;k++){
        cout<<a[k]<<" ";
    }
    cout<<endl;
    return 0;
}

算法分析

算法的最好时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：
Cmin=n-1
Mmin=0。
冒泡排序最好的时间复杂度为 O(n)。
算法的最坏时间复杂度
若初始文件是反序的，需要进行 n-1 趟排序。每趟排序要进行 n-i 次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
Cmax=n(n-1)/2=O(n^2)
Mmax=3n(n-1)/2=O(n^2)
冒泡排序的最坏时间复杂度为 O(n^2)。
算法的平均时间复杂度为 O(n2)
虽然冒泡排序不一定要进行 n-1 趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。
算法稳定性
冒泡排序是就地排序，且它是稳定的。

快速排序

快速排序是 C.R.A.Hoare 于 1962 年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

基本思想

就以将序列按从小到大排列为例，任意取序列中的某一元素为基准元素，然后把比基准元素小的元素全放到基准元素的左边，把比基准元素大的元素全放到基准元素的右边。这样基准元素就归位了。基准元素左右两边分别得到了两个新的无序序列，我们可以对这两个无序序列做同样的操作，就这样递归下去，直到所有的元素都归位为止。

具体实现

qs1
假如我们以将上图的序列按照从小到大排列为例。由于基准元素的选取具有随机性，我在这里每次就直接以序列最左边的那个数作为基准元素(这里的基准元素就是６)。我们设定两个哨兵：ｉ和ｊ，分别指向序列的第一个元素和最后一个元素。然后将j向左移动(一定是ｊ先开始移动)，去找一个比６小的数，找到之后就停下。然后让ｉ向右移动，找到一个比６大的元素，找到之后也停下来。这时两个哨兵就可以交换两者的元素了。如下图：
qs1

交换后：
qs1

同样的这时仍然是j先开始向左移动，去找比６小的元素，找到后停下来。i开始向右移动，找到一个比6大的元素。然后交换。
qs1
交换后：
qs1

重复上面的j,i移动过程，但是这一次好像出现了一定小问题，i和j碰头了！
qs1
这时就需要把我们的基准元素和当前i,j共同指向的元素交换位置即可。
qs1
交换后：
qs1
至此，我们的基准元素就归位了，基准元素的两边的又得到了两个新的无序序列，我们只需要对他们使用同样的方法处理即可。

代码

快速排序可以使用两种方式实现，分别是递归法和迭代法。

递归法

#include <stdio.h>
int a[101],n;//定义全局变量，这两个变量需要在子函数中使用
void quicksort(int left,int right)
{
    int i,j,t,temp;
    if(left>right)
       return;
                                    
    temp=a[left]; //temp中存的就是基准数
    i=left;
    j=right;
    while(i!=j)
    {
                   //顺序很重要，要先从右边开始找
                   while(a[j]>=temp && i<j)
                            j--;
                   //再找右边的
                   while(a[i]<=temp && i<j)
                            i++;
                   //交换两个数在数组中的位置
                   if(i<j)
                   {
                            t=a[i];
                            a[i]=a[j];
                            a[j]=t;
                   }
    }
    //最终将基准数归位
    a[left]=a[i];
    a[i]=temp;
                                 
    quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程
    quicksort(i+1,right);//继续处理右边的 ，这里是一个递归的过程
}
int main()
{
    int i,j,t;
    //读入数据
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    quicksort(1,n); //快速排序调用
                                 
    //输出排序后的结果
    for(i=1;i<=n;i++)
        printf("%d ",a[i]);
    return 0;
}

迭代法

#include <stdio.h>
struct node
{
    int min;
    int max;
};
void quickSort(int min, int max, int a[])
{
    int key = a[min];
    int i = min;
    int j = max;
    int temp;
    struct node myStack[100];
    int top = 0;
    myStack[top].min = min;
    myStack[top].max = max;
    while (top > -1)
    {
        //min max 记录当前处理的这个区间的左极限和有极限
        i = min = myStack[top].min;
        j = max = myStack[top].max;
        top--;
        key = a[min];
        while (i < j)
        {
            while ((i < j) && (key <= a[j]))
            {
                j--;
            }
            if (i < j)
            {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                i++;
            }
            while ((i < j) && (key >= a[i]))
            {
                i++;
            }
            if (i < j)
            {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                j--;
            }
        } //处理一次即将比绑定值小的全部放左边 比绑定值大的放右边
        if (min < i - 1)
        {
            top++;
            myStack[top].min = min;
            myStack[top].max = i - 1;
        }
        if (max > i + 1)
        {
            top++;
            myStack[top].min = i + 1;
            myStack[top].max = max;
        }
    }
}
int main()
{
    int i;
    int a[14] = {20,2,52,23,12,14,16,25,10,2,5,9,7,3};
    for (i = 0; i < 14; i++)
        printf(" %d ", a[i]);
    printf("\n");
    quickSort(0, 13, a);
    for (i = 0; i < 14; i++)
        printf(" %d ", a[i]);
    printf("\n");
    return 0;
}

算法分析

在数据量很大的情况下，快速排序是在时间和空间综合方面做的非常好的排序方法之一。
最坏时间复杂度：O(n^2)
最好时间复杂度：O(nlogn)
快速排序是不稳定的。

选择排序

直接选择排序

基本思想

依然以将序列从小到大排列为例，选择排序的思想是这样的：既然排序之后第一位一定是放着最小的元素，第二位是放着第二小的元素……那么我们就可以在序列中先找到最小的元素放在第一位，然后从第二位开始找余下的数据的最小值并且放在第二位，然后从第三位找余下的数据的最小值并且放在第三位，以此类推，直达排序完成。

具体实现

以数组a为例，外层循环从a[0]开始，里层循环从a[1]开始，如果a[1]小于a[0]则交换之，接着分别比较a[2],a[3],a[4]……和a[0]的大小，谁更小谁就去坐a[0]的位置。就这样经过一轮的循环，就选择出来了最小的元素放在了a[0]的位置，接下来外层循环从a[1]开始(看看剩下的元素中谁最小，谁就可以坐a[1]这个位置)，里层循环从a[2]开始，依次类推。

代码

//Select Sort
#include <iostream>
using namespace std;
int main (void){
    int a[10]={8,1,5,3,4,6,27,5,2,9};
    for(int i=0;i<10;i++)
    {
        for(int j=i+1;j<10;j++)
        {
            
            if(a[i]>a[j]){
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }

    for(int k=0;k<10;k++){
        cout<<a[k]<<" ";
    }
    cout<<endl;
    return 0;
}

直接选择排序的改进

简单选择排序的改进——二元选择排序
简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：

void SelectSort(int r[],int n) {
    int i ,j , min ,max, tmp;
    for (i=1 ;i <= n/2;i++) {
        // 做不超过n/2趟选择排序
        min = i; max = i ; //分别记录最大和最小关键字记录位置
        for (j= i+1; j<= n-i; j++){
            if (r[j] > r[max]) {
                max = j ;
            }
            if (r[j]< r[min]) {
                min = j ;
            }
        }
    //该交换操作还可分情况讨论以提高效率
    tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;
    tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;
    }
}

算法分析

关键字比较次数
无论文件初始状态如何，在第 i 趟排序中选出最小关键字的记录，需做 n-i 次比较，因此，总的比较次数为： n(n-1)/2=O(n2)
记录的移动次数
当初始文件为正序时，移动次数为 0
文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值 3(n-1)。
直接选择排序的平均时间复杂度为 O(n2)。
直接选择排序是一个就地排序
稳定性分析
直接选择排序是不稳定的

堆排序

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

算法思想

堆的定义如下：具有n个元素的序列（k1,k2,…,kn),当且仅当满足下面的条件时称之为堆。
堆定义
由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆)或最大项(大顶堆)。
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：
(a）大顶堆序列：（96, 83,27,38,11,09)
(b) 小顶堆序列：（12，36，24，85，47，30，53，91）

heap3
初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。
因此，实现堆排序需解决两个问题：

如何将n 个待排序的数建成堆；
输出堆顶元素后，怎样调整剩余n-1个元素，使其成为一个新堆。

首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程。
调整小顶堆的方法：
1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。
2）将根结点与左、右子树中较小元素的进行交换。
3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法（2）.
4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法（2）.
5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。
称这个自根结点到叶子结点的调整过程为筛选。如图：
heap

再讨论对n 个元素初始建堆的过程。
建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。
1）n 个结点的完全二叉树，则最后一个结点是第个结点的子树。
2）筛选从第个结点为根的子树开始，该子树成为堆。
3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。
如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）

detail
算法的实现：
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

代码

#include <iostream>
using namespace std;
void print(int a[], int n){
    for(int j= 0; j<n; j++){
        cout<<a[j] <<” “;
    }
    cout<<endl;
}
/**
    已知H[s…m]除了H[s] 外均满足堆的定义
    调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,
*
    @param H是待调整的堆数组
    @param s是待调整的数组元素的位置
    @param length是数组的长度
*
*/
void HeapAdjust(int H[],int s, int length)
{
    int tmp = H[s];
    int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
    while (child < length) {
        if(child+1 <length && H[child]<H[child+1]){ // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
            ++child ;
        }
        if(H[s]<H[child]) { // 如果较大的子结点大于父结点
            H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点
            s = child; // 重新设置s ,即待调整的下一个结点的位置
            child = 2*s+1;
        } 
        else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
            break;
        }
        H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
    }
    print(H,length);
}
/**
    初始堆进行调整
    将H[0..length-1]建成堆
    调整完之后第一个元素是序列的最小的元素
*/
void BuildingHeap(int H[], int length)
{
    //最后一个有孩子的节点的位置 i= (length -1) / 2
    for (int i = (length -1) / 2 ; i >= 0; –i)
        HeapAdjust(H,i,length);
}
/**
    堆排序算法
*/
void HeapSort(int H[],int length)
{
    //初始堆
    BuildingHeap(H, length);
    //从最后一个元素开始对序列进行调整
    for (int i = length - 1; i > 0; –i)
    {
        //交换堆顶元素H[0]和堆中最后一个元素
        int temp = H[i]; 
        H[i] = H[0];
        H[0] = temp;
        //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
        HeapAdjust(H,0,i);
    }
}

int main(void){
    int H[10] = {3,1,5,7,2,4,9,6,10,8};
    cout<<”初始值：”;
    print(H,10);
    HeapSort(H,10);
    //selectSort(a, 8);
    cout<<”结果：”;
    print(H,10);
}

算法分析

设树深度为k,(k=(log₂n)+1)。从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式：
2[(log₂(n-1))+(log₂(n-2))+……+log₂2] < 2nlog₂n
而建堆时的比较次数不超过4n次，因此堆排序最坏情况下，时间复杂度也为：O(nlogn)

归并排序

算法思想

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序示例：
mergesort

具体实现

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为n-i+1、n-m。

j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束
//选取r[i]和r[j]较小的存入辅助数组rf
如果r[i]<r[j]，rf[k]=r[i]； i++； k++；转⑵
否则，rf[k]=r[j]； j++； k++；转⑵
//将尚未处理完的子表中元素存入rf
如果i<=m,将r[i…m]存入rf[k…n] //前一子表非空
如果j<=n,将r[j…n] 存入rf[k…n] //后一子表非空
合并结束。

 //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
 void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
{  
     int j,k;  
     for(j=m+1,k=i; i<=m && j <=n ; ++k){  
         if(r[j] < r[i]) 
            rf[k] = r[j++];  
         else 
            rf[k] = r[i++];  
     }  
     while(i <= m)  rf[k++] = r[i++];  
     while(j <= n)  rf[k++] = r[j++];  
}

代码

归并的迭代算法

1个元素的表总是有序的。所以对n个元素的待排序列，每个元素可看成1个有序子表。对子表两两合并生成n/2个子表，所得子表除最后一个子表长度可能为1外，其余子表长度均为2。再进行两两合并，直到生成n个元素按关键码有序的表。

#include <iostream>
using namespace std;
void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  
  
//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
{  
    int j,k;  
    for(j=m+1,k=i; i<=m && j <=n ; ++k){  
        if(r[j] < r[i]) rf[k] = r[j++];  
        else rf[k] = r[i++];  
    }  
    while(i <= m)  rf[k++] = r[i++];  
    while(j <= n)  rf[k++] = r[j++];  
    print(rf,n+1);  
}  
  
void MergeSort(ElemType *r, ElemType *rf, int lenght)  
{   
    int len = 1;  
    ElemType *q = r ;  
    ElemType *tmp ;  
    while(len < lenght) {  
        int s = len;  
        len = 2 * s ;  
        int i = 0;  
        while(i+ len <lenght){  
            Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并  
            i = i+ len;  
        }  
        if(i + s < lenght){  
            Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并  
        }  
        tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf  
    }  
}  
  
int main(){  
    int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    int b[10];  
    MergeSort(a, b, 10);  
    print(b,10);  
    cout<<"结果：";  
    print(a,10);  
   }

两路归并的递归算法

void MSort(ElemType *r, ElemType *rf,int s, int t)  
{   
    ElemType *rf2;  
    if(s==t)
        r[s] = rf[s];  
    else  
    {   
        int m=(s+t)/2;          //平分p表 
        MSort(r, rf2, s, m);        //递归地将p[s…m]归并为有序的p2[s…m]  
        MSort(r, rf2, m+1, t);      //递归地将p[m+1…t]归并为有序的p2[m+1…t]  
        Merge(rf2, rf, s, m+1,t);   //将p2[s…m]和p2[m+1…t]归并到p1[s…t]  
    }  
}  
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  
{   //对顺序表*p 作归并排序
    MSort(r, rf,0, n-1);  
}

分配排序

分配排序的基本思想：排序过程无须比较关键字，而是通过”分配”和”收集”过程来实现排序.它们的时间复杂度可达到线性阶：O(n)。

桶排序

算法思想

设置若干个桶，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。这样就可以实现不经过比较，而经过分配和收集就排序成功。

例如：要将一副混洗的 52 张扑克牌按点数 A<2<…<J<Q<K 排序，需设置 13 个”箱子”，排序时依次将每张牌按点数放入相应的箱子里，然后依次将这些箱子首尾相接，就得到了按点数递增序排列的一副牌。
又例如要对大小为[1..1000]范围内的n个整数A[1..n]排序：

首先,可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储(10..20]的整数，……集合B[i]存储((i-1)*10, i*10]的整数，i=1,2,..100。总共有100个桶。
然后，对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。
最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。

假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果对每个桶中的数字采用快速排序，那么整个算法的复杂度是
O(n+m*n/m*log(n/m))=O(n+nlogn-nlogm)
从上式看出，当m接近n的时候，桶排序复杂度接近O(n)
当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。

前面说的几大排序算法,大部分时间复杂度都是O(n^2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是：

首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。
其次待排序的元素都要在一定的范围内等等。

桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较，但前提是要知道待排序列的一些具体情况。桶子的类型一般设为链表为宜。

基数排序

多关键码排序实例:

扑克牌中52张牌，可按花色和面值分成两个字段，其大小关系为：
花色：梅花< 方块< 红心< 黑心
面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A
若对扑克牌按花色、面值进行升序排序，得到如下序列：

即两张牌，若花色不同，不论面值怎样，花色低的那张牌小于花色高的，只有在同花色情况下，大小关系才由面值的大小确定。这就是多关键码排序。

为得到排序结果，我们讨论两种排序方法。

方法1：先对花色排序，将其分为4 个组，即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序，最后，将4 个组连接起来即可。
方法2：先按13个面值给出13个编号组(2 号，3 号，…，A 号),将牌按面值依次放入对应的编号组,分成13堆。再按花色给出4个编号组(梅花、方块、红心、黑心)，将2号组中牌取出分别放入对应花色组,再将3号组中牌取出分别放入对应花色组，……，这样，4个花色组中均按面值有序，然后，将4个花色组依次连接起来即可。

设n个元素的待排序列包含d个关键码{k1，k2，…，kd}，则称序列对关键码{k1，k2，…，kd}有序是指：对于序列中任两个记录r[i]和rj都满足下列有序关系：
(K_i¹,K_i²,……,K_i^d) < (K_j¹,K_j²,……,K_i^d)
其中k1 称为最主位关键码，kd称为最次位关键码。

两种多关键码排序方法：

多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：

最高位优先(Most Significant Digit first)法，简称MSD法：

1）先按k1 排序分组，将序列分成若干子序列，同一组序列的记录中，关键码k1 相等。
2）再对各组按k2 排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd 对各子组排序后。
3）再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

最低位优先(Least Significant Digit first)法，简称LSD法：

1) 先从kd 开始排序，再对kd-1进行排序，依次重复，直到按k1排序分组分成最小的子序列后。
2) 最后将各个子序列连接起来，便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。

基于LSD方法的链式基数排序的基本思想

“多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采用“分配 -收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按红、黑、方、花的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。

基数排序:
是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
算法实现：

Void RadixSort(Node L[],length,maxradix)  
{  
   int m,n,k,lsp;  
   k=1;m=1;  
   int temp[10][length-1];  
   Empty(temp); //清空临时空间  
   while(k<maxradix) //遍历所有关键字  
   {  
     for(int i=0;i<length;i++) //分配过程  
     {  
        if(L[i]<m)  
           Temp[0][n]=L[i];  
        else  
           Lsp=(L[i]/m)%10; //确定关键字  
        Temp[lsp][n]=L[i];  
        n++;  
    }  
    CollectElement(L,Temp); //收集  
    n=0;  
    m=m*10;  
    k++;  
  }  
}

总结

各种排序的稳定性，时间复杂度和空间复杂度总结：
sum

相关概念

排序的分类

按是否涉及数据的内外存交换分

在内排序基础上按策略分

排序的稳定性

插入排序

直接插入排序

算法思想

具体实现

代码

算法分析

关于哨兵

效率分析

希尔排序

算法思想

具体实现

代码

算法分析

交换排序

冒泡排序

算法思想

具体实现

代码

算法分析

快速排序

基本思想

具体实现

代码

递归法

迭代法

算法分析

选择排序

直接选择排序

基本思想

具体实现

代码

直接选择排序的改进

算法分析

堆排序

算法思想

代码

算法分析

归并排序

算法思想

具体实现

代码

归并的迭代算法

两路归并的递归算法

分配排序

桶排序

算法思想

基数排序

多关键码排序实例:

两种多关键码排序方法：

最高位优先(Most Significant Digit first)法，简称MSD法：

最低位优先(Least Significant Digit first)法，简称LSD法：

基于LSD方法的链式基数排序的基本思想

总结