設樹深度為k,k=[log2n]+1。從根到葉的篩選，元素比較次數至多2(k-1)次。所以，在建好堆后，排序程序中的篩選次數不超過下式：
2（[log2(n-1)]+[log2(n-2)]+…+log22）<2n（[log2n]）
而建堆時的比較次數不超過4n次，因此堆排序最壞情況下，時間復雜度為O(nlogn)
交換排序-冒泡排序（Bubble Sort）
在要排序的一組數中，對當前還未排好序的范圍內的全部數，自上而下對相鄰的兩個數一次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較后發現他們的排序與排序要求相反時，就將他們互換。
冒泡排序的示例：
演算法的實作
void bubbleSort(int a[], int n){
for(int i =0 ; i< n-1; ++i) {
for(int j = 0; j < n-i-1; ++j) {
if(a[j] > a[j+1])
{
int tmp = a[j] ; a[j] = a[j+1] ; a[j+1] = tmp;
}
}
}
}
對冒泡排序常見的改進方法是加入一標志性變數exchange，用于標志某一趟排序程序中是否有資料交換，如果進行某一趟排序時并沒有進行資料交換，則說明資料已經按要求排列好，可立即結束排序，避免不必要的比較程序。本文再提供以下兩種改進演算法：
1、 設定一標志性變數pos，用于記錄每趟排序中最后一次進行交換的位置。由于pos位置之后的記錄均已交換到位，故在進行下一趟排序時只要掃描到pos位置即可。
void Bubble_1 ( int r[], int n) {
int i= n -1; //初始時,最后位置保持不變
while ( i> 0) {
int pos= 0; //每趟開始時,無記錄交換
for (int j= 0; j< i; j++)
if (r[j]> r[j+1]) {
pos= j; //記錄交換的位置
int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
}
i= pos; //為下一趟排序作準備
}
}
2、 傳統冒泡排序中每一趟排序操作只能找到一個最大值或最小值，我們考慮利用每趟排序中進行正向和反向兩遍冒泡的方法一次可以得到兩個最終值（最大值和最小值），從而是排序趟數幾乎減少了一半。
改進后的演算法實作為：
void Bubble_2 ( int r[], int n){
int low = 0;
int high= n -1; //設定變數的初始值
int tmp,j;
while (low < high) {
for (j= low; j< high; ++j) //正向冒泡,找到最大者
if (r[j]> r[j+1]) {
tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
}
--high; //修改high值, 前移一位
for ( j=high; j>low; --j) //反向冒泡,找到最小者
if (r[j]<r[j-1]) {
tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;
}
++low; //修改low值,后移一位
}
}
交換排序-快速排序(Quick Sort)
1) 選擇一個基準元素，通常選擇第一個元素或者最后一個元素，
2) 通過一趟排序將待排序的記錄分割成獨立的兩部分，其中一部分的元素值均比基準元素值小。另一部分記錄的元素值比基準值大。
3) 此時基準元素在其排好序后的正確位置
4) 然后分別對這兩部分記錄用同樣的方法繼續進行排序，直到整個序列有序。
快速排序的示例：
（1） 一趟排序的程序：
（b）排序的全程序
演算法的實作：
遞回實作：
#include <iostream>
using namespace std::cout;
using namespace std::endl;
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);
}
分析：
快速排序是通常被認為在同數量級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 qsort_improve(int r[ ],int low,int high, int k){
if( high -low > k ) { //長度大于k時遞回, k為指定的數
int pivot = partition(r, low, high); // 呼叫的Partition演算法保持不變
qsort_improve(r, low, pivot - 1,k);
qsort_improve(r, pivot + 1, high,k);
}
}
void quickSort(int r[], int n, int k){
qsort_improve(r,0,n,k);//先呼叫改進演算法Qsort使之基本有序
//再用插入排序對基本有序序列排序
for(int i=1; i<=n;i ++){
int tmp = r[i];
int j=i-1;
while(tmp < r[j]){
r[j+1]=r[j]; j=j-1;
}
r[j+1] = tmp;
}
}
int main(){
int a[10] = {3,1,5,7,2,4,9,6,10,8};
cout<<"初始值：";
print(a,10);
quickSort(a,9,4);
cout<<"結果：";
print(a,10);
}
歸并排序（Merge Sort）
基本思想
歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。
歸并排序示例：
合并方法：
設[i…n]由兩個有序子表r[i…m]和r[m+1…n]組成，兩個子表長度分別為n-i+1、n-m。
1、 j=m+1;k=I;i=I;//置兩個子表的起始下標及輔助陣列的起始下標
2、 若i>m或j>n,轉(4)//其中一個子表已合并完，比較選取結束
3、 選取r[i]和r[j]較小的存入輔助陣列rf
如果r[i]<r[j],rf[k]=r[i];i++;k++; 轉(2)
否則，rf[k]=r[j];j++;k++;轉(2)
4、 將尚未處理完的子表中元素存入rf
如果i<=m,將r[i…m]存入rf[k…n] //前一子表非空
如果j<=n,將r[j…n]存入rf[k…n] //后一子表非空
5、 合并結束
一個元素的表總是有序的。所以對n個元素的待排序列，每個元素可看成是1個有序子表。對子表兩兩合并生成n/2個子表，所得子表除最后一個子表長度可能為1外，其余子表長度均為2.再進行兩兩合并，知道生成n個元素按關鍵碼有序的表。
桶排序/基數排序(Radix Sort)
說基數排序之前，我們先說桶排序
基本思想：是將陣列分到有限數量的桶子里。每個桶子再個別排序(有可能再使用別的排序演算法或是以遞回方式繼續使用桶排序進行排序)。桶排序是鴿巢排序的一種歸納結果。當要被排序的陣列內的數值是均勻分配時候，桶排序使用線性時間(O（n）)。但桶排序并不是比較排序，他不受到O(nlogn)下限的影響。
簡單來說，就是把資料分組，放在一個個的桶中，然后對每個桶里面的進行排序。
例如要對大小為[1…1000]范圍內的n個整數A[1…n]排序
首先，可以把桶設大大小為10的范圍，具體而言，設集合B[1]存盤[1…10]整數，集合B[2]存盤(10..20)的整數，。。。集合B[i]存盤((i-1)*10,i*10)的整數，i=1,2,…100.總共有100個桶。
然后，對A[1…n]從頭到尾掃描一遍，把每個A[i]放如對應的桶B[j].再這100個桶中每個桶里的數字排序，這時可用冒泡，選擇，乃至快排，一般來說任何排序法都可以。
最后，依次輸入每個桶里面的數字，且每個桶中的數字從小到大輸出，這樣得到所有數字排好序的一個序列了。
假設有n個數字，有m個桶，如果數字是平均分布的，則每個桶里面平均有n/m個數字。如果對每個桶中的數字采用快速排序，那么整個演算法的復雜度是
O(n+m*n/m*log(n/m))=O(n+nlogn-nlogm)
從上式看出，當m接近n的時候，桶排序復雜度接近O(n)
當然，以上復雜度的計算是基于輸入的n個數字是平均分布這個假設。這個假設是很強，實體應用中效果并沒有這么好。如果所有的數字都落在同一桶，那就退化成一般的排序了。
前面說的幾大排序演算法，大部分時間復雜度都是O(n2),也有部分排序演算法時間復雜度O(nlogn)。而桶式排序能實作O(n)的時間復雜讀。但桶排序的缺點是：
1、 首先是桶空間復雜比較高，需要的額外開銷大。排序有兩個陣列的控制元件開銷，一個存放待排序陣列，一個就是所謂的桶，比如待排序值是從0到m-1，那就需要m個桶，這個桶陣列就要至少m個空間
2、 其次待排序的元素都要在一定的范圍內等等。
桶式排序是一種分配排序。分配排序的特定是不需要進行關鍵碼的比較，但前提是要知道待排序列的一些具體情況。
分配排序的基本思想：說白了就是進行多次的桶式排序。
基數排序程序無須比較關鍵字，而是通過“分配”和“收集”程序來實作排序。它們的時間復雜度可達到線性階：O(n)。
實體:
撲克牌中52 張牌，可按花色和面值分成兩個欄位，其大小關系為：
花色： 梅花< 方塊< 紅心< 黑心
面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A
若對撲克牌按花色、面值進行升序排序，得到如下序列：
即兩張牌，若花色不同，不論面值怎樣，花色低的那張牌小于花色高的，只有在同花色情況下，大小關系才由面值的大小確定。這就是多關鍵碼排序。
為得到排序結果，我們討論兩種排序方法。
方法1：先對花色排序，將其分為4 個組，即梅花組、方塊組、紅心組、黑心組。再對每個組分別按面值進行排序，最后，將4 個組連接起來即可。
方法2：先按13 個面值給出13 個編號組(2 號，3 號，...，A 號)，將牌按面值依次放入對應的編號組，分成13 堆。再按花色給出4 個編號組(梅花、方塊、紅心、黑心)，將2號組中牌取出分別放入對應花色組，再將3 號組中牌取出分別放入對應花色組，……，這樣，4 個花色組中均按面值有序，然后，將4 個花色組依次連接起來即可。
設n 個元素的待排序列包含d 個關鍵碼{k1，k2，…，kd}，則稱序列對關鍵碼{k1，k2，…，kd}有序是指：對于序列中任兩個記錄r[i]和r[j](1≤i≤j≤n)都滿足下列有序關系：
其中k1 稱為最主位關鍵碼，kd 稱為最次位關鍵碼 。
兩種多關鍵碼排序方法：
多關鍵碼排序按照從最主位關鍵碼到最次位關鍵碼或從最次位到最主位關鍵碼的順序逐次排序，分兩種方法：
最高位優先(Most Significant Digit first)法，簡稱MSD 法：
1）先按k1 排序分組，將序列分成若干子序列，同一組序列的記錄中，關鍵碼k1 相等。
2）再對各組按k2 排序分成子組，之后，對后面的關鍵碼繼續這樣的排序分組，直到按最次位關鍵碼kd 對各子組排序后。
3）再將各組連接起來，便得到一個有序序列。撲克牌按花色、面值排序中介紹的方法一即是MSD 法。
最低位優先(Least Significant Digit first)法，簡稱LSD 法：
1) 先從kd 開始排序，再對kd-1進行排序，依次重復，直到按k1排序分組分成最小的子序列后。
2) 最后將各個子序列連接起來，便可得到一個有序的序列, 撲克牌按花色、面值排序中介紹的方法二即是LSD 法。
基于LSD方法的鏈式基數排序的基本思想
“多關鍵字排序”的思想實作“單關鍵字排序”。對數字型或字符型的單關鍵字，可以看作由多個數位或多個字符構成的多關鍵字，此時可以采用“分配-收集”的方法進行排序，這一程序稱作基數排序法，其中每個數字或字符可能的取值個數稱為基數。比如，撲克牌的花色基數為4，面值基數為13。在整理撲克牌時，既可以先按花色整理，也可以先按面值整理。按花色整理時，先按紅、黑、方、花的順序分成4摞（分配），再按此順序再疊放在一起（收集），然后按面值的順序分成13摞（分配），再按此順序疊放在一起（收集），如此進行二次分配和收集即可將撲克牌排列有序。
基數排序:
是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。基數排序基于分別排序，分別收集，所以是穩定的。
演算法實作：
Void RadixSort(Node L[],length,maxradix)
{
int m,n,k,lsp;
k=1;m=1;
int temp[10][length-1];
Empty(temp); //清空臨時空間
while(k<maxradix) //遍歷所有關鍵字
{
for(int i=0;i<length;i++) //分配程序
{
if(L[i]<m)
Temp[0][n]=L[i];
else
Lsp=(L[i]/m)%10; //確定關鍵字
Temp[lsp][n]=L[i];
n++;
}
CollectElement(L,Temp); //收集
n=0;
m=m*10;
k++;
}
}
各種排序的穩定性，時間復雜度和控制元件復雜度總結：
uj5u.com熱心網友回復：
實體:撲克牌中52 張牌，可按花色和面值分成兩個欄位，其大小關系為：
花色： 梅花< 方塊< 紅心< 黑心
面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A
若對撲克牌按花色、面值進行升序排序，得到如下序列：
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/83397.html
上一篇：指令集是如何存放到CPU里的？