常用的几种排序算法
排序是什么就不用介绍了，直接进入正题吧，并且我们的排序只是讨论基于比较的排序（>=<有定义），只讨论内部排序，什么是内部排序呢？内部排序是指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列，并且没有任何一种排序是在任何情况下都表现得最好的，下面我们介绍简单排序当中的冒泡排序和插入排序。
（1）冒泡排序
通过每次交换两个相邻的元素，每一次排序将最大或者最小的元素移到应该放的位置，接下来下一次循环将第二大或者第二小的元素放在应该放的位置，伪代码如下所示：
void Bubble_Sort( ElementType A[], int N )
{ for ( P=N-1; P>=0; P-- )
{
flag = 0;
for( i=0; i<P; i++ )
{ /* 一趟冒泡 */
if ( A[i] > A[i+1] ) {
Swap(A[i], A[i+1]);
flag = 1; /* 标识发生了交换 */
}
}
if ( flag==0 ) break; /* 全程无交换时，代表元素已经有序了，直接退出排序*/
}
}
最好情况下它的时间复杂度为O（N），在待排序元素是顺序的情况下，最坏情况下它的时间复杂度是O（N^2），是在待排序元素是逆序的情况下，并且它是一个稳定排序，因为当A[i]和A[i+1]两者相等时，是不需要交换的，所以保证了原来的相对顺序。
（2）插入排序
插入排序就类似于一个取扑克牌的过程，首先一个具有N个未排序的数组A是未排序部分，取出其第一个元素A[0],这样A[0]就是一个有序部分，A[1]到A[N-1]就是剩下的未排序的部分，然后取出未排序部分的第一个元素A[1]往已排序部分加入，从已排序部分的最后一个元素开始比较，如果该元素大于此元素，继续和已排序部分的前一个元素比较，直到找到第一个小于待插入元素的已排序部分元素，或者已排序部分被遍历完了，在此位置插入该元素，直到将所有的未排序部分的元素插入已排序部分，排序结束，伪代码如下所示：
void Insertion_Sort( ElementType A[], int N )
{ for ( P=1; P<N; P++ ) {
Tmp = A[P]; /* 摸下一张牌 */
for ( i=P; i>0 && A[i-1]>Tmp; i-- )
A[i] = A[i-1]; /* 移出空位 */
A[i] = Tmp; /* 新牌落位 */
}
}
最好情况下它的时间复杂度为O（N），在待排序元素是顺序的情况下，最坏情况下它的时间复杂度是O（N^2），是在待排序元素是逆序的情况下，并且它是一个稳定排序，因为这条语句A[i-1]>Tmp，可以看出，只有在tmp等于此元素的时候，会停止往前移动，所以相对位置并没有改变。
针对上面两个排序算法，到底需要多少次元素交换才能完成排序呢？两者需要的次数是相等的，因为数组之所以无序是因为存在逆序对，交换两个相邻元素正好可以消去1个逆序对，而上述两个简单排序都只是交换两个相邻的元素，所以两者交换的次数是相等的，插入排序在序列基本有序的情况下是非常简单和高效的，更为准确的来说，插入排序的时间复杂度为O（N+I），其中N是元素个数，I是数组中的逆序对。
定理：
2.1任意N个不同元素所组成的序列平均具有N（N-1）/4个逆序对。
2.2任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为佘格马（N^2）。
通过上述两个定理，我们知道如果你想提高一个排序算法的效率，那么你必须在一次交换中不止消去一个逆序对，那么你就需要每次交换相隔比较远的2个元素，接下来介绍一个这种排序。
（3）希尔排序（Donald Shell）
定义一个增量序列D^m>D^(m-1)>…..>D^1=1,对每个D^k进行一个K间隔排序（K=M，M-1，….1），希尔排序的基础之一就是D^k间隔排序后有序的数组，在执行D^(k-1)间隔排序后，它依然是一个D^k间隔有序的。最原始的希尔排序中，选择的的增量序列是D^m=N/2,D^k=D^(k+1)/2,换言之就是假设有一个N个元素的未排序数组A，第一次选择做一个N/2长度的排序，就是说在数组的有效元素范围内，将A[0]与A[0+N/2]进行比较，将A[1]与A[1+N/2]进行比较，直到最后比到最后一个有效元素为止，第二次选择的长度为N/4进行比较，同理，将A[0]与A[0+N/4]进行比较，将A[1]与A[1+N/4]进行比较，直到最后比到最后一个有效元素为止，一直比到长度为1，也就是两个相邻元素比较，伪代码如下：
void Shell_sort( ElementType A[], int N )
{ for ( D=N/2; D>0; D/=2 ) { /* 希尔增量序列 */
for ( P=D; P<N; P++ ) { /* 插入排序 */
Tmp = A[P];
for ( i=P; i>=D && A[i-D]>Tmp; i-=D )
A[i] = A[iD];
A[i] = Tmp;
}
}
}
这种排序算法在最坏的情况下，依然是一个N^2的复杂度，在当增量元素不互质的情况下，小增量可能根本就不起作用，只是在浪费比较时间而已，所以对于希尔排序来说，很重要的一个是选择合适的增量序列，提供两个很常用的增量序列：
3.1 Hibbard增量序列
这个增量序列是按照D^k=2^k-1来进行计算的，这样保证了相邻的两个增量序列是互质的，这个增量序列在最坏的情况下T=O（N^(3/2)），在平均情况下目前只有一个猜想（2014年）是T=O（N^(5/4)）.
3.2 Sedgewick增量序列
这个序列是｛1，5，19，41，109，….｝，它是94^i-92^i+1或4^i-3*2^i+1,这个增量序列在最坏的情况下猜想为T=O（N^(4/3)），在平均情况下目前一个猜想（2014年）是T=O（N^(7/6)）.（2014年）
以Sedgewick增量序列为例写一个希尔排序，代码如下：
void ShellSort( ElementType A[], int N )
{ /* 希尔排序 - 用Sedgewick增量序列 */
int Si, D, P, i;
ElementType Tmp;
/* 这里只列出一小部分增量 */
int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};
for ( Si=0; Sedgewick[Si]>=N; Si++ )
; /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */
for ( D=Sedgewick[Si]; D>0; D=Sedgewick[++Si] )
for ( P=D; P<N; P++ ) { /* 插入排序*/
Tmp = A[P];
for ( i=P; i>=D && A[i-D]>Tmp; i-=D )
A[i] = A[i-D];
A[i] = Tmp;
}
}
（4）堆排序
顾名思义了，堆排序就是利用了最大堆或者最小堆进行排序的一种排序算法了，它是结合了选择排序和堆的特性的一种排序算法，选择排序的伪代码如下：
void Selection_Sort ( ElementType A[], int N )
{ for ( i = 0; i < N; i ++ ) {
MinPosition = ScanForMin( A, i, N–1 );
/* 从A[i]到A[N–1]中找最小元，并将其位置赋给MinPosition */
Swap( A[i], A[MinPosition] );
/* 将未排序部分的最小元换到有序部分的最后位置 */
}
}
如果只是用暴力的算法每次找出A中的最小元素，那么需要遍历整个数组，然后外层还有一个循环，所以整个排序算法的时间复杂度是N^2级别的，排序N个元素，肯定要将N个元素都看一遍，所以只能从找到最小元素这里做出改进，那如何找到最值元素呢，这里就用到了堆这种数据结构，代码如下所示:
void Heap_Sort ( ElementType A[], int N )
{ BuildHeap(A); /* O(N) */
for ( i=0; i<N; i++ )
TmpA[i] = DeleteMin(A); /* O(logN) */
for ( i=0; i<N; i++ ) /* O(N) */
A[i] = TmpA[i];
}
已知调整堆时的时间复杂度是logN，此数列循环了N次，所以时间复杂度是N*logN，但是这个算法如果是最小堆，那么它需要额外的O（N）的空间用来存储堆，并且复制元素也需要一定的时间，那么可以就在数组提供的空间内实现一个堆排序，不占用额外空间吗？可以的，只需要将数组设置成最大堆结构，每次把A[0]这个元素弄到A[N-1]的位置，然后最大堆长度减一，调整堆，接下来再把A[0]放到A[N-2]这个位置，代码如下所示：
void Heap_Sort ( ElementType A[], int N )
{ for ( i=N/2-1; i>=0; i-- )/* BuildHeap */
PercDown( A, i, N );
for ( i=N-1; i>0; i-- ) {
Swap( &A[0], &A[i] ); /* DeleteMax */
PercDown( A, 0, i );
}
}
堆排序处理N哥不同元素的随机排列的平均比较次数是2*NlogN-O（NloglogN），虽然堆排序给出了最佳平均时间复杂度，但是它的实际效果不如用了Sedgewick增量序列的希尔排序，完整c代码如下：
void Swap( ElementType *a, ElementType *b )
{
ElementType t = *a; *a = *b; *b = t;
}
void PercDown( ElementType A[], int p, int N )
{ /* 改编自上一章学习的堆的PercDown( MaxHeap H, int p ) */
/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
int Parent, Child;
ElementType X;
X = A[p]; /* 取出根结点存放的值 */
for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
Child = Parent * 2 + 1;
if( (Child!=N-1) && (A[Child]<A[Child+1]) )
Child++; /* Child指向左右子结点的较大者 */
if( X >= A[Child] ) break; /* 找到了合适位置 */
else /* 下滤X */
A[Parent] = A[Child];
}
A[Parent] = X;
}
void HeapSort( ElementType A[], int N )
{ /* 堆排序 */
int i;
for ( i=N/2-1; i>=0; i-- )/* 建立最大堆 *，已知数组从下标0开始的，那么最后一个有子节点的数组元素下标为N/2-1/
PercDown( A, i, N );
for ( i=N-1; i>0; i-- ) {
/* 删除最大堆顶 */
Swap( &A[0], &A[i] );
PercDown( A, 0, i );
}
}
(5)归并排序
归并排序的核心思想如下图所示：
由上图可知，需要得到一个左右两边分别有序的子数组，那如何才能得到一个左右分别有序的子数组呢，再把这个方法用到左右两边的子数组中，这样就变成了4个子数组，同理，还是相同的问题，如何让这四个子数组有序呢，接着划分，知道子数组被划分成为了只有一个元素的子数组，那么只有一个元素的子数组就自然是有序得了，所以可以尝试着写出如下的归并过程伪代码：
/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置 */
void Merge( ElementType A[], ElementType TmpA[],int L, int R, int RightEnd )
{ LeftEnd = R - 1; /* 左边终点位置。假设左右两列挨着 */
Tmp = L; /* 存放结果的数组的初始位置 */
NumElements = RightEnd - L + 1;
while( L <= LeftEnd && R <= RightEnd ) {
if ( A[L] <= A[R] ) TmpA[Tmp++] = A[L++];
else TmpA[Tmp++] = A[R++];
}
while( L <= LeftEnd ) /* 直接复制左边剩下的 */
TmpA[Tmp++] = A[L++];
while( R <= RightEnd ) /*直接复制右边剩下的 */
TmpA[Tmp++] = A[R++];
for( i = 0; i < NumElements; i++, RightEnd -- )
A[RightEnd] = TmpA[RightEnd];//将排序结果返回原数组。
}
void MSort( ElementType A[], ElementType TmpA[],int L, int RightEnd )//L是左边起始点，RightEnd是右边结束点
{ int Center;
if ( L < RightEnd ) {
Center = ( L + RightEnd ) / 2;//将待排序数组分为左右两部分
MSort( A, TmpA, L, Center );//左边分而治之
MSort( A, TmpA, Center+1, RightEnd );//右边同理
Merge( A, TmpA, L, Center+1, RightEnd );//将两边合并起来
}
}
显然这是T（N）=T（N/2）+T(N/2)+O(N)的算法，已经推理过，这样的算法的时间复杂度为O（NlogN），推理过程如下图，并且由上归并过程可知，当左右相等时，优先把左边归并进去，所以是一个稳定的排序算法。
上述算法利用了递归，试着将此递归修改为循环，这样提高程序的运行效率，循环算法就是将递归算法的过程反着来，非递归算法要注意几个细节，一个是如何确定此时的排序数组是在辅助空间内还是在原来的数组中，还有就是奇数时，数组怎么进行归并，下面将两种算法的c代码附上：
/* 归并排序 - 递归实现 */
/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
int LeftEnd, NumElements, Tmp;
int i;
LeftEnd = R - 1; /* 左边终点位置 */
Tmp = L; /* 有序序列的起始位置 */
NumElements = RightEnd - L + 1;
while( L <= LeftEnd && R <= RightEnd ) {
if ( A[L] <= A[R] )
TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
else
TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
}
while( L <= LeftEnd )
TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
while( R <= RightEnd )
TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
for( i = 0; i < NumElements; i++, RightEnd -- )
A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}
void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{ /* 核心递归排序函数 */
int Center;
if ( L < RightEnd ) {
Center = (L+RightEnd) / 2;
Msort( A, TmpA, L, Center ); /* 递归解决左边 */
Msort( A, TmpA, Center+1, RightEnd ); /* 递归解决右边 */
Merge( A, TmpA, L, Center+1, RightEnd ); /* 合并两段有序序列 */
}
}
void MergeSort( ElementType A[], int N )
{ /* 归并排序 */
ElementType *TmpA;
TmpA = (ElementType *)malloc(N*sizeof(ElementType));
if ( TmpA != NULL ) {
Msort( A, TmpA, 0, N-1 );
free( TmpA );
}
else printf( "空间不足" );
}
/* 归并排序 - 循环实现 */
/* 这里Merge函数在递归版本中给出 */
/* length = 当前有序子列的长度*/
#include<stdio.h>
void Merge( int A[], int TmpA[], int L, int R, int RightEnd )
{ /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
int LeftEnd, NumElements, Tmp;
int i;
LeftEnd = R - 1; /* 左边终点位置 */
Tmp = L; /* 有序序列的起始位置 */
NumElements = RightEnd - L + 1;
while( L <= LeftEnd && R <= RightEnd ) {
if ( A[L] <= A[R] )
TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
else
TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
}
while( L <= LeftEnd )
TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
while( R <= RightEnd )
TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
for( i = 0; i < NumElements; i++, RightEnd -- )
A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}
void Merge_pass( int A[], int TmpA[], int N, int length )
{ /* 两两归并相邻有序子列 */
int i, j;
for ( i=0; i <= N-2*length; i += 2*length )
Merge( A, TmpA, i, i+length, i+2*length-1 );
if ( i+length < N ) /* 归并最后2个子列，保证实现每个子数组内有序*/
Merge( A, TmpA, i, i+length, N-1);
else /* 最后只剩1个子列*/
for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}
void Merge_Sort( int A[], int N )
{
int length;
int *TmpA;
length = 1; /* 初始化子序列长度*/
TmpA = malloc( N * sizeof( int ) );
if ( TmpA != NULL ) {
while( length < N ) {
Merge_pass( A, TmpA, N, length );
length *= 2;
Merge_pass( TmpA, A, N, length );
length *= 2;
}
free( TmpA );
}
else printf( "空间不足" );
}
int main(void) {
int A[7]={3,2,5,7,6,8,1};
int N=7;
Merge_Sort(A,N);
for(int i=0;i<N;i++)
printf("%d ",A[i]);
printf("\n");
return 0;
}
运行结果如下：
（6）快速排序
快速排序的思想和归并有点类似，就是一样的分而治之的思想，选择一个元素，将比它大的放在左边，比它小的放在右边，这样该元素的位置在数组中就肯定正确了，不需要移动它了，这也是快速排序之所以很快的一个原因，比如插入排序，进入的数组之后可能还要面临多次移动，不像快排一步到位。由此算法的性质，可知最佳情况是每次选择的这个元素都是中间的元素，这样就是一个明显的NlogN的时间复杂度，伪代码情况如下所示：
void Quicksort( ElementType A[], int N )
{ if ( N < 2 ) return;
pivot = 从A[]中选一个主元;
将S = { A[] \ pivot } 分成2个独立子集:
A1={ a属于S | a <= pivot } 和
A2={ a属于S | a >= pivot };
A[] = Quicksort(A1,N1)并上{pivot}并上Quicksort(A2,N2);
}
所以pivot的选择是最重要的一步，如果选择每次都是最差的情况，那么它会退化到N^2的时间复杂度，那什么是最差情况呢，如下图所示：
那如何选取主员呢，一个办法是用rand（）函数，这样随机起来可以避免每次选到最差的元素，但是rand函数也需要时间，所以另外一个办法是取头、中、尾的中位数，下面就是一个选择中位数的函数。
ElementType Median3( ElementType A[], int Left, int Right )
{ int Center = ( Left + Right ) / 2;
if ( A[ Left ] > A[ Center ] )
Swap( &A[ Left ], &A[ Center ] );
if ( A[ Left ] > A[ Right ] )
Swap( &A[ Left ], &A[ Right ] );
if ( A[ Center ] > A[ Right ] )
Swap( &A[ Center ], &A[ Right ] );
/* A[ Left ] <= A[ Center ] <= A[ Right ] */
Swap( &A[ Center ], &A[ Right-1 ] ); /* 将pivot藏到右边，节约一次比较，反正都比过了 */
/* 只需要考虑 A[ Left+1 ] … A[ Right–2 ] */
return A[ Right-1 ]; /* 返回 pivot */
}
但是，假如我们刚好有元素等于选定的元素怎么办，一是不理它，继续移动指针，二是停下来等待交换，两种方法最后的排序结果都是正确的，但是要选择第二种，为什么呢？因为交换之后，会让下一次选取的元素更加接近中间的元素值，这样能够更逼近NlogN，原因就是假设有一个全是1的数组，开始比较的时候，发现第一个和最后一个都等于1，于是交换，然后再比较，再交换，最后进行了一堆无用的交换，但是最后i和j的位置基本是在数组中间的，而如果遇到之后不交换，直接跳过，那先从后面开始寻找小于选定元素的元素，直到找到待排序数组的头部都找不到，但是此时i和j的位置就在很左边了，很有可能退化成一个N^2的算法，有没有解决的方法呢，当然有了，在设置一个左边结束坐标，一个右边结束坐标，当相等时可以将该元素放在选定元素的身边，这样就相当于替所以值相等的选定元素找到了该待的位置，还减少了下一步的计算量。
快速排序的速度确实很快，但是在小规模的排序上，例如（1到100），因为存在递归，所以它的速度可能还比不上插入排序，所以当递归数据的规模很小的时候，应当停止递归，直接调用简单排序，例如下一个伪代码所示：
void Quicksort( ElementType A[], int Left, int Right )
{ if ( Cutoff <= Right-Left ) {
Pivot = Median3( A, Left, Right );
i = Left; j = Right – 1;
for( ; ; ) {
while ( A[ ++i ] < Pivot ) { }
while ( A[ ––j ] > Pivot ) { }
if ( i < j )
Swap( &A[i], &A[j] );
else break;
}
Swap( &A[i], &A[ Right-1 ] );
Quicksort( A, Left, i-1 );
Quicksort( A, i+1, Right );
}
else
Insertion_Sort( A+Left, Right-Left+1 );
｝
c代码：
/* 快速排序 */
ElementType Median3( ElementType A[], int Left, int Right )
{
int Center = (Left+Right) / 2;
if ( A[Left] > A[Center] )
Swap( &A[Left], &A[Center] );
if ( A[Left] > A[Right] )
Swap( &A[Left], &A[Right] );
if ( A[Center] > A[Right] )
Swap( &A[Center], &A[Right] );
/* 此时A[Left] <= A[Center] <= A[Right] */
Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
/* 只需要考虑A[Left+1] … A[Right-2] */
return A[Right-1]; /* 返回基准Pivot */
}
void Qsort( ElementType A[], int Left, int Right )
{ /* 核心递归函数 */
int Pivot, Cutoff, Low, High;
if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多，进入快排 */
Pivot = Median3( A, Left, Right ); /* 选基准 */
Low = Left; High = Right-1;
while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
while ( A[++Low] < Pivot ) ;
while ( A[--High] > Pivot ) ;
if ( Low < High ) Swap( &A[Low], &A[High] );
else break;
}
Swap( &A[Low], &A[Right-1] ); /* 将基准换到正确的位置 */
Qsort( A, Left, Low-1 ); /* 递归解决左边 */
Qsort( A, Low+1, Right ); /* 递归解决右边 */
}
else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少，用简单排序 */
}
void QuickSort( ElementType A[], int N )
{ /* 统一接口 */
Qsort( A, 0, N-1 );
}
显然，它是一个不稳定排序。。。。。。后面还有表排序和基排序，就暂时不写上来了，因为我学的也不好，下面来比较下这几种排序算法，由下面一张图来感受下这些算法的情况：
排序算法就告一段落了，接下来就是查找算法了。
然后总结了一点细节上的东西，冒泡排序虽然排序时间成本大，属于简单排序，但是它因为只交换两个相邻的元素，可以很方便的用于排序链表，因为它还是一个严格的从上到下排序的过程，堆排序就是选择排序的进阶版本嘛，归并排序是一个强NlogN排序，但是就是需要额外的空间，表排序是用于结构排序的一种排序算法，因为结构的移动成本很大，我们不移动结构本身，移动指向结构的指针，这是一种间接排序。