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