概述排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過(guò)程中需要訪問(wèn)外存。
我們這里說(shuō)說(shuō)八大排序就是內(nèi)部排序。
????
????當(dāng)n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。
?? 快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短；
?
1.插入排序—直接插入排序(Straight Insertion Sort)
基本思想:
將一個(gè)記錄插入到已排序好的有序表中，從而得到一個(gè)新，記錄數(shù)增1的有序表。即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹埂?/p>
要點(diǎn)：設(shè)立哨兵，作為臨時(shí)存儲(chǔ)和判斷數(shù)組邊界之用。
直接插入排序示例：
?
如果碰見一個(gè)和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無(wú)序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。
算法的實(shí)現(xiàn)：
[cpp] view plaincopyprint?
void?print(int?a[],?int?n?,int?i){??????cout<<i?<<":";??????for(int?j=?0;?j<8;?j++){??????????cout<<a[j]?<<"?";??????}??????cout<<endl;??}??????void?InsertSort(int?a[],?int?n)??{??????for(int?i=?1;?i<n;?i++){??????????if(a[i]?<?a[i-1]){???????????????????????????int?j=?i-1;???????????????int?x?=?a[i];????????????????????a[i]?=?a[i-1];???????????????????????while(x?<?a[j]){??????????????????a[j+1]?=?a[j];??????????????????j--;?????????????????????}??????????????a[j+1]?=?x;??????????????}??????????print(a,n,i);???????????????}????????}????int?main(){??????int?a[8]?=?{3,1,5,7,2,4,9,6};??????InsertSort(a,8);??????print(a,8,8);??}?? void print(int a[], int n ,int i){cout<<i <<":";for(int j= 0; j<8; j++){cout<<a[j] <<" ";}cout<<endl;
}void InsertSort(int a[], int n)
{for(int i= 1; i<n; i++){if(a[i] < a[i-1]){ //若第i個(gè)元素大于i-1元素，直接插入。小于的話，移動(dòng)有序表后插入int j= i-1; int x = a[i]; //復(fù)制為哨兵，即存儲(chǔ)待排序元素a[i] = a[i-1]; //先后移一個(gè)元素while(x < a[j]){ //查找在有序表的插入位置a[j+1] = a[j];j--; //元素后移}a[j+1] = x; //插入到正確位置}print(a,n,i); //打印每趟排序的結(jié)果}}int main(){int a[8] = {3,1,5,7,2,4,9,6};InsertSort(a,8);print(a,8,8);
}
效率：
時(shí)間復(fù)雜度：O（n^2）.
其他的插入排序有二分插入排序，2-路插入排序。
?
?2. 插入排序—希爾排序（Shell`s Sort）
希爾排序是1959 年由D.L.Shell 提出來(lái)的，相對(duì)直接排序有較大的改進(jìn)。希爾排序又叫縮小增量排序
基本思想：
先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。
操作方法：
選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。希爾排序的示例：
?
算法實(shí)現(xiàn)：
?
我們簡(jiǎn)單處理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n為要排序數(shù)的個(gè)數(shù)
即：先將要排序的一組記錄按某個(gè)增量d（n/2,n為要排序數(shù)的個(gè)數(shù)）分成若干組子序列，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行直接插入排序，然后再用一個(gè)較小的增量（d/2）對(duì)它進(jìn)行分組，在每組中再進(jìn)行直接插入排序。繼續(xù)不斷縮小增量直至為1，最后使用直接插入排序完成排序。
[cpp] view plaincopyprint?
void?print(int?a[],?int?n?,int?i){??????cout<<i?<<":";??????for(int?j=?0;?j<8;?j++){??????????cout<<a[j]?<<"?";??????}??????cout<<endl;??}????void?ShellInsertSort(int?a[],?int?n,?int?dk)??{??????for(int?i=?dk;?i<n;?++i){??????????if(a[i]?<?a[i-dk]){??????????????????????int?j?=?i-dk;?????????????????int?x?=?a[i];???????????????????????a[i]?=?a[i-dk];?????????????????????while(x?<?a[j]){?????????????????????a[j+dk]?=?a[j];??????????????????j?-=?dk;?????????????????????????}??????????????a[j+dk]?=?x;????????????????????}??????????print(a,?n,i?);??????}????????}????void?shellSort(int?a[],?int?n){????????int?dk?=?n/2;??????while(?dk?>=?1??){??????????ShellInsertSort(a,?n,?dk);??????????dk?=?dk/2;??????}??}??int?main(){??????int?a[8]?=?{3,1,5,7,2,4,9,6};??????????shellSort(a,8);???????????????print(a,8,8);??}?? void print(int a[], int n ,int i){cout<<i <<":";for(int j= 0; j<8; j++){cout<<a[j] <<" ";}cout<<endl;
}
/*** 直接插入排序的一般形式** @param int dk 縮小增量，如果是直接插入排序，dk=1**/void ShellInsertSort(int a[], int n, int dk)
{for(int i= dk; i<n; ++i){if(a[i] < a[i-dk]){ //若第i個(gè)元素大于i-1元素，直接插入。小于的話，移動(dòng)有序表后插入int j = i-dk; int x = a[i]; //復(fù)制為哨兵，即存儲(chǔ)待排序元素a[i] = a[i-dk]; //首先后移一個(gè)元素while(x < a[j]){ //查找在有序表的插入位置a[j+dk] = a[j];j -= dk; //元素后移}a[j+dk] = x; //插入到正確位置}print(a, n,i );}}/*** 先按增量d（n/2,n為要排序數(shù)的個(gè)數(shù)進(jìn)行希爾排序**/
void shellSort(int a[], int n){int dk = n/2;while( dk >= 1 ){ShellInsertSort(a, n, dk);dk = dk/2;}
}
int main(){int a[8] = {3,1,5,7,2,4,9,6};//ShellInsertSort(a,8,1); //直接插入排序shellSort(a,8); //希爾插入排序print(a,8,8);
}
?
希爾排序時(shí)效分析很難，關(guān)鍵碼的比較次數(shù)與記錄移動(dòng)次數(shù)依賴于增量因子序列d的選取，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動(dòng)次數(shù)。目前還沒有人給出選取最好的
增量因子序列的方法。增量因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：增量因子中除1 外沒有公因子，且最后一個(gè)增量因子必須為1。希爾排序方法是一個(gè)不穩(wěn)定的排序方法。 ?
3. 選擇排序—簡(jiǎn)單選擇排序（Simple Selection Sort）
基本思想：
在要排序的一組數(shù)中，選出最小（或者最大）的一個(gè)數(shù)與第1個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小（或者最大）的與第2個(gè)位置的數(shù)交換，依次類推，直到第n-1個(gè)元素（倒數(shù)第二個(gè)數(shù)）和第n個(gè)元素（最后一個(gè)數(shù)）比較為止。
簡(jiǎn)單選擇排序的示例：
?
操作方法：
第一趟，從n 個(gè)記錄中找出關(guān)鍵碼最小的記錄與第一個(gè)記錄交換；
第二趟，從第二個(gè)記錄開始的n-1 個(gè)記錄中再選出關(guān)鍵碼最小的記錄與第二個(gè)記錄交換；
以此類推.....
第i 趟，則從第i 個(gè)記錄開始的n-i+1 個(gè)記錄中選出關(guān)鍵碼最小的記錄與第i 個(gè)記錄交換，
直到整個(gè)序列按關(guān)鍵碼有序。
算法實(shí)現(xiàn)：
[cpp] view plaincopyprint?
void?print(int?a[],?int?n?,int?i){??????cout<<"第"<<i+1?<<"趟?:?";??????for(int?j=?0;?j<8;?j++){??????????cout<<a[j]?<<"??";??????}??????cout<<endl;??}??int?SelectMinKey(int?a[],?int?n,?int?i)??{??????int?k?=?i;??????for(int?j=i+1?;j<?n;?++j)?{??????????if(a[k]?>?a[j])?k?=?j;??????}??????return?k;??}????void?selectSort(int?a[],?int?n){??????int?key,?tmp;??????for(int?i?=?0;?i<?n;?++i)?{??????????key?=?SelectMinKey(a,?n,i);???????????????????if(key?!=?i){??????????????tmp?=?a[i];??a[i]?=?a[key];?a[key]?=?tmp;?????????}??????????print(a,??n?,?i);??????}??}??int?main(){??????int?a[8]?=?{3,1,5,7,2,4,9,6};??????cout<<"初始值：";??????for(int?j=?0;?j<8;?j++){??????????cout<<a[j]?<<"??";??????}??????cout<<endl<<endl;??????selectSort(a,?8);??????print(a,8,8);??}?? void print(int a[], int n ,int i){cout<<"第"<<i+1 <<"趟 : ";for(int j= 0; j<8; j++){cout<<a[j] <<" ";}cout<<endl;
}
/*** 數(shù)組的最小值** @return int 數(shù)組的鍵值*/
int SelectMinKey(int a[], int n, int i)
{int k = i;for(int j=i+1 ;j< n; ++j) {if(a[k] > a[j]) k = j;}return k;
}/*** 選擇排序**/
void selectSort(int a[], int n){int key, tmp;for(int i = 0; i< n; ++i) {key = SelectMinKey(a, n,i); //選擇最小的元素if(key != i){tmp = a[i]; a[i] = a[key]; a[key] = tmp; //最小元素與第i位置元素互換}print(a, n , i);}
}
int main(){int a[8] = {3,1,5,7,2,4,9,6};cout<<"初始值：";for(int j= 0; j<8; j++){cout<<a[j] <<" ";}cout<<endl<<endl;selectSort(a, 8);print(a,8,8);
}
?簡(jiǎn)單選擇排序的改進(jìn)——二元選擇排序
簡(jiǎn)單選擇排序，每趟循環(huán)只能確定一個(gè)元素排序后的定位。我們可以考慮改進(jìn)為每趟循環(huán)確定兩個(gè)元素（當(dāng)前趟最大和最小記錄）的位置,從而減少排序所需的循環(huán)次數(shù)。改進(jìn)后對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序，最多只需進(jìn)行[n/2]趟循環(huán)即可。具體實(shí)現(xiàn)如下：
[cpp] view plaincopyprint?
void?SelectSort(int?r[],int?n)?{??????int?i?,j?,?min?,max,?tmp;??????for?(i=1?;i?<=?n/2;i++)?{????????????????????min?=?i;?max?=?i?;?????????for?(j=?i+1;?j<=?n-i;?j++)?{??????????????if?(r[j]?>?r[max])?{???????????????????max?=?j?;?continue?;???????????????}????????????????if?(r[j]<?r[min])?{???????????????????min?=?j?;???????????????}???????????}????????????????tmp?=?r[i-1];?r[i-1]?=?r[min];?r[min]?=?tmp;????????tmp?=?r[n-i];?r[n-i]?=?r[max];?r[max]?=?tmp;?????????}???}?? void SelectSort(int r[],int n) {int i ,j , min ,max, tmp;for (i=1 ;i <= n/2;i++) { // 做不超過(guò)n/2趟選擇排序 min = i; max = i ; //分別記錄最大和最小關(guān)鍵字記錄位置for (j= i+1; j<= n-i; j++) {if (r[j] > r[max]) { max = j ; continue ; } if (r[j]< r[min]) { min = j ; } } //該交換操作還可分情況討論以提高效率tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp; }
}
4. 選擇排序—堆排序（Heap Sort）
堆排序是一種樹形選擇排序，是對(duì)直接選擇排序的有效改進(jìn)。
基本思想：
堆的定義如下：具有n個(gè)元素的序列（k1,k2,...,kn),當(dāng)且僅當(dāng)滿足
時(shí)稱之為堆。由堆的定義可以看出，堆頂元素（即第一個(gè)元素）必為最小項(xiàng)（小頂堆）。 若以一維數(shù)組存儲(chǔ)一個(gè)堆，則堆對(duì)應(yīng)一棵完全二叉樹，且所有非葉結(jié)點(diǎn)的值均不大于(或不小于)其子女的值，根結(jié)點(diǎn)（堆頂元素）的值是最小(或最大)的。如：
（a）大頂堆序列：（96, 83,27,38,11,09)
? (b)? 小頂堆序列：（12，36，24，85，47，30，53，91）
?
初始時(shí)把要排序的n個(gè)數(shù)的序列看作是一棵順序存儲(chǔ)的二叉樹（一維數(shù)組存儲(chǔ)二叉樹），調(diào)整它們的存儲(chǔ)序，使之成為一個(gè)堆，將堆頂元素輸出，得到n 個(gè)元素中最小(或最大)的元素，這時(shí)堆的根節(jié)點(diǎn)的數(shù)最小（或者最大）。然后對(duì)前面(n-1)個(gè)元素重新調(diào)整使之成為堆，輸出堆頂元素，得到n 個(gè)元素中次小(或次大)的元素。依此類推，直到只有兩個(gè)節(jié)點(diǎn)的堆，并對(duì)它們作交換，最后得到有n個(gè)節(jié)點(diǎn)的有序序列。稱這個(gè)過(guò)程為堆排序。
因此，實(shí)現(xiàn)堆排序需解決兩個(gè)問(wèn)題： 1. 如何將n 個(gè)待排序的數(shù)建成堆； 2. 輸出堆頂元素后，怎樣調(diào)整剩余n-1 個(gè)元素，使其成為一個(gè)新堆。
首先討論第二個(gè)問(wèn)題：輸出堆頂元素后，對(duì)剩余n-1元素重新建成堆的調(diào)整過(guò)程。 調(diào)整小頂堆的方法：
1）設(shè)有m 個(gè)元素的堆，輸出堆頂元素后，剩下m-1 個(gè)元素。將堆底元素送入堆頂（（最后一個(gè)元素與堆頂進(jìn)行交換），堆被破壞，其原因僅是根結(jié)點(diǎn)不滿足堆的性質(zhì)。
2）將根結(jié)點(diǎn)與左、右子樹中較小元素的進(jìn)行交換。
3）若與左子樹交換：如果左子樹堆被破壞，即左子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)，則重復(fù)方法 （2）.
4）若與右子樹交換，如果右子樹堆被破壞，即右子樹的根結(jié)點(diǎn)不滿足堆的性質(zhì)。則重復(fù)方法 （2）.
5）繼續(xù)對(duì)不滿足堆性質(zhì)的子樹進(jìn)行上述交換操作，直到葉子結(jié)點(diǎn)，堆被建成。
稱這個(gè)自根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的調(diào)整過(guò)程為篩選。如圖：
再討論對(duì)n 個(gè)元素初始建堆的過(guò)程。 建堆方法：對(duì)初始序列建堆的過(guò)程，就是一個(gè)反復(fù)進(jìn)行篩選的過(guò)程。
1）n 個(gè)結(jié)點(diǎn)的完全二叉樹，則最后一個(gè)結(jié)點(diǎn)是第個(gè)結(jié)點(diǎn)的子樹。
2）篩選從第個(gè)結(jié)點(diǎn)為根的子樹開始，該子樹成為堆。
3）之后向前依次對(duì)各結(jié)點(diǎn)為根的子樹進(jìn)行篩選，使之成為堆，直到根結(jié)點(diǎn)。
如圖建堆初始過(guò)程：無(wú)序序列：（49，38，65，97，76，13，27，49） ?????????????????????????????
?????????????????????????????
?
?算法的實(shí)現(xiàn)：
從算法描述來(lái)看，堆排序需要兩個(gè)過(guò)程，一是建立堆，二是堆頂與堆的最后一個(gè)元素交換位置。所以堆排序有兩個(gè)函數(shù)組成。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實(shí)現(xiàn)排序的函數(shù)。
[cpp] view plaincopyprint?
void?print(int?a[],?int?n){??????for(int?j=?0;?j<n;?j++){??????????cout<<a[j]?<<"??";??????}??????cout<<endl;??}????????void?HeapAdjust(int?H[],int?s,?int?length)??{??????int?tmp??=?H[s];??????int?child?=?2*s+1;?????while?(child?<?length)?{??????????if(child+1?<length?&&?H[child]<H[child+1])?{?????????????++child?;??????????}??????????if(H[s]<H[child])?{??????????????H[s]?=?H[child];?????????????s?=?child;???????????????????child?=?2*s+1;??????????}??else?{?????????????????????????break;??????????}??????????H[s]?=?tmp;?????????????}??????print(H,length);??}??????void?BuildingHeap(int?H[],?int?length)??{???????????for?(int?i?=?(length?-1)?/?2?;?i?>=?0;?--i)??????????HeapAdjust(H,i,length);??}??void?HeapSort(int?H[],int?length)??{??????????BuildingHeap(H,?length);??????????for?(int?i?=?length?-?1;?i?>?0;?--i)??????{??????????????????int?temp?=?H[i];?H[i]?=?H[0];?H[0]?=?temp;??????????????????HeapAdjust(H,0,i);????}??}?????int?main(){??????int?H[10]?=?{3,1,5,7,2,4,9,6,10,8};??????cout<<"初始值：";??????print(H,10);??????HeapSort(H,10);??????????cout<<"結(jié)果：";??????print(H,10);????}?? void print(int a[], int n){for(int j= 0; j<n; j++){cout<<a[j] <<" ";}cout<<endl;
}/*** 已知H[s…m]除了H[s] 外均滿足堆的定義* 調(diào)整H[s],使其成為大頂堆.即將對(duì)第s個(gè)結(jié)點(diǎn)為根的子樹篩選, ** @param H是待調(diào)整的堆數(shù)組* @param s是待調(diào)整的數(shù)組元素的位置* @param length是數(shù)組的長(zhǎng)度**/
void HeapAdjust(int H[],int s, int length)
{int tmp = H[s];int child = 2*s+1; //左孩子結(jié)點(diǎn)的位置。(i+1 為當(dāng)前調(diào)整結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的位置)while (child < length) {if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比當(dāng)前待調(diào)整結(jié)點(diǎn)大的孩子結(jié)點(diǎn))++child ;}if(H[s]<H[child]) { // 如果較大的子結(jié)點(diǎn)大于父結(jié)點(diǎn)H[s] = H[child]; // 那么把較大的子結(jié)點(diǎn)往上移動(dòng)，替換它的父結(jié)點(diǎn)s = child; // 重新設(shè)置s ,即待調(diào)整的下一個(gè)結(jié)點(diǎn)的位置child = 2*s+1;} else { // 如果當(dāng)前待調(diào)整結(jié)點(diǎn)大于它的左右孩子，則不需要調(diào)整，直接退出break;}H[s] = tmp; // 當(dāng)前待調(diào)整的結(jié)點(diǎn)放到比其大的孩子結(jié)點(diǎn)位置上}print(H,length);
}/*** 初始堆進(jìn)行調(diào)整* 將H[0..length-1]建成堆* 調(diào)整完之后第一個(gè)元素是序列的最小的元素*/
void BuildingHeap(int H[], int length)
{ //最后一個(gè)有孩子的節(jié)點(diǎn)的位置 i= (length -1) / 2for (int i = (length -1) / 2 ; i >= 0; --i)HeapAdjust(H,i,length);
}
/*** 堆排序算法*/
void HeapSort(int H[],int length)
{//初始堆BuildingHeap(H, length);//從最后一個(gè)元素開始對(duì)序列進(jìn)行調(diào)整for (int i = length - 1; i > 0; --i){//交換堆頂元素H[0]和堆中最后一個(gè)元素int temp = H[i]; H[i] = H[0]; H[0] = temp;//每次交換堆頂元素和堆中最后一個(gè)元素之后，都要對(duì)堆進(jìn)行調(diào)整HeapAdjust(H,0,i);}
} int main(){int H[10] = {3,1,5,7,2,4,9,6,10,8};cout<<"初始值：";print(H,10);HeapSort(H,10);//selectSort(a, 8);cout<<"結(jié)果：";print(H,10);}
分析:
設(shè)樹深度為k，。從根到葉的篩選，元素比較次數(shù)至多2(k-1)次，交換記錄至多k 次。所以，在建好堆后，排序過(guò)程中的篩選次數(shù)不超過(guò)下式：?
???????????????????????????????
而建堆時(shí)的比較次數(shù)不超過(guò)4n 次，因此堆排序最壞情況下，時(shí)間復(fù)雜度也為：O(nlogn )。
?
5. 交換排序—冒泡排序（Bubble Sort）
基本思想：
在要排序的一組數(shù)中，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。
冒泡排序的示例：
?
算法的實(shí)現(xiàn)：
?
[cpp] view plaincopyprint?
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;??????????????}??????????}??????}??}?? 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;}}}
}
冒泡排序算法的改進(jìn)
對(duì)冒泡排序常見的改進(jìn)方法是加入一標(biāo)志性變量exchange，用于標(biāo)志某一趟排序過(guò)程中是否有數(shù)據(jù)交換，如果進(jìn)行某一趟排序時(shí)并沒有進(jìn)行數(shù)據(jù)交換，則說(shuō)明數(shù)據(jù)已經(jīng)按要求排列好，可立即結(jié)束排序，避免不必要的比較過(guò)程。本文再提供以下兩種改進(jìn)算法：
1．設(shè)置一標(biāo)志性變量pos,用于記錄每趟排序中最后一次進(jìn)行交換的位置。由于pos位置之后的記錄均已交換到位,故在進(jìn)行下一趟排序時(shí)只要掃描到pos位置即可。
改進(jìn)后算法如下:
[cpp] view plaincopyprint?
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;??????}???}???? void Bubble_1 ( int r[], int n) {int i= n -1; //初始時(shí),最后位置保持不變while ( i> 0) { int pos= 0; //每趟開始時(shí),無(wú)記錄交換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; //為下一趟排序作準(zhǔn)備}
}
2．傳統(tǒng)冒泡排序中每一趟排序操作只能找到一個(gè)最大值或最小值,我們考慮利用在每趟排序中進(jìn)行正向和反向兩遍冒泡的方法一次可以得到兩個(gè)最終值(最大者和最小者) , 從而使排序趟數(shù)幾乎減少了一半。
改進(jìn)后的算法實(shí)現(xiàn)為:
[cpp] view plaincopyprint?
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;?????????????????????????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;??????????????????????}???}??? void Bubble_2 ( int r[], int n){int low = 0; int high= n -1; //設(shè)置變量的初始值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值,后移一位}
}
6. 交換排序—快速排序（Quick Sort）
基本思想：
1）選擇一個(gè)基準(zhǔn)元素,通常選擇第一個(gè)元素或者最后一個(gè)元素,
2）通過(guò)一趟排序講待排序的記錄分割成獨(dú)立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)元素值小。另一部分記錄的?元素值比基準(zhǔn)值大。
3）此時(shí)基準(zhǔn)元素在其排好序后的正確位置
4）然后分別對(duì)這兩部分記錄用同樣的方法繼續(xù)進(jìn)行排序，直到整個(gè)序列有序。
快速排序的示例：
（a）一趟排序的過(guò)程：
（b）排序的全過(guò)程
算法的實(shí)現(xiàn)：
?遞歸實(shí)現(xiàn)：
[cpp] view plaincopyprint?
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;??????????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<<"結(jié)果：";??????print(a,10);????}?? 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]; //基準(zhǔn)元素while(low < high){ //從表的兩端交替地向中間掃描while(low < high && a[high] >= privotKey) --high; //從high 所指位置向前搜索，至多到low+1 位置。將比基準(zhǔn)元素小的交換到低端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); //遞歸對(duì)低子表遞歸排序quickSort(a, privotLoc + 1, high); //遞歸對(duì)高子表遞歸排序}
}int main(){int a[10] = {3,1,5,7,2,4,9,6,10,8};cout<<"初始值：";print(a,10);quickSort(a,0,9);cout<<"結(jié)果：";print(a,10);}
分析：
快速排序是通常被認(rèn)為在同數(shù)量級(jí)（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按關(guān)鍵碼有序或基本有序時(shí)，快排序反而蛻化為冒泡排序。為改進(jìn)之，通常以“三者取中法”來(lái)選取基準(zhǔn)記錄，即將排序區(qū)間的兩個(gè)端點(diǎn)與中點(diǎn)三個(gè)記錄關(guān)鍵碼居中的調(diào)整為支點(diǎn)記錄。快速排序是一個(gè)不穩(wěn)定的排序方法。
? 快速排序的改進(jìn)
在本改進(jìn)算法中,只對(duì)長(zhǎng)度大于k的子序列遞歸調(diào)用快速排序,讓原序列基本有序，然后再對(duì)整個(gè)基本有序序列用插入排序算法排序。實(shí)踐證明，改進(jìn)后的算法時(shí)間復(fù)雜度有所降低，且當(dāng)k取值為? 8 左右時(shí),改進(jìn)算法的性能最佳。算法思想如下：
[cpp] view plaincopyprint?
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;?????????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?)?{?????????int?pivot?=?partition(r,?low,?high);?????????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);??????????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<<"結(jié)果：";??????print(a,10);????}?? 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]; //基準(zhǔn)元素while(low < high){ //從表的兩端交替地向中間掃描while(low < high && a[high] >= privotKey) --high; //從high 所指位置向前搜索，至多到low+1 位置。將比基準(zhǔn)元素小的交換到低端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 ) { //長(zhǎng)度大于k時(shí)遞歸, k為指定的數(shù)int pivot = partition(r, low, high); // 調(diào)用的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);//先調(diào)用改進(jìn)算法Qsort使之基本有序//再用插入排序?qū)居行蛐蛄信判騠or(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<<"結(jié)果：";print(a,10);}
?
7. 歸并排序（Merge Sort）
?
基本思想：
歸并（Merge）排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。
歸并排序示例：
?
?
合并方法：
設(shè)r[i…n]由兩個(gè)有序子表r[i…m]和r[m+1…n]組成，兩個(gè)子表長(zhǎng)度分別為n-i +1、n-m。
j=m+1；k=i；i=i; //置兩個(gè)子表的起始下標(biāo)及輔助數(shù)組的起始下標(biāo)若i>m 或j>n，轉(zhuǎn)⑷ //其中一個(gè)子表已合并完，比較選取結(jié)束//選取r[i]和r[j]較小的存入輔助數(shù)組rf 如果r[i]<r[j]，rf[k]=r[i]； i++； k++； 轉(zhuǎn)⑵ 否則，rf[k]=r[j]； j++； k++； 轉(zhuǎn)⑵//將尚未處理完的子表中元素存入rf 如果i<=m，將r[i…m]存入rf[k…n] //前一子表非空 如果j<=n , ?將r[j…n] 存入rf[k…n] //后一子表非空合并結(jié)束。 [cpp] view plaincopyprint?
void?Merge(ElemType?*r,ElemType?*rf,?int?i,?int?m,?int?n)??{??????int?j,k;??????for(j=m+1,k=i;?i<=m?&&?j?<=n?;?++k){??????????if(r[j]?<?r[i])?rf[k]?=?r[j++];??????????else?rf[k]?=?r[i++];??????}??????while(i?<=?m)??rf[k++]?=?r[i++];??????while(j?<=?n)??rf[k++]?=?r[j++];??}?? //將r[i…m]和r[m +1 …n]歸并到輔助數(shù)組rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{int j,k;for(j=m+1,k=i; i<=m && j <=n ; ++k){if(r[j] < r[i]) rf[k] = r[j++];else rf[k] = r[i++];}while(i <= m) rf[k++] = r[i++];while(j <= n) rf[k++] = r[j++];
}
歸并的迭代算法
?
1 個(gè)元素的表總是有序的。所以對(duì)n 個(gè)元素的待排序列，每個(gè)元素可看成1 個(gè)有序子表。對(duì)子表兩兩合并生成n/2個(gè)子表，所得子表除最后一個(gè)子表長(zhǎng)度可能為1 外，其余子表長(zhǎng)度均為2。再進(jìn)行兩兩合并，直到生成n 個(gè)元素按關(guān)鍵碼有序的表。
[cpp] view plaincopyprint?
void?print(int?a[],?int?n){??????for(int?j=?0;?j<n;?j++){??????????cout<<a[j]?<<"??";??????}??????cout<<endl;??}????void?Merge(ElemType?*r,ElemType?*rf,?int?i,?int?m,?int?n)??{??????int?j,k;??????for(j=m+1,k=i;?i<=m?&&?j?<=n?;?++k){??????????if(r[j]?<?r[i])?rf[k]?=?r[j++];??????????else?rf[k]?=?r[i++];??????}??????while(i?<=?m)??rf[k++]?=?r[i++];??????while(j?<=?n)??rf[k++]?=?r[j++];??????print(rf,n+1);??}????void?MergeSort(ElemType?*r,?ElemType?*rf,?int?lenght)??{???????int?len?=?1;??????ElemType?*q?=?r?;??????ElemType?*tmp?;??????while(len?<?lenght)?{??????????int?s?=?len;??????????len?=?2?*?s?;??????????int?i?=?0;??????????while(i+?len?<lenght){??????????????Merge(q,?rf,??i,?i+?s-1,?i+?len-1?);?????????????i?=?i+?len;??????????}??????????if(i?+?s?<?lenght){??????????????Merge(q,?rf,??i,?i+?s?-1,?lenght?-1);?????????}??????????tmp?=?q;?q?=?rf;?rf?=?tmp;?????}??}??????int?main(){??????int?a[10]?=?{3,1,5,7,2,4,9,6,10,8};??????int?b[10];??????MergeSort(a,?b,?10);??????print(b,10);??????cout<<"結(jié)果：";??????print(a,10);????}?? void print(int a[], int n){for(int j= 0; j<n; j++){cout<<a[j] <<" ";}cout<<endl;
}//將r[i…m]和r[m +1 …n]歸并到輔助數(shù)組rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{int j,k;for(j=m+1,k=i; i<=m && j <=n ; ++k){if(r[j] < r[i]) rf[k] = r[j++];else rf[k] = r[i++];}while(i <= m) rf[k++] = r[i++];while(j <= n) rf[k++] = r[j++];print(rf,n+1);
}void MergeSort(ElemType *r, ElemType *rf, int lenght)
{ int len = 1;ElemType *q = r ;ElemType *tmp ;while(len < lenght) {int s = len;len = 2 * s ;int i = 0;while(i+ len <lenght){Merge(q, rf, i, i+ s-1, i+ len-1 ); //對(duì)等長(zhǎng)的兩個(gè)子表合并i = i+ len;}if(i + s < lenght){Merge(q, rf, i, i+ s -1, lenght -1); //對(duì)不等長(zhǎng)的兩個(gè)子表合并}tmp = q; q = rf; rf = tmp; //交換q,rf，以保證下一趟歸并時(shí)，仍從q 歸并到rf}
}int main(){int a[10] = {3,1,5,7,2,4,9,6,10,8};int b[10];MergeSort(a, b, 10);print(b,10);cout<<"結(jié)果：";print(a,10);}
兩路歸并的遞歸算法
[cpp] view plaincopyprint?
void?MSort(ElemType?*r,?ElemType?*rf,int?s,?int?t)??{???????ElemType?*rf2;??????if(s==t)?r[s]?=?rf[s];??????else??????{???????????int?m=(s+t)/2;??????????????????MSort(r,?rf2,?s,?m);????????????????MSort(r,?rf2,?m+1,?t);??????????????Merge(rf2,?rf,?s,?m+1,t);???????}??}??void?MergeSort_recursive(ElemType?*r,?ElemType?*rf,?int?n)??{???????MSort(r,?rf,0,?n-1);??}?? void MSort(ElemType *r, ElemType *rf,int s, int t)
{ ElemType *rf2;if(s==t) r[s] = rf[s];else{ int m=(s+t)/2; /*平分*p 表*/MSort(r, rf2, s, m); /*遞歸地將p[s…m]歸并為有序的p2[s…m]*/MSort(r, rf2, m+1, t); /*遞歸地將p[m+1…t]歸并為有序的p2[m+1…t]*/Merge(rf2, rf, s, m+1,t); /*將p2[s…m]和p2[m+1…t]歸并到p1[s…t]*/}
}
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)
{ /*對(duì)順序表*p 作歸并排序*/MSort(r, rf,0, n-1);
}
8. 桶排序/基數(shù)排序(Radix Sort)
說(shuō)基數(shù)排序之前，我們先說(shuō)桶排序：
基本思想：是將陣列分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞回方式繼續(xù)使用桶排序進(jìn)行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的陣列內(nèi)的數(shù)值是均勻分配的時(shí)候，桶排序使用線性時(shí)間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。 ???????? 簡(jiǎn)單來(lái)說(shuō)，就是把數(shù)據(jù)分組，放在一個(gè)個(gè)的桶中，然后對(duì)每個(gè)桶里面的在進(jìn)行排序。 ?
?
?例如要對(duì)大小為[1..1000]范圍內(nèi)的n個(gè)整數(shù)A[1..n]排序 ?
?首先，可以把桶設(shè)為大小為10的范圍，具體而言，設(shè)集合B[1]存儲(chǔ)[1..10]的整數(shù)，集合B[2]存儲(chǔ) ? (10..20]的整數(shù)，……集合B[i]存儲(chǔ)( ? (i-1)*10, ? i*10]的整數(shù)，i ? = ? 1,2,..100。總共有? 100個(gè)桶。 ?
? 然后，對(duì)A[1..n]從頭到尾掃描一遍，把每個(gè)A[i]放入對(duì)應(yīng)的桶B[j]中。? 再對(duì)這100個(gè)桶中每個(gè)桶里的數(shù)字排序，這時(shí)可用冒泡，選擇，乃至快排，一般來(lái)說(shuō)任? 何排序法都可以。
? 最后，依次輸出每個(gè)桶里面的數(shù)字，且每個(gè)桶中的數(shù)字從小到大輸出，這? 樣就得到所有數(shù)字排好序的一個(gè)序列了。 ?
? 假設(shè)有n個(gè)數(shù)字，有m個(gè)桶，如果數(shù)字是平均分布的，則每個(gè)桶里面平均有n/m個(gè)數(shù)字。如果 ?
? 對(duì)每個(gè)桶中的數(shù)字采用快速排序，那么整個(gè)算法的復(fù)雜度是 ?
? O(n?? + ? m ? * ? n/m*log(n/m)) ? = ? O(n?? + ? nlogn ? - ? nlogm) ?
? 從上式看出，當(dāng)m接近n的時(shí)候，桶排序復(fù)雜度接近O(n) ?
? 當(dāng)然，以上復(fù)雜度的計(jì)算是基于輸入的n個(gè)數(shù)字是平均分布這個(gè)假設(shè)的。這個(gè)假設(shè)是很強(qiáng)的? ，實(shí)際應(yīng)用中效果并沒有這么好。如果所有的數(shù)字都落在同一個(gè)桶中，那就退化成一般的排序了。??
??????? 前面說(shuō)的幾大排序算法 ，大部分時(shí)間復(fù)雜度都是O（n2），也有部分排序算法時(shí)間復(fù)雜度是O(nlogn)。而桶式排序卻能實(shí)現(xiàn)O（n）的時(shí)間復(fù)雜度。但桶排序的缺點(diǎn)是：
??????? 1）首先是空間復(fù)雜度比較高，需要的額外開銷大。排序有兩個(gè)數(shù)組的空間開銷，一個(gè)存放待排序數(shù)組，一個(gè)就是所謂的桶，比如待排序值是從0到m-1，那就需要m個(gè)桶，這個(gè)桶數(shù)組就要至少m個(gè)空間。
??????? 2）其次待排序的元素都要在一定的范圍內(nèi)等等。
?????? 桶式排序是一種分配排序。分配排序的特定是不需要進(jìn)行關(guān)鍵碼的比較，但前提是要知道待排序列的一些具體情況。
?
分配排序的基本思想：說(shuō)白了就是進(jìn)行多次的桶式排序。
基數(shù)排序過(guò)程無(wú)須比較關(guān)鍵字，而是通過(guò)“分配”和“收集”過(guò)程來(lái)實(shí)現(xiàn)排序。它們的時(shí)間復(fù)雜度可達(dá)到線性階：O(n)。
實(shí)例:
撲克牌中52 張牌，可按花色和面值分成兩個(gè)字段，其大小關(guān)系為： 花色： 梅花< 方塊< 紅心< 黑心 ? 面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A
若對(duì)撲克牌按花色、面值進(jìn)行升序排序，得到如下序列：
即兩張牌，若花色不同，不論面值怎樣，花色低的那張牌小于花色高的，只有在同花色情況下，大小關(guān)系才由面值的大小確定。這就是多關(guān)鍵碼排序。
為得到排序結(jié)果，我們討論兩種排序方法。 方法1：先對(duì)花色排序，將其分為4 個(gè)組，即梅花組、方塊組、紅心組、黑心組。再對(duì)每個(gè)組分別按面值進(jìn)行排序，最后，將4 個(gè)組連接起來(lái)即可。 方法2：先按13 個(gè)面值給出13 個(gè)編號(hào)組(2 號(hào)，3 號(hào)，...，A 號(hào))，將牌按面值依次放入對(duì)應(yīng)的編號(hào)組，分成13 堆。再按花色給出4 個(gè)編號(hào)組(梅花、方塊、紅心、黑心)，將2號(hào)組中牌取出分別放入對(duì)應(yīng)花色組，再將3 號(hào)組中牌取出分別放入對(duì)應(yīng)花色組，……，這樣，4 個(gè)花色組中均按面值有序，然后，將4 個(gè)花色組依次連接起來(lái)即可。
設(shè)n 個(gè)元素的待排序列包含d 個(gè)關(guān)鍵碼{k1，k2，…，kd}，則稱序列對(duì)關(guān)鍵碼{k1，k2，…，kd}有序是指：對(duì)于序列中任兩個(gè)記錄r[i]和r[j](1≤i≤j≤n)都滿足下列有序關(guān)系：
?????????????????????????????????????????????????? ???????????
其中k1 稱為最主位關(guān)鍵碼，kd 稱為最次位關(guān)鍵碼?????。
?
兩種多關(guān)鍵碼排序方法：
多關(guān)鍵碼排序按照從最主位關(guān)鍵碼到最次位關(guān)鍵碼或從最次位到最主位關(guān)鍵碼的順序逐次排序，分兩種方法：
最高位優(yōu)先(Most Significant Digit first)法，簡(jiǎn)稱MSD 法：
1）先按k1 排序分組，將序列分成若干子序列，同一組序列的記錄中，關(guān)鍵碼k1 相等。
2）再對(duì)各組按k2 排序分成子組，之后，對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd 對(duì)各子組排序后。
3）再將各組連接起來(lái)，便得到一個(gè)有序序列。撲克牌按花色、面值排序中介紹的方法一即是MSD 法。
最低位優(yōu)先(Least Significant Digit first)法，簡(jiǎn)稱LSD 法：
1) 先從kd 開始排序，再對(duì)kd-1進(jìn)行排序，依次重復(fù)，直到按k1排序分組分成最小的子序列后。
2) 最后將各個(gè)子序列連接起來(lái)，便可得到一個(gè)有序的序列, 撲克牌按花色、面值排序中介紹的方法二即是LSD 法。
?
基于LSD方法的鏈?zhǔn)交鶖?shù)排序的基本思想
“多關(guān)鍵字排序”的思想實(shí)現(xiàn)“單關(guān)鍵字排序”。對(duì)數(shù)字型或字符型的單關(guān)鍵字，可以看作由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，此時(shí)可以采用“分配-收集”的方法進(jìn)行排序，這一過(guò)程稱作基數(shù)排序法，其中每個(gè)數(shù)字或字符可能的取值個(gè)數(shù)稱為基數(shù)。比如，撲克牌的花色基數(shù)為4，面值基數(shù)為13。在整理?yè)淇伺茣r(shí)，既可以先按花色整理，也可以先按面值整理。按花色整理時(shí)，先按紅、黑、方、花的順序分成4摞（分配），再按此順序再疊放在一起（收集），然后按面值的順序分成13摞（分配），再按此順序疊放在一起（收集），如此進(jìn)行二次分配和收集即可將撲克牌排列有序。? ?
基數(shù)排序:
是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序。最后的次序就是高優(yōu)先級(jí)高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前。基數(shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。
算法實(shí)現(xiàn)：
[cpp] view plaincopyprint?
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++;???}??}?? Void RadixSort(Node L[],length,maxradix)
{int m,n,k,lsp;k=1;m=1;int temp[10][length-1];Empty(temp); //清空臨時(shí)空間while(k<maxradix) //遍歷所有關(guān)鍵字{for(int i=0;i<length;i++) //分配過(guò)程{if(L[i]<m)Temp[0][n]=L[i];elseLsp=(L[i]/m)%10; //確定關(guān)鍵字Temp[lsp][n]=L[i];n++;}CollectElement(L,Temp); //收集n=0;m=m*10;k++;}
}
?
?
?
?
總結(jié)
各種排序的穩(wěn)定性，時(shí)間復(fù)雜度和空間復(fù)雜度總結(jié)：
?我們比較時(shí)間復(fù)雜度函數(shù)的情況：
?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?時(shí)間復(fù)雜度函數(shù)O(n)的增長(zhǎng)情況
所以對(duì)n較大的排序記錄。一般的選擇都是時(shí)間復(fù)雜度為O(nlog2n)的排序方法。
?
時(shí)間復(fù)雜度來(lái)說(shuō)：
(1)平方階(O(n2))排序 各類簡(jiǎn)單排序:直接插入、直接選擇和冒泡排序； ?(2)線性對(duì)數(shù)階(O(nlog2n))排序 快速排序、堆排序和歸并排序； ?(3)O(n1+§))排序,§是介于0和1之間的常數(shù)。
?????? 希爾排序 (4)線性階(O(n))排序 基數(shù)排序，此外還有桶、箱排序。
說(shuō)明：
當(dāng)原表有序或基本有序時(shí)，直接插入排序和冒泡排序?qū)⒋蟠鬁p少比較次數(shù)和移動(dòng)記錄的次數(shù)，時(shí)間復(fù)雜度可降至O（n）；
而快速排序則相反，當(dāng)原表基本有序時(shí)，將蛻化為冒泡排序，時(shí)間復(fù)雜度提高為O（n2）；
原表是否有序，對(duì)簡(jiǎn)單選擇排序、堆排序、歸并排序和基數(shù)排序的時(shí)間復(fù)雜度影響不大。
?
穩(wěn)定性：
排序算法的穩(wěn)定性:若待排序的序列中，存在多個(gè)具有相同關(guān)鍵字的記錄，經(jīng)過(guò)排序， 這些記錄的相對(duì)次序保持不變，則稱該算法是穩(wěn)定的；若經(jīng)排序后，記錄的相對(duì) 次序發(fā)生了改變，則稱該算法是不穩(wěn)定的。? ???? 穩(wěn)定性的好處：排序算法如果是穩(wěn)定的，那么從一個(gè)鍵上排序，然后再?gòu)牧硪粋€(gè)鍵上排序，第一個(gè)鍵排序的結(jié)果可以為第二個(gè)鍵排序所用。基數(shù)排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時(shí)是不會(huì)改變的。另外，如果排序算法穩(wěn)定，可以避免多余的比較；
穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序
不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序
?
選擇排序算法準(zhǔn)則：
每種排序算法都各有優(yōu)缺點(diǎn)。因此，在實(shí)用時(shí)需根據(jù)不同情況適當(dāng)選用，甚至可以將多種方法結(jié)合起來(lái)使用。
選擇排序算法的依據(jù)
影響排序的因素有很多，平均時(shí)間復(fù)雜度低的算法并不一定就是最優(yōu)的。相反，有時(shí)平均時(shí)間復(fù)雜度高的算法可能更適合某些特殊情況。同時(shí)，選擇算法時(shí)還得考慮它的可讀性，以利于軟件的維護(hù)。一般而言，需要考慮的因素有以下四點(diǎn)：
1．待排序的記錄數(shù)目n的大小；
2．記錄本身數(shù)據(jù)量的大小，也就是記錄中除關(guān)鍵字外的其他信息量的大小；
3．關(guān)鍵字的結(jié)構(gòu)及其分布情況；
4．對(duì)排序穩(wěn)定性的要求。
設(shè)待排序元素的個(gè)數(shù)為n.
1）當(dāng)n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。
?? 快速排序：是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短； ?????? 堆排序 ：? 如果內(nèi)存空間允許且要求穩(wěn)定性的，
?????? 歸并排序：它有一定數(shù)量的數(shù)據(jù)移動(dòng)，所以我們可能過(guò)與插入排序組合，先獲得一定長(zhǎng)度的序列，然后再合并，在效率上將有所提高。
2）? 當(dāng)n較大，內(nèi)存空間允許，且要求穩(wěn)定性 =》歸并排序
3）當(dāng)n較小，可采用直接插入或直接選擇排序。
??? 直接插入排序：當(dāng)元素分布有序，直接插入排序?qū)⒋蟠鬁p少比較次數(shù)和移動(dòng)記錄的次數(shù)。
??? 直接選擇排序 ：元素分布有序，如果不要求穩(wěn)定性，選擇直接選擇排序
5）一般不使用或不直接使用傳統(tǒng)的冒泡排序。
6）基數(shù)排序 它是一種穩(wěn)定的排序算法，但有一定的局限性： 1、關(guān)鍵字可分解。 2、記錄的關(guān)鍵字位數(shù)較少，如果密集更好 3、如果是數(shù)字時(shí)，最好是無(wú)符號(hào)的，否則將增加相應(yīng)的映射復(fù)雜度，可先將其正負(fù)分開排序。
轉(zhuǎn)載于:https://www.cnblogs.com/openeim/p/3921645.html
總結(jié)
以上是生活随笔為你收集整理的九大排序算法，你会几个？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
