本期是C++基礎(chǔ)語(yǔ)法分享的第十六節(jié)，今天給大家來梳理一下十大排序算法后五個(gè)！

歸并排序

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

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

///整數(shù)或浮點(diǎn)數(shù)皆可使用，若要使用物件（class）時(shí)必須設(shè)定“小於”（《）的運(yùn)算子功能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］;}//整數(shù)或浮點(diǎn)數(shù)皆可使用，若要使用物件（class）時(shí)必須設(shè)定“小於”（《）的運(yùn)算子功能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;}

希爾排序

希爾排序：每一輪按照事先決定的間隔進(jìn)行插入排序，間隔會(huì)依次縮小，最后一次一定要是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; }}

計(jì)數(shù)排序

計(jì)數(shù)排序：統(tǒng)計(jì)小于等于該元素值的元素的個(gè)數(shù)i，于是該元素就放在目標(biāo)數(shù)組的索引i位（i≥0）。

計(jì)數(shù)排序基于一個(gè)假設(shè)，待排序數(shù)列的所有數(shù)均為整數(shù)，且出現(xiàn)在（0，k）的區(qū)間之內(nèi)。

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

計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。

時(shí)間復(fù)雜度為 O（n+k），空間復(fù)雜度為 O（n+k）

算法的步驟如下：

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

2. 統(tǒng)計(jì)數(shù)組中每個(gè)值為 i 的元素出現(xiàn)的次數(shù)，存入數(shù)組 C 的第 i 項(xiàng)

3. 對(duì)所有的計(jì)數(shù)累加（從 C 中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加）

4. 反向填充目標(biāo)數(shù)組：將每個(gè)元素 i 放在新數(shù)組的第 C［i］ 項(xiàng)，每放一個(gè)元素就將 C［i］ 減去 1

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

using namespace std;

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

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

// 統(tǒng)計(jì)每個(gè)鍵值出現(xiàn)的次數(shù) for （int i = 0; i 《 vecRaw.size（）; i++） vecCount［vecRaw［i］］++; // 后面的鍵值出現(xiàn)的位置為前面所有鍵值出現(xiàn)的次數(shù)之和 for （int i = 1; i 《 vecCountLength; i++） vecCount［i］ += vecCount［i - 1］;

// 將鍵值放到目標(biāo)位置 for （int i = vecRaw.size（）; i 》 0; i--） // 此處逆序是為了保持相同鍵值的穩(wěn)定性 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號(hào)桶，最后依次把桶里的元素倒出來。

桶排序序思路：

1. 設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子。

2. 尋訪序列，并且把項(xiàng)目一個(gè)一個(gè)放到對(duì)應(yīng)的桶子去。

3. 對(duì)每個(gè)不是空的桶子進(jìn)行排序。

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

假設(shè)數(shù)據(jù)分布在［0，100）之間，每個(gè)桶內(nèi)部用鏈表表示，在數(shù)據(jù)入桶的同時(shí)插入排序，然后把各個(gè)桶中的數(shù)據(jù)合并。

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; }}

基數(shù)排序

基數(shù)排序：一種多關(guān)鍵字的排序算法，可用桶排序?qū)崿F(xiàn)。

int maxbit（int data［］， int n） //輔助函數(shù)，求數(shù)據(jù)的最大位數(shù){ int maxData = data［0］; ///《 最大數(shù) /// 先求出最大數(shù)，再求其位數(shù)，這樣有原先依次每個(gè)數(shù)判斷其位數(shù)，稍微優(yōu)化點(diǎn)。 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; //保存最大的位數(shù) 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） //基數(shù)排序{ int d = maxbit（data， n）;

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

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

//將tmp中的位置依次分配給每個(gè)桶 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++） //將臨時(shí)數(shù)組的內(nèi)容復(fù)制到data中 data［j］ = tmp［j］; radix = radix * 10;

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

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

責(zé)任編輯：haq