各種排序方法復雜度總結
在C中，排序算法是最基本最常用的算法，不同的排序算法在不同的場(chǎng)景或應用中會(huì )有不同的表現，接下來(lái)小編搜集了各種排序方法復雜度總結，歡迎查看。
一、冒泡排序
主要思路是：
通過(guò)交換相鄰的兩個(gè)數變成小數在前大數在后，這樣每次遍歷后，最大的數就“沉”到最后面了。重復N次即可以使數組有序。
代碼實(shí)現
void bubble_sort（int arr[]， int len）
{
for （int i = 0; i < len — 1; i++）
{
for （int j = len — 1; j >= i; j——）
{
if （arr[j] < arr[j — 1]）
{
int temp = arr[j];
arr[j] = arr[j — 1];
arr[j — 1] = temp;
}
}
}
}
冒泡排序改進(jìn)1：
在某次遍歷中，如果沒(méi)有數據交換，說(shuō)明整個(gè)數組已經(jīng)有序，因此通過(guò)設置標志位來(lái)記錄此次遍歷有無(wú)數據交換就可以判斷是否要繼續循環(huán)。
冒泡排序改進(jìn)2：
記錄某次遍歷時(shí)最后發(fā)生數據交換的位置，這個(gè)位置之后的數據顯然已經(jīng)有序。因此設置標志位記錄每次遍歷中最后發(fā)生數據交換的位置可以確定下次循環(huán)的范圍。
二、直接插入排序
主要思路是：
每次將一個(gè)待排序的'數組元素，插入到前面已排序的序列中這個(gè)元素應該在的位置，直到全部數據插入完成。類(lèi)似撲克牌洗牌過(guò)程。
代碼實(shí)現
void _sort（int arr[]， int len）
{
for （int i = 1; i < len; i ++）
{
int j = i — 1;
int k = arr[i];
while （j > —1 && k < arr[j] ）
{
arr[j + 1] = arr[j];
j ——;
}
arr[j + 1] = k;
}
}
三、直接選擇排序
主要思路是：
數組分成有序區和無(wú)序區，初始時(shí)整個(gè)數組都是無(wú)序區，每次遍歷都從無(wú)序區選擇一個(gè)最小的元素直接放在有序區最后，直到排序完成。
代碼實(shí)現
void select_sort（int arr[]， int len）
{
for （int i = 0; i < len; i++）
{
int index = i;
for （int j = i + 1; j < len; j++）
{
if （arr[j] < arr[index]）
index = j;
}
if （index ！= i）
{
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
}
四、快速排序
主要思路是：
“挖坑填數 + 分治法”，首先令i = L;j = R；將a[i]挖出形成打一個(gè)坑，稱(chēng)a[i]為基準數。然后j——從后向前找到一個(gè)比基準數小的數，挖出來(lái)填到a[i]的坑中，這樣a[j]就形成了一個(gè)新的坑，再i++從前向后找到一個(gè)比基準數大的數填到a[j]坑中。重復進(jìn)行這種挖坑填數，直到i = j。這時(shí)a[i]形成了一個(gè)新的坑，將基數填到a[i]坑中，這樣i之前的數都比基準數小，i之后的數都比基準數大。因此將數組分成兩部分再分別重復上述步驟就完成了排序。
代碼實(shí)現
void quick_sort（int arr[]， int left， int right）
{
if （left < right）
{
int i = left， j = right， target = arr[left];
while （i < j）
{
while （i < j && arr[j] > target）
j——;
if （i < j）
arr[i++] = arr[j];
while （i < j && arr[i] < target）
i++;
if （i < j）
arr[j] = arr[i];
}
arr[i] = target;
quick_sort（arr， left， i — 1）;
quick_sort（arr， i + 1， right）;
}
}
五、希爾排序
主要思路是：
先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個(gè)序列中的元素基本有序（增量足夠�。⿻r(shí)，再對全體元素進(jìn)行一次直接插入排序。由于希爾排序是對相隔若干距離的數據進(jìn)行直接插入排序，因此可以形象的稱(chēng)希爾排序為“跳著(zhù)插”。
六、歸并排序
主要思路是：
當一個(gè)數組左邊有序，右邊也有序，那合并這兩個(gè)有序數組就完成了排序。如何讓左右兩邊有序了？用遞歸！這樣遞歸下去，合并上來(lái)就是歸并排序。
代碼實(shí)現
void merge（int arr[]， int temp_arr[]， int start_index， int mid_index， int end_index）
{
int i = start_index， j = mid_index + 1;
int k = 0;
while （i < mid_index + 1 && j < end_index + 1）
{
if （arr[i] > arr[j]）
temp_arr[k++] = arr[j++];
else
temp_arr[k++] = arr[i++];
}
while （i < mid_index + 1）
{
temp_arr[k++] = arr[i++];
}
while （j < end_index + 1）
temp_arr[k++] = arr[j++];
for （i = 0， j = start_index; j < end_index + 1; i ++， j ++）
arr[j] = temp_arr[i];
}
void merge_sort（int arr[]， int temp_arr[]， int start_index， int end_index）
{
if （start_index < end_index）
{
int mid_index = （start_index + end_index） / 2;
merge_sort（arr， temp_arr， start_index， mid_index）;
merge_sort（arr， temp_arr， mid_index + 1， end_index）;
merge（arr， temp_arr， start_index， mid_index， end_index）;
}
}
七、堆排序
堆排序的難點(diǎn)就在于堆的的插入和刪除。
堆的插入就是——每次插入都是將新數據放在數組最后，而從這個(gè)新數據的父結點(diǎn)到根結點(diǎn)必定是一個(gè)有序的數列，因此只要將這個(gè)新數據插入到這個(gè)有序數列中即可。
堆的刪除就是——堆的刪除就是將最后一個(gè)數據的值賦給根結點(diǎn)，然后再從根結點(diǎn)開(kāi)始進(jìn)行一次從上向下的調整。調整時(shí)先在左右兒子結點(diǎn)中找最小的，如果父結點(diǎn)比這個(gè)最小的子結點(diǎn)還小說(shuō)明不需要調整了，反之將父結點(diǎn)和它交換后再考慮后面的結點(diǎn)。相當于從根結點(diǎn)開(kāi)始將一個(gè)數據在有序數列中進(jìn)行“下沉”。
因此，堆的插入和刪除非常類(lèi)似直接插入排序，只不是在二叉樹(shù)上進(jìn)行插入過(guò)程。所以可以將堆排序形容為“樹(shù)上插”。
【各種排序方法復雜度總結】相關(guān)文章：
《排序》優(yōu)秀教案課件05-16
排序和篩選說(shuō)課稿11-04
《有趣的排序》教學(xué)設計02-09
高中英語(yǔ)各種文體的寫(xiě)作練習方法和要素分析08-23
用各種方法巧妙抒發(fā)感情的小學(xué)寫(xiě)作技巧06-10
各種圖形剪紙貼畫(huà)03-21
各種分類(lèi)佳句摘抄05-28
元旦各種飲食習俗01-04
各種道歉信01-05