关于排序，在我的所学范围之内，时间复杂度比较低的，其实就这么几种，快速排序，堆排序，希尔排序，归并排序（主要指二路归并）
下面我就来介绍这几种排序算法
快速排序是应用最广泛和弹性最大的排序算法，他不仅可以进行简单的增排序和减排序，还可以进行一些比较特殊的排序
//这是函数的精华所在，分区函数
1 void Mypartition ( elementType A[],int low,int high,int *cutPoint ) 2 { 3 int x = A[low]; 4 while ( low < high ) 5 { 6 while ( high > low && A[high] >= x ) //这个地方可以看出来，快速排序是不稳定的 7 { 8 high--; 9 } 10 A[low] = A[high]; 11 while ( low < high && A[low] < x ) 12 { 13 low++; 14 } 15 A[high] = A[low]; 16 } 17 A[low] = A[high] = x; 18 *cutPoint = low; 19 } 20 void QuickSort ( elementType A[],int low,int high ) 21 { 22 if ( low < high ) 23 { 24 int cutPoint; 25 Mypartition ( A,low,high,&cutPoint ); 26 QuickSort( A,low,cutPoint - 1 ); 27 QuickSort( A,cutPoint + 1,high); 28 } 29 }
从上面我们可以看出，分区函数是最关键的函数，他的作用也绝不止步于此，下面就看他的一个应用
1 //4. 快速排序的应用 2 //*********************************************// 3 //* 函数功能:所有三的倍数在最左面，除三余一的在中间，除三余二的在最右面*// 4 //* 函数参数:数组指针，数组下标的下界和上界*// 5 //* 返 回 值:无*// 6 //*********************************************// 7 void SpecialSort ( elementType A[],int low,int high ) 8 { 9 int i = low; 10 int j = high; 11 //下面对整体进行三的倍数和非三的倍数的区分 12 13 //先从左端找到第一个3的非倍数 14 while ( i < j && A[i] % 3 != 0 ) 15 { 16 i++; 17 } 18 int x = A[i]; 19 20 while ( i < j ) 21 { 22 while ( j > i && A[j] % 3 != 0 ) 23 { 24 j--; 25 } 26 A[i] = A[j]; 27 while ( i < j && A[i] % 3 == 0 ) 28 { 29 i++; 30 } 31 A[j] = A[i]; 32 } 33 A[j] = A[i] = x; 34 //下面对非三的倍数进行区分 35 j = high; 36 //先找到第一个除三余2的数 37 while ( i < j && A[i] % 3 == 1 ) 38 { 39 i++; 40 } 41 x = A[i]; 42 43 while ( i < j ) 44 { 45 while ( j > i && A[j] % 3 == 2 ) 46 { 47 j--; 48 } 49 A[i] = A[j]; 50 while ( i < j && A[i] % 3 == 1 ) 51 { 52 i++; 53 } 54 A[j] = A[i]; 55 } 56 A[i] = A[j] = x; 57 }
上面函数的应用是很能说明问题的，对一个数组按照不同的特征进行分类，这也正是分区函数的作用所在，除此之外，我们一定要注意，分区函数的关键是找到分界点，根据分界点进行不同特征的划分
希尔排序
希尔排序它是在直接插入排序的基础上设计的，插入排序的时间复杂度与数据的是否有序是息息相关的，所以希尔排序便是利用这一点，从不同的步长出发将数组分成几组进行排序，最后再对整体进行排序，时间复杂度就将会降低
1 void ShellSort ( elementType A[],int n ) 2 { 3 int dh,i,j; 4 cout<<"请输入步dh:"<<endl; 5 cin>>dh; 6 int temp; 7 while ( dh > 0 ) 8 { 9 for ( i = dh;i < n;i++ ) 10 { 11 temp = A[i]; 12 for ( j = i - dh;j >= 0;j = j - dh ) 13 { 14 if ( temp < A[j] ) 15 { 16 A[j + dh] = A[j]; 17 } 18 else 19 { 20 break; 21 } 22 } 23 A[j + dh] = temp; 24 } 25 dh = dh / 2; 26 } 27 }
堆排序
这个是在选择排序的基础上，将数组看做是顺序储存的树，经过特殊的筛选操作，一个个的找到最大值或者最小值，从而实现类似于直接选择排序的算法
1 //4. 堆排序 2 //*********************************************// 3 //* 函数功能:堆排序（shift为核心的筛选算法）*// 4 //* 函数参数:*// 5 //* 返 回 值:空*// 6 //*********************************************// 7 //对以root为根节点，不超过n的数组调整为大根堆(注意调整是在已是大根堆的基础上调整的） 8 void shift ( elementType A[],int root,int n ) 9 { 10 int i = root; 11 int x = A[i]; //保存根节点的值 12 int j = 2*i; 13 14 while ( j < n ) 15 { 16 if ( j + 1 <= n && A[j+1] > A[j] ) 17 { 18 j = j + 1; 19 } 20 if ( x >= A[j] ) 21 { 22 break; 23 } 24 else 25 { 26 A[i] = A[j]; 27 i = j; 28 j = 2*j; 29 } 30 } 31 A[i] = x; 32 33 } 34 //先建立堆，再输出堆 35 void HeapSort ( elementType A[],int n ) 36 { 37 for ( int i = n / 2;i >= 0;i-- ) 38 { 39 shift ( A,i,n ); 40 } 41 for ( int i = n - 1;i > 0;i-- ) 42 { 43 elementType temp; 44 temp = A[0]; 45 A[0] = A[i]; 46 A[i] = temp; 47 48 shift( A,0,i - 1); 49 } 50 } 51 //************函数结束*************//
最后便是归并排序，我们这里只介绍二路归并排序，归并排序分为自顶向下和自底向上的排序，而就操作的复杂性而言，自顶向下是比较简单的，先划分再归并，利用递归
1 //3. 二路归并排序 2 //*********************************************// 3 //* 函数功能:自上而下的二路归并排序*// 4 //* 函数参数:数组下标的下界和上界*// 5 //* 返 回 值:无*// 6 //*********************************************// 7 //归并函数，将la-lb和lb-lc的数组进行归并 8 void Merge ( elementType A[],int la,int lb,int lc ) 9 { 10 int i = la; 11 int j = lb + 1; 12 int k = 0; 13 elementType C[lc-la+1]; 14 while ( i <= lb && j <= lc ) 15 { 16 if ( A[i] < A[j] ) 17 { 18 C[k++] = A[i++]; 19 } 20 if ( A[i] > A[j] ) 21 { 22 C[k++] = A[j++]; 23 } 24 if ( A[i] == A[j] ) 25 { 26 C[k++] = A[i++]; 27 } 28 } 29 while ( i <= lb ) 30 { 31 C[k++] = A[i++]; 32 } 33 while ( j <= lc ) 34 { 35 C[k++] = A[j++]; 36 } 37 //将C数组赋值回原来的A数组 38 for ( i = la,k = 0;i <= lc;i++,k++ ) 39 { 40 A[i] = C[k]; 41 } 42 } 43 //主函数 44 void MergeSort ( elementType A[],int low,int high ) 45 { 46 if ( low < high ) 47 { 48 int mid = ( low + high ) / 2; 49 MergeSort(A,low,mid); 50 MergeSort(A,mid+1,high); 51 Merge(A,low,mid,high); 52 } 53 } 54 //************函数结束*************//
原文：https://www.cnblogs.com/qianqianjunzi/p/10295328.html