必须知道的C语言八大排序算法(收藏)

分析：

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

快速排序的改进

在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有所降低，且当k取值为 8 左右时,改进算法的性能最佳。算法思想如下：

void print(int a[], int n){ 
 for(int j= 0; j<n; j++){ 
 cout<<a[j] <<" "; 
 } 
 cout<<endl; 
} 
void swap(int *a, int *b) 
{ 
 int tmp = *a; 
 *a = *b; 
 *b = tmp; 
} 
int partition(int a[], int low, int high) 
{ 
 int privotKey = a[low];  //基准元素 
 while(low < high){   //从表的两端交替地向中间扫描 
 while(low < high && a[high] >= privotKey) --high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端 
 swap(&a[low], &a[high]); 
 while(low < high && a[low] <= privotKey ) ++low; 
 swap(&a[low], &a[high]); 
 } 
 print(a,10); 
 return low; 
} 
void quickSort(int a[], int low, int high){ 
 if(low < high){ 
 int privotLoc = partition(a, low, high); //将表一分为二 
 quickSort(a, low, privotLoc -1); //递归对低子表递归排序 
 quickSort(a, privotLoc + 1, high); //递归对高子表递归排序 
 } 
} 
int main(){ 
 int a[10] = {3,1,5,7,2,4,9,6,10,8}; 
 cout<<"初始值："; 
 print(a,10); 
 quickSort(a,0,9); 
 cout<<"结果："; 
 print(a,10); 
}