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