排序算法总结附代码（冒泡、选择、插入、希尔、归并、快排）
最近，看数据结构，系统的学了一遍各种排序算法，抽点空总结出来。
堆排序和基数排序，后面再总结一下。。。。
冒泡排序： 从前向后扫描，依次比较相邻两个元素，若前者大，则交换位置。第一趟下来，最大的元素必在最后的位置。
（本质问题：有多少个逆序对，就需要交换多少次，每次只能消除一个逆序对）
特点：最坏情况 O（N^2），优点是可以对链表数据排序， 稳定（不会交换数值相同元素的顺序）。
代码：
void Bubble_sort ( ElementType A[], int N) //冒泡排序
{
int i,p;
int flag; //flag 用于判断，如果某一次的冒泡过程中，已排好序，则跳出排序
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^2），不稳定
代码：
int ScanForMin(int list[], int i, int n) //查找最小数的位置下标
{
int Min_position = i;
int j;
for ( j=i; j<n; j++){
if( list[j] < list[Min_position] )
Min_position = j;
}
return Min_position;
}
void Selection_Sort( ElementType A[], int N) //选择排序算法，每次在未排序的数列中选择一个最小
//的，粘在已排好序的数组后面
{
int i;
int MinPosition;
for ( i=0; i<N; i ++) {
MinPosition = ScanForMin( A, i, N ); //算法速度的瓶颈，在于查找
Swap( &A[i], &A[MinPosition] ); //交换步骤O(N)
}
}插入排序：模拟抓牌的过程，抓起一张牌，与前面的进行比较，插入到前面已排好序相应的位置（最后一次插入之前，可能所有的 元素都未在正确位置）
（本质问题同冒泡排序一样：有多少个逆序对，就需要交换多少次，每次只能消除一个逆序对）
特点：最坏情况 O（N^2）， 稳定。
代码：
void Insertion_sort ( ElementType A[], int N) //插入排序
{
int i,p,Tmp;
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; //新牌落位
}
}
希尔排序：在插入排序的基础上，每次选择要插入的数据有一定间隔，然后间隔从大到小，最后一趟间距为1，就是原插入排序
（根本目标，在于每次交换尽可能消除更多的逆序对，因为间隔交换数据，势必会减少很多逆序对 ，核心是希尔增序序列）
特点：最坏情况 thet (N^(3/2 ))，但不稳定
代码：
void Shell_sort ( ElementType A[] , int N) //希尔排序 (不稳定)
{
int i,p,Tmp,D;
for( D=N/2; D>0; D/=2) { //希尔增量序列 ，这里可以定义不同的增量序列
//Hibbard增量序列，Dk= 2^k -1 ,最坏情况 thet(N^(3/2 ))
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;
}
}
}
//void Shell_sort( 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;
// }
//}归并排序：将序列不停的分割下去，直到2个，直接比较交换位置（然后，再两两合并。有两种算法，一种是递归算法，一种是非递归算法。
特点：平均复杂度 NlogN , 稳定，最坏复杂度也是NlogN,而且还是稳定的 ，算法千好万好，唯独需要开个内存空间， 来回倒元素 ，一般不用于内排序，多用于外排序 （内存装不下全部的数据，需要借用外部存储空间进行排序）
代码：
///////////*****递归的归并排序****/////////////////
/* L = 左边起始位置，R = 右边起始位置， RightEnd= 右边重点位置 */
void Merge ( ElementType A[], ElementType TmpA[], //归并函数
int L, int R, int RightEnd )
{
int LeftEnd = R - 1;
int Tmp = L;
int 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++];
int i;
for ( i=0; i< NumElements; i++, RightEnd--)
A[RightEnd] = TmpA[RightEnd];
}
///////递归排序函数，递归到最小单元：一单元一个数，相邻归并成两个数，一次类推
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 Merge_sort ( ElementType A[], int N)
{
ElementType *TmpA;
TmpA = malloc( N * sizeof( ElementType ) );
if ( TmpA != NULL ) {
MSort( A, TmpA, 0, N-1);
free ( TmpA );
}
else printf("ERROR 空间不足");
}
///////////*****非递归的归并排序****/////////////////
void Merge1 ( ElementType A[], ElementType TmpA[], //归并函数
int L, int R, int RightEnd )
{
int LeftEnd = R - 1;
int Tmp = L;
int 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++];
/////与Merge唯一不同的地方就是 不需要将TmpA 倒回至 A；
}
///////非递归排序算法
void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length)
{
int i,j;
for ( i=0; i<= N-2*length; i+= 2*length )
Merge1( A, TmpA, i, i+length, i+2*length-1 );
if ( i+length < N )
Merge1( A, TmpA, i, i+length, N-1);
else
for ( j=i; j<N; j++ ) TmpA[j] = A[j];
}
////////排序接口函数///////
void Merge1_sort ( ElementType A[], int N )
{
int length = 1;
ElementType *TmpA;
TmpA = malloc( N * sizeof( ElementType ) );
if ( TmpA != NULL ) {
while( length < N ) {
Merge_pass( A, TmpA, N, length );
length *=2;
Merge_pass( TmpA, A, N, length ); //为了保证排好序的数据一定在A中
length *=2;
}
free ( TmpA );
}
else printf("ERROR 空间不足");
}快速排序：首先随机选择一个主元pivot，从两边向中间扫描，满足条件（前面大于pivot，后面的小于pivot）时，互换位置，每扫描一次，主元的位置就固定好了，左边都是小于自己的元素，右边都是大于自己的元素 ，然后左右两边分别递归调用这个函数，直到各个小序列剩2个元素，根据大小互换位置（或者当序列长度小于某个值cutoff时，对这个序列采用插入排序即可）
特点：目前应用较广泛的算法，平均时间NlogN,因为递归，需要空间logN，速度快，核心在于如何确定主元pivot，但不稳定。选主元的一种方法：选三个元素：第一个，中间的，最后一个，将三个数的中位数作为主元，并放在序列最后位置
代码：
void Insertion_sort ( ElementType A[], int N) //插入排序
{
int i,p,Tmp;
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; //新牌落位
}
}
////选主元的一种方法：选三个元素：第一个，中间的，最后一个，将三个数的中位数作为主元，并放在序列
///最后位置
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，后面的小于pivot）时，互换位置
void Qsort( ElementType A[], int Left, int Right )
{
int Cutoff = 2; //阈值，快排递归中，当序列长度小于cutoff时，采用简单排序（插入）
int pivot,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
Insertion_sort( A+Left, Right-Left+1 );
}
void QuickSort( ElementType A[], int N)
{
Qsort( A, 0, N-1);
}