C++中十大排序算法前五個(gè)詳解

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

冒泡排序

冒泡排序思路：

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

2. 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。

3. 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

4. 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

示例：

void BubbleSort（vector《int》& v） { int len = v.size（）; for （int i = 0; i 《 len - 1; ++i） for （int j = 0; j 《 len - 1 - i; ++j） if （v［j］ 》 v［j + 1］） swap（v［j］， v［j + 1］）;}

// 模板實(shí)現(xiàn)冒泡排序template《typename T》 //整數(shù)或浮點(diǎn)數(shù)皆可使用，若要使用物件（class）時(shí)必須設(shè)定大於（》）的運(yùn)算子功能void bubble_sort（T arr［］， int len） { for （int i = 0; i 《 len - 1; i++） for （int j = 0; j 《 len - 1 - i; j++） if （arr［j］ 》 arr［j + 1］） swap（arr［j］， arr［j + 1］）;}

// 冒泡排序（改進(jìn)版）void BubbleSort_orderly（vector《int》& v） { int len = v.size（）; bool orderly = false; for （int i = 0; i 《 len - 1 && ！orderly; ++i） { orderly = true; for （int j = 0; j 《 len - 1 - i; ++j） { if （v［j］ 》 v［j + 1］） { // 從小到大 orderly = false; // 發(fā)生交換則仍非有序 swap（v［j］， v［j + 1］）;

} } }}

選擇排序

選擇排序思路：

1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

2. 從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾

3. 以此類推，直到所有元素均排序完畢

示例：

void SelectionSort（vector《int》& v） { int min， len = v.size（）; for （int i = 0; i 《 len - 1; ++i） { min = i; for （int j = i + 1; j 《 len; ++j） { if （v［j］ 《 v［min］） { // 標(biāo)記最小的 min = j; } } if （i ！= min） // 交換到前面 swap（v［i］， v［min］）; }}

// 模板實(shí)現(xiàn)template《typename T》 void Selection_Sort（std：：vector《T》& arr） { int len = arr.size（）;

for （int i = 0; i 《 len - 1; i++） { int min = i; for （int j = i + 1; j 《 len; j++） if （arr［j］ 《 arr［min］） min = j; if（i ！= min） std：：swap（arr［i］， arr［min］）; }}

插入排序

插入排序思路：

1. 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序

2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描

3. 如果該元素（已排序）大于新元素，將該元素移到下一位置

4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置

5. 將新元素插入到該位置后

6. 重復(fù)步驟2~5

示例：

void InsertSort（vector《int》& v）{ int len = v.size（）; for （int i = 1; i 《 len; ++i） { int temp = v［i］; for（int j = i - 1;

j 》= 0; --j） { if（v［j］ 》 temp） { v［j + 1］ = v［j］; v［j］ = temp; } else break; } }}

快速排序

快速排序思路：

1. 選取第一個(gè)數(shù)為基準(zhǔn)

2. 將比基準(zhǔn)小的數(shù)交換到前面，比基準(zhǔn)大的數(shù)交換到后面

3. 對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)

void QuickSort（vector《int》& v， int low， int high） { if （low 》= high） // 結(jié)束標(biāo)志 return; int first = low; // 低位下標(biāo) int last = high; // 高位下標(biāo) int key = v［first］; // 設(shè)第一個(gè)為基準(zhǔn)

while （first 《 last） { // 將比第一個(gè)小的移到前面 while （first 《 last && v［last］ 》= key） last--; if （first 《 last） v［first++］ = v［last］;

// 將比第一個(gè)大的移到后面 while （first 《 last && v［first］ 《= key） first++; if （first 《 last） v［last--］ = v［first］; } // 基準(zhǔn)置位 v［first］ = key; // 前半遞歸 QuickSort（v， low， first - 1）; // 后半遞歸 QuickSort（v， first + 1， high）;

}

// ----------------------------------------------------

// 模板實(shí)現(xiàn)快速排序（遞歸）template 《typename T》void quick_sort_recursive（T arr［］， int start， int end） { if （start 》= end） return; T mid = arr［end］;

int left = start， right = end - 1; while （left 《 right） { while （arr［left］ 《 mid && left 《 right） left++; while （arr［right］ 》= mid && left 《 right） right--; std：：swap（arr［left］， arr［right］）; } if （arr［left］ 》= arr［end］） std：：swap（arr［left］， arr［end］）; else left++; quick_sort_recursive（arr， start， left - 1）;

quick_sort_recursive（arr， left + 1， end）;}template 《typename T》 //整數(shù)或浮點(diǎn)數(shù)皆可使用，若要使用物件（class）時(shí)必須設(shè)定“小於”（《）、“大於”（》）、“不小於”（》=）的運(yùn)算子功能void quick_sort（T arr［］， int len） { quick_sort_recursive（arr， 0， len - 1）;}

// ----------------------------------------------------

// 模板實(shí)現(xiàn)快速排序（迭代）struct Range { int start， end; Range（int s = 0， int e = 0） { start = s， end = e;

}};template 《typename T》 // 整數(shù)或浮點(diǎn)數(shù)皆可使用，若要使用物件（class）時(shí)必須設(shè)定“小於”（《）、“大於”（》）、“不小於”（》=）的運(yùn)算子功能void quick_sort（T arr［］， const int len） { if （len 《= 0） return; // 避免len等於負(fù)值時(shí)宣告堆疊陣列當(dāng)機(jī) // r［］模擬堆疊，p為數(shù)量，r［p++］為push，r［--p］為pop且取得元素 Range r［len］;

int p = 0; r［p++］ = Range（0， len - 1）; while （p） { Range range = r［--p］; if （range.start 》= range.end） continue; T mid = arr［range.end］; int left = range.start， right = range.end - 1;

while （left 《 right） { while （arr［left］ 《 mid && left 《 right） left++; while （arr［right］ 》= mid && left 《 right） right--; std：：swap（arr［left］， arr［right］）;

} if （arr［left］ 》= arr［range.end］） std：：swap（arr［left］， arr［range.end］）; else left++; r［p++］ = Range（range.start， left - 1）; r［p++］ = Range（left + 1， range.end）; }}

堆排序

堆排序：（最大堆，有序區(qū)）。從堆頂把根卸出來放在有序區(qū)之前，再恢復(fù)堆。

#include 《iostream》#include 《algorithm》using namespace std;

// 堆排序：（最大堆，有序區(qū)）。從堆頂把根卸出來放在有序區(qū)之前，再恢復(fù)堆。

void max_heapify（int arr［］， int start， int end） { //建立父節(jié)點(diǎn)指標(biāo)和子節(jié)點(diǎn)指標(biāo) int dad = start; int son = dad * 2 + 1; while （son 《= end） {

//若子節(jié)點(diǎn)指標(biāo)在範(fàn)圍內(nèi)才做比較 if （son + 1 《= end && arr［son］ 《 arr［son + 1］）

//先比較兩個(gè)子節(jié)點(diǎn)大小，選擇最大的 son++; if （arr［dad］ 》 arr［son］） //如果父節(jié)點(diǎn)大於子節(jié)點(diǎn)代表調(diào)整完畢，直接跳出函數(shù) return; else { //否則交換父子內(nèi)容再繼續(xù)子節(jié)點(diǎn)和孫節(jié)點(diǎn)比較 swap（arr［dad］， arr［son］）; dad = son; son = dad * 2 + 1; } }}

void heap_sort（int arr［］， int len） { //初始化，i從最後一個(gè)父節(jié)點(diǎn)開始調(diào)整 for （int i = len / 2 - 1; i 》= 0; i--） max_heapify（arr， i， len - 1）;

//先將第一個(gè)元素和已經(jīng)排好的元素前一位做交換，再從新調(diào)整（剛調(diào)整的元素之前的元素），直到排序完畢 for （int i = len - 1; i 》 0; i--） { swap（arr［0］， arr［i］）; max_heapify（arr， 0， i - 1）; }}

int main（） { int arr［］ = { 3， 5， 3， 0， 8， 6， 1， 5， 8， 6， 2， 4， 9， 4， 7， 0， 1， 8， 9， 7， 3， 1， 2， 5， 9， 7， 4， 0， 2， 6 };

int len = （int） sizeof（arr） / sizeof（*arr）; heap_sort（arr， len）; for （int i = 0; i 《 len; i++） cout 《《 arr［i］ 《《 ‘ ’; cout 《《 endl; return 0;}

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

責(zé)任編輯：haq