总结一下常见的排序算法。 排序分内排序和外排序。内排序:指在排序期间数据对象全部存放在内存的排序。外排序:指在排序期间全部对象个数太多,不能同时存放在内存,必须根据排序过程的要求,不断在内、外存之间移动的排序。内排序的方法有许多种,按所用策略不同,可归纳为五类:插入排序、选择排序、交换排序、归并排序、分配排序和计数排序。插入排序主要包括直接插入排序，折半插入排序和希尔排序两种;选择排序主要包括直接选择排序和堆排序;交换排序主要包括冒泡排序和快速排序;归并排序主要包括二路归并(常用的归并排序)和自然归并。分配排序主要包括箱排序和基数排序。计数排序就一种。
稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的。其中冒泡,插入,基数,归并属于稳定排序;选择,快速,希尔,堆属于不稳定排序。 下面是对这些常见排序算法的介绍。未来测试代码的正确性，我们采取了随机生成10个序列，然后先使用C++STL中给出的排序算法sort来得到一个正确的排序，然后再使用我们的方法进行排序得到结果，通过对比这两者的结果来验证我们代码的正确性。
测试代码如下：

复制代码

复制代码

其中参数是要测试的方法，void (_sort)(int,int)是排序方法的指针，我们所有的排序方法都写成这种形式。

1. 直接插入排序 直接插入排序(straight insertion sort)的作法是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
   　　第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
   　　直接插入排序属于稳定的排序，时间复杂性为o(n^2)，空间复杂度为O(1)。
   　　直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。 内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数 值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。（从小到大）
   值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位。插入排序类似玩牌时整理手中纸牌的过程。

代码如下：

复制代码

void insert_sort(int a[],int n){ _FUNC; for(int i=1;i<n;i++) { int t=a[i]; int j; for(j=i-1;j>=0&&a[j]>t;j--) { a[j+1]=a[j]; } a[j+1]=t; print(a,n); }}

复制代码

测试结果如下：

2. 折半插入排序
   折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
   折半插入排序算法的具体操作为：在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low],末元素设置为 a[high]，则轮比较时将待插入元素与a[m],其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新 的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成 立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。
   折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。
   代码如下：

   
   
   复制代码
   
   

   void binary_insert_sort(int a[],int n){ for(int i=1;i<n;i++){ int low=0; int high=i-1; int t=a[i]; int mid; while(low<=high){ mid=(low+high)/2; if(t<a[mid]) high=mid-1; else low=mid+1; } for(int j=i;j>mid;j--) a[j]=a[j-1]; a[low]=t; }}

   
   
   复制代码

测试结果如下：

3. 希尔排序
   希尔排序（Shell Sort）又叫做缩小增量排序（diminishing increment sort），是一种很优秀的排序法，算法本身不难理解，也很容易实现，而且它的速度很快。 基本思想：
   　　先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入 排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)， 即所有记录放在同一组中进行直接插入排序为止。
   　　该方法实质上是一种分组插入方法。插入排序（Insertion Sort）的一个重要的特点是，如果原始数据的大部分元素已经排序，那么插入排序的速度很快（因为需要移动的元素很少）。从这个事实我们可以想到，如果原 始数据只有很少元素，那么排序的速度也很快。－－希尔排序就是基于这两点对插入排序作出了改进。
   下图是希尔排序的一种实现方式：

   
   

复制代码

void shell_sort(int a[],int n){ _FUNC; int gap=n/2; bool flag=true; while(gap>1||flag) { flag=false; for(int i=0;i+gap<n;i++) if(a[i]>a[i+gap]) { swap(a[i],a[i+gap]); flag=true; } print(a,n); if(gap>1) gap/=2; }}

复制代码

测试结果如下：

另一种实现方式：

复制代码

复制代码

4. 直接选择排序
   排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个 元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么 交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。时间复杂度是O(n^2)
   代码如下：

   
   
   复制代码
   
   

   void select_sort(int a[],int n){ for(int i=0;i<n-1;i++) { int min=a[i]; int index=i; for(int j=i+1;j<n;j++) if(a[j]<min) { min=a[j]; index=j; } swap(a[i],a[index]); }}

   
   
   复制代码

这个是最基本的：从中找出最小的然后和第一个数交换，再从第2到n-1中找出最小的和第二个数交换
方法二：

复制代码

void select_sort2(int a[],int n){ _FUNC; for(int i=n-1;i>0;i--){ for(int j=0;j<i;j++) if(a[j]>a[i]) swap(a[j],a[i]); }}

复制代码

这儿感觉形式上有点类似下面的冒泡排序。
方法三：
这是对方法二的改进，判断过程中是否有交换发生，如果没有交换，说明已经完成排序了。

复制代码

void select_sort3(int a[],int n){ _FUNC; bool flag=true; for(int i=n-1;i>0&&flag;i--){ flag=false; for(int j=0;j<i;j++) if(a[j]>a[i]) swap(a[j],a[i]),flag=true; print(a,n); }}

复制代码

5. 堆排序
我们知道堆的结构是节点i的孩子为2i和2i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n /2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
堆排序的代码如下：

复制代码

复制代码

需要注意的是，如果使用数组表示堆的话，要从下标1开始，而不是从0开始。所以，这儿采用了一个技巧，让int*b=a-1;这样的话b[1]就相当于对原数组从0开始似的,即a[0]。

6. 冒泡排序
   冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不用交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改 变，所以冒泡排序是一种稳定排序算法。
   代码如下：

   
   
   复制代码
   
   

   void bubble_sort(int a[],int n){ _FUNC; for(int i=n-1;i>0;i--) for(int j=0;j<i;j++) if(a[j]>a[j+1]) swap(a[j],a[j+1]);}

   
   
   复制代码

下面的方法是加入了是否已经排好序的判断。

复制代码

复制代码

7. 快速排序
   快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然 后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

   
   
   
   

   快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交 换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11，现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和 a[j] 交换的时刻。
   下面的代码中中枢元素采用的中间的元素：

   
   
   复制代码
   
   void qsort(int a[],int l,int r){ int pvt=a[(l+r)/2]; int i=l,j=r; while(i<=j){ while(a[i]<pvt) i++; while(a[j]>pvt) j--; if(i<=j){ if(i!=j) swap(a[i],a[j]); i++; j--; } } if(j>l) qsort(a,l,j); if(i<r) qsort(a,i,r);}void quick_sort(int a[],int n){ qsort(a,0,n-1);}
   
   复制代码

8. 二路归并排序

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有 序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定 性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结 果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

复制代码

复制代码

方法二：去除递归的方法

复制代码

复制代码

9. 自然归并排序

   
   
   
   

   下面的两种形式是一样的，开始我先采用的vector来记录子序列的位置，后来发现其实采用一个数组就可以了。两种代码都放在这儿吧。
   形式1：

   
   
   复制代码
   
   void merge_sort3(int a[],int n){ vector<int> st; for(int i=0;i<n-1;i++){ if(a[i]>a[i+1]) st.push_back(i); } st.push_back(n-1);// copy(st.begin(),st.end(),ostream_iterator<int>(cout," "));// cout<<endl; int *b=new int [n]; int l,m,r; l=0; if(!st.empty()) { m=st.front(); st.erase(st.begin()); } while(!st.empty()){ r=st.front(); st.erase(st.begin()); merge(a,b,l,m,r);// print(a,n);// copy(st.begin(),st.end(),ostream_iterator<int>(cout," "));// cout<<endl; m=r; }// print(a,n); delete [] b;}
   
   复制代码

形式2：

复制代码

复制代码

10. 箱排序

    
    

View Code
上面的程序采用一个简单的Node类来描述学生的姓名和成绩，采用STL中的list来实现箱子排序。同样进行随机生成了多个实例来测试程序的正确性。而所采用的标准是STL中的multimap容器。因为这个容器可以自动根据关键字进行排序。本来想使用map容器，但是map容器不允许重复，而我们的测试实例中有很多的重复元素。测试的部分结果如下：

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

下面的一种方法是采用STL的链表容器list来实现的，这种实现比较直观：

复制代码

复制代码

另一种方法是采用多个数组来实现，不是很容易理解，这是参考的网上的代码。具体代码如下：

复制代码

复制代码

12.计数排序

复制代码

复制代码

复制代码

void rank_sort2(int a[],int n){ int *r=new int[n]; rank(a,n,r); int *u=new int[n]; for(int i=0;i<n;i++) u[r[i]]=a[i]; for(int i=0;i<n;i++) a[i]=u[i]; delete[] r; delete[] u;}

复制代码

代码如下：

复制代码

void rank_sort(int arr[],int n){ int *r=new int[n]; rank(arr,n,r); for(int i=0;i<n;i++) { while(r[i]!=i) { int t=r[i]; swap(arr[i],arr[t]); swap(r[i],r[t]); } } delete[] r;}

复制代码

排序算法复杂度：
按平均时间将排序分为四类：（1）平方阶(O(n2
))排序 　一般称为简单排序，例如直接插入、直接选择和冒泡排序；（2）线性对数阶(O(nlgn))排序 　如快速、堆和归并排序；（3）O(n1+￡
)阶排序 　￡是介于0和1之间的常数，即0<￡<1，如希尔排序；（4）线性阶(O(n))排序 　如桶、箱和基数排序。