本期是C++基礎語法分享的第十六節，今天給大家來梳理一下十大排序算法后五個！

歸并排序

歸并排序：把數據分為兩段，從兩段中逐個選最小的元素移入新數據段的末尾。可從上到下或從下到上進行。

/***************** 迭代版*****************

///整數或浮點數皆可使用，若要使用物件（class）時必須設定“小於”（《）的運算子功能template《typename T》void merge_sort（T arr［］， int len） { T* a = arr;

T* b = new T［len］; for （int seg = 1;

seg 《 len; seg += seg） { for （int start = 0; start 《 len; start += seg + seg） { int low = start， mid = min（start + seg， len）， high = min（start + seg + seg， len）;

int k = low; int start1 = low， end1 = mid; int start2 = mid， end2 = high; while （start1 《 end1 && start2 《 end2） b［k++］ = a［start1］ 《 a［start2］ ？ a［start1++］ ： a［start2++］; while （start1 《 end1） b［k++］ = a［start1++］;

while （start2 《 end2） b［k++］ = a［start2++］; } T* temp = a;

a = b; b = temp; } if （a ！= arr） { for （int i = 0; i 《 len; i++） b［i］ = a［i］; b = a;

} delete［］ b;}

/***************** 遞歸版*****************/template《typename T》void merge_sort_recursive（T arr［］， T reg［］， int start， int end） { if （start 》= end） return; int len = end - start， mid = （len 》》 1） + start; int start1 = start， end1 = mid;

int start2 = mid + 1， end2 = end; merge_sort_recursive（arr， reg， start1， end1）; merge_sort_recursive（arr， reg， start2， end2）;

int k = start; while （start1 《= end1 && start2 《= end2） reg［k++］ = arr［start1］ 《 arr［start2］ ？ arr［start1++］ ： arr［start2++］;

while （start1 《= end1） reg［k++］ = arr［start1++］; while （start2 《= end2） reg［k++］ = arr［start2++］;

for （k = start; k 《= end; k++） arr［k］ = reg［k］;}//整數或浮點數皆可使用，若要使用物件（class）時必須設定“小於”（《）的運算子功能template《typename T》 void merge_sort（T arr［］， const int len） { T *reg = new T［len］; merge_sort_recursive（arr， reg， 0， len - 1）; delete［］ reg;}

希爾排序

希爾排序：每一輪按照事先決定的間隔進行插入排序，間隔會依次縮小，最后一次一定要是1。

template《typename T》void shell_sort（T array［］， int length） { int h = 1; while （h 《 length / 3） { h = 3 * h + 1; } while （h 》= 1） { for （int i = h; i 《 length; i++） { for （int j = i; j 》= h && array［j］ 《 array［j - h］; j -= h） { std：：swap（array［j］， array［j - h］）; } } h = h / 3; }}

計數排序

計數排序：統計小于等于該元素值的元素的個數i，于是該元素就放在目標數組的索引i位（i≥0）。

計數排序基于一個假設，待排序數列的所有數均為整數，且出現在（0，k）的區間之內。

如果 k（待排數組的最大值） 過大則會引起較大的空間復雜度，一般是用來排序 0 到 100 之間的數字的最好的算法，但是它不適合按字母順序排序人名。

計數排序不是比較排序，排序的速度快于任何比較排序算法。

時間復雜度為 O（n+k），空間復雜度為 O（n+k）

算法的步驟如下：

1. 找出待排序的數組中最大和最小的元素

2. 統計數組中每個值為 i 的元素出現的次數，存入數組 C 的第 i 項

3. 對所有的計數累加（從 C 中的第一個元素開始，每一項和前一項相加）

4. 反向填充目標數組：將每個元素 i 放在新數組的第 C［i］ 項，每放一個元素就將 C［i］ 減去 1

#include 《iostream》#include 《vector》#include 《algorithm》

using namespace std;

// 計數排序void CountSort（vector《int》& vecRaw， vector《int》& vecObj）{ // 確保待排序容器非空 if （vecRaw.size（） == 0） return;

// 使用 vecRaw 的最大值 + 1 作為計數容器 countVec 的大小 int vecCountLength = （*max_element（begin（vecRaw）， end（vecRaw））） + 1; vector《int》 vecCount（vecCountLength， 0）;

// 統計每個鍵值出現的次數 for （int i = 0; i 《 vecRaw.size（）; i++） vecCount［vecRaw［i］］++; // 后面的鍵值出現的位置為前面所有鍵值出現的次數之和 for （int i = 1; i 《 vecCountLength; i++） vecCount［i］ += vecCount［i - 1］;

// 將鍵值放到目標位置 for （int i = vecRaw.size（）; i 》 0; i--） // 此處逆序是為了保持相同鍵值的穩定性 vecObj［--vecCount［vecRaw［i - 1］］］ = vecRaw［i - 1］;}

int main（）{ vector《int》 vecRaw = { 0，5，7，9，6，3，4，5，2，8，6，9，2，1 }; vector《int》 vecObj（vecRaw.size（）， 0）;

CountSort（vecRaw， vecObj）;

for （int i = 0; i 《 vecObj.size（）; ++i） cout 《《 vecObj［i］ 《《 “ ”; cout 《《 endl;

return 0;}

桶排序

桶排序：將值為i的元素放入i號桶，最后依次把桶里的元素倒出來。

桶排序序思路：

1. 設置一個定量的數組當作空桶子。

2. 尋訪序列，并且把項目一個一個放到對應的桶子去。

3. 對每個不是空的桶子進行排序。

4. 從不是空的桶子里把項目再放回原來的序列中。

假設數據分布在［0，100）之間，每個桶內部用鏈表表示，在數據入桶的同時插入排序，然后把各個桶中的數據合并。

const int BUCKET_NUM = 10;

struct ListNode{ explicit ListNode（int i=0）：mData（i），mNext（NULL）{} ListNode* mNext; int mData;};

ListNode* insert（ListNode* head，int val）{ ListNode dummyNode; ListNode *newNode = new ListNode（val）; ListNode *pre，*curr; dummyNode.mNext = head; pre = &dummyNode; curr = head; while（NULL！=curr && curr-》mData《=val）{ pre = curr; curr = curr-》mNext; } newNode-》mNext = curr; pre-》mNext = newNode; return dummyNode.mNext;}

ListNode* Merge（ListNode *head1，ListNode *head2）{ ListNode dummyNode; ListNode *dummy = &dummyNode; while（NULL！=head1 && NULL！=head2）{ if（head1-》mData 《= head2-》mData）{ dummy-》mNext = head1; head1 = head1-》mNext; }else{ dummy-》mNext = head2; head2 = head2-》mNext; } dummy = dummy-》mNext; } if（NULL！=head1） dummy-》mNext = head1; if（NULL！=head2） dummy-》mNext = head2; return dummyNode.mNext;}

void BucketSort（int n，int arr［］）{ vector《ListNode*》 buckets（BUCKET_NUM，（ListNode*）（0））; for（int i=0;i《n;++i）{ int index = arr［i］/BUCKET_NUM; ListNode *head = buckets.at（index）; buckets.at（index） = insert（head，arr［i］）; } ListNode *head = buckets.at（0）; for（int i=1;i《BUCKET_NUM;++i）{ head = Merge（head，buckets.at（i））; } for（int i=0;i《n;++i）{ arr［i］ = head-》mData; head = head-》mNext; }}

基數排序

基數排序：一種多關鍵字的排序算法，可用桶排序實現。

int maxbit（int data［］， int n） //輔助函數，求數據的最大位數{ int maxData = data［0］; ///《 最大數 /// 先求出最大數，再求其位數，這樣有原先依次每個數判斷其位數，稍微優化點。 for （int i = 1; i 《 n; ++i） { if （maxData 《 data［i］） maxData = data［i］;

} int d = 1;

int p = 10; while （maxData 》= p） { //p *= 10; // Maybe overflow maxData /= 10; ++d; } return d;/* int d = 1; //保存最大的位數 int p = 10; for（int i = 0; i 《 n; ++i） { while（data［i］ 》= p） { p *= 10; ++d;

} } return d;*/}void radixsort（int data［］， int n） //基數排序{ int d = maxbit（data， n）;

int *tmp = new int［n］; int *count = new int［10］;

//計數器 int i， j， k; int radix = 1; for（i = 1; i 《= d; i++） //進行d次排序 { for（j = 0; j 《 10; j++） count［j］ = 0; //每次分配前清空計數器 for（j = 0; j 《 n; j++） { k = （data［j］ / radix） % 10; //統計每個桶中的記錄數 count［k］++; } for（j = 1; j 《 10; j++） count［j］ = count［j - 1］ + count［j］;

//將tmp中的位置依次分配給每個桶 for（j = n - 1; j 》= 0; j--） //將所有桶中記錄依次收集到tmp中 { k = （data［j］ / radix） % 10; tmp［count［k］ - 1］ = data［j］;

count［k］--; } for（j = 0; j 《 n; j++） //將臨時數組的內容復制到data中 data［j］ = tmp［j］; radix = radix * 10;

} delete ［］tmp; delete ［］count;}

今天的分享就到這里了，大家要好好學C++喲~

責任編輯：haq