排序算法时间复杂度、空间复杂度、稳定性比较
排序算法分類(lèi)
排序算法比較表格填空
| 冒泡排序 | :————-: | :—–: | :—–: | :—–: |
| 選擇排序 | :————-: | :—–: | :—–: | :—–: |
| 直接插入排序 | :————-: | :—–: | :—–: | :—–: |
| 歸并排序 | :————-: | :—–: | :—–: | :—–: |
| 快速排序 | :————-: | :—–: | :—–: | :—–: |
| 堆排序 | :————-: | :—–: | :—–: | :—–: |
| 希爾排序 | :————-: | :—–: | :—–: | :—–: |
| 計(jì)數(shù)排序 | :————-: | :—–: | :—–: | :—–: |
| 基數(shù)排序 | :————-: | :—–: | :—–: | :—–: |
排序算法比較表格
| 冒泡排序 | O（n2）O（n2） | O（n2）O（n2） | O（1）O（1） | 是 |
| 選擇排序 | O（n2）O（n2） | O（n2）O（n2） | O（1）O（1） | 不是 |
| 直接插入排序 | O（n2）O（n2） | O（n2）O（n2） | O（1）O（1） | 是 |
| 歸并排序 | O(nlogn)O(nlogn) | O(nlogn)O(nlogn) | O（n）O（n） | 是 |
| 快速排序 | O(nlogn)O(nlogn) | O（n2）O（n2） | O（logn）O（logn） | 不是 |
| 堆排序 | O(nlogn)O(nlogn) | O(nlogn)O(nlogn) | O（1）O（1） | 不是 |
| 希爾排序 | O(nlogn)O(nlogn) | O（ns）O（ns） | O（1）O（1） | 不是 |
| 計(jì)數(shù)排序 | O(n+k)O(n+k) | O(n+k)O(n+k) | O(n+k)O(n+k) | 是 |
| 基數(shù)排序 | O(N?M)O(N?M) | O(N?M)O(N?M) | O(M)O(M) | 是 |
注：
1 歸并排序可以通過(guò)手搖算法將空間復(fù)雜度降到O（1），但是時(shí)間復(fù)雜度會(huì)提高。
2 基數(shù)排序時(shí)間復(fù)雜度為O（N*M），其中N為數(shù)據(jù)個(gè)數(shù)，M為數(shù)據(jù)位數(shù)。
輔助記憶
- 時(shí)間復(fù)雜度記憶-?
- 冒泡、選擇、直接 排序需要兩個(gè)for循環(huán)，每次只關(guān)注一個(gè)元素，平均時(shí)間復(fù)雜度為O（n2）O（n2）（一遍找元素O(n)O(n)，一遍找位置O(n)O(n)）
- 快速、歸并、希爾、堆基于二分思想，log以2為底，平均時(shí)間復(fù)雜度為O(nlogn)O(nlogn)（一遍找元素O(n)O(n)，一遍找位置O(logn)O(logn)）
- 穩(wěn)定性記憶-“快希選堆”（快犧牲穩(wěn)定性）?
- 排序算法的穩(wěn)定性：排序前后相同元素的相對(duì)位置不變，則稱(chēng)排序算法是穩(wěn)定的；否則排序算法是不穩(wěn)定的。
原理理解
1 冒泡排序
1.1 過(guò)程
冒泡排序從小到大排序：一開(kāi)始交換的區(qū)間為0~N-1，將第1個(gè)數(shù)和第2個(gè)數(shù)進(jìn)行比較，前面大于后面，交換兩個(gè)數(shù)，否則不交換。再比較第2個(gè)數(shù)和第三個(gè)數(shù)，前面大于后面，交換兩個(gè)數(shù)否則不交換。依次進(jìn)行，最大的數(shù)會(huì)放在數(shù)組最后的位置。然后將范圍變?yōu)?~N-2，數(shù)組第二大的數(shù)會(huì)放在數(shù)組倒數(shù)第二的位置。依次進(jìn)行整個(gè)交換過(guò)程，最后范圍只剩一個(gè)數(shù)時(shí)數(shù)組即為有序。
1.2 動(dòng)圖
1.3 核心代碼（函數(shù)）
//array[]為待排序數(shù)組，n為數(shù)組長(zhǎng)度 void BubbleSort(int array[], int n) {int i, j, k;for(i=0; i<n-1; i++)for(j=0; j<n-1-i; j++){if(array[j]>array[j+1]){k=array[j];array[j]=array[j+1];array[j+1]=k;}} }2 選擇排序
2.1 過(guò)程
選擇排序從小到大排序：一開(kāi)始從0~n-1區(qū)間上選擇一個(gè)最小值，將其放在位置0上，然后在1~n-1范圍上選取最小值放在位置1上。重復(fù)過(guò)程直到剩下最后一個(gè)元素，數(shù)組即為有序。
2.2 動(dòng)圖
?
2.3 核心代碼（函數(shù)）
//array[]為待排序數(shù)組，n為數(shù)組長(zhǎng)度 void selectSort(int array[], int n) {int i, j ,min ,k;for( i=0; i<n-1; i++){min=i; //每趟排序最小值先等于第一個(gè)數(shù)，遍歷剩下的數(shù)for( j=i+1; j<n; j++) //從i下一個(gè)數(shù)開(kāi)始檢查{if(array[min]>array[j]){min=j;}}if(min!=i){k=array[min];array[min]=array[i];array[i]=k;}} }3 插入排序
3.1 過(guò)程
插入排序從小到大排序：首先位置1上的數(shù)和位置0上的數(shù)進(jìn)行比較，如果位置1上的數(shù)大于位置0上的數(shù)，將位置0上的數(shù)向后移一位，將1插入到0位置，否則不處理。位置k上的數(shù)和之前的數(shù)依次進(jìn)行比較，如果位置K上的數(shù)更大，將之前的數(shù)向后移位，最后將位置k上的數(shù)插入不滿(mǎn)足條件點(diǎn)，反之不處理。
3.2 動(dòng)圖
?
3.3 核心代碼（函數(shù)）
//array[]為待排序數(shù)組，n為數(shù)組長(zhǎng)度 void insertSort(int array[], int n) {int i,j,temp;for( i=1;i<n;i++){if(array[i]<array[i-1]){temp=array[i];for( j=i;array[j-1]>temp;j--){array[j]=array[j-1];}array[j]=temp;}} }4 歸并排序
4.1 過(guò)程
歸并排序從小到大排序：首先讓數(shù)組中的每一個(gè)數(shù)單獨(dú)成為長(zhǎng)度為1的區(qū)間，然后兩兩一組有序合并，得到長(zhǎng)度為2的有序區(qū)間，依次進(jìn)行，直到合成整個(gè)區(qū)間。
4.2 動(dòng)圖
?
4.3 核心代碼（函數(shù)）
- 遞歸實(shí)現(xiàn)
- 迭代實(shí)現(xiàn)
5 快速排序
5.1 過(guò)程
快速排序從小到大排序：在數(shù)組中隨機(jī)選一個(gè)數(shù)（默認(rèn)數(shù)組首個(gè)元素），數(shù)組中小于等于此數(shù)的放在左邊，大于此數(shù)的放在右邊，再對(duì)數(shù)組兩邊遞歸調(diào)用快速排序，重復(fù)這個(gè)過(guò)程。
5.2 動(dòng)圖
?
5.3 核心代碼（函數(shù)）
推薦程序（好理解）
//接口調(diào)整 void adjust_quicksort(int k[],int n) { quicksort(k,0,n-1); } void quicksort(int a[], int left, int right) { int i,j,t,temp; if(left>right) //（遞歸過(guò)程先寫(xiě)結(jié)束條件）return; temp=a[left]; //temp中存的就是基準(zhǔn)數(shù) i=left; j=right; while(i!=j) { //順序很重要，要先從右邊開(kāi)始找（最后交換基準(zhǔn)時(shí)換過(guò)去的數(shù)要保證比基準(zhǔn)小，因?yàn)榛鶞?zhǔn) //選取數(shù)組第一個(gè)數(shù)，在小數(shù)堆中） while(a[j]>=temp && i<j) j--; //再找右邊的 while(a[i]<=temp && i<j) i++; //交換兩個(gè)數(shù)在數(shù)組中的位置 if(i<j) { t=a[i]; a[i]=a[j]; a[j]=t; } } //最終將基準(zhǔn)數(shù)歸位 （之前已經(jīng)temp=a[left]過(guò)了，交換只需要再進(jìn)行兩步）a[left]=a[i]; a[i]=temp; quicksort(left,i-1);//繼續(xù)處理左邊的，這里是一個(gè)遞歸的過(guò)程 quicksort(i+1,right);//繼續(xù)處理右邊的 ，這里是一個(gè)遞歸的過(guò)程 }6 堆排序
6.1 過(guò)程
堆排序從小到大排序：首先將數(shù)組元素建成大小為n的大頂堆，堆頂（數(shù)組第一個(gè)元素）是所有元素中的最大值，將堆頂元素和數(shù)組最后一個(gè)元素進(jìn)行交換，再將除了最后一個(gè)數(shù)的n-1個(gè)元素建立成大頂堆，再將最大元素和數(shù)組倒數(shù)第二個(gè)元素進(jìn)行交換，重復(fù)直至堆大小減為1。
-
注：完全二叉樹(shù)?
假設(shè)二叉樹(shù)深度為n，除了第n層外，n-1層節(jié)點(diǎn)都有兩個(gè)孩子，第n層節(jié)點(diǎn)連續(xù)從左到右。如下圖? -
注：大頂堆?
大頂堆是具有以下性質(zhì)的完全二叉樹(shù)：每個(gè)節(jié)點(diǎn)的值都大于或等于其左右孩子節(jié)點(diǎn)的值。?
即，根節(jié)點(diǎn)是堆中最大的值，按照層序遍歷給節(jié)點(diǎn)從1開(kāi)始編號(hào)，則節(jié)點(diǎn)之間滿(mǎn)足如下關(guān)系：?
?(1<=i<=n/2)
6.2 動(dòng)圖
?
?
6.3 核心代碼（函數(shù)）
注意！！！數(shù)組從1開(kāi)始，1~n
7 希爾排序
7.1 過(guò)程
希爾排序是插入排序改良的算法，希爾排序步長(zhǎng)從大到小調(diào)整，第一次循環(huán)后面元素逐個(gè)和前面元素按間隔步長(zhǎng)進(jìn)行比較并交換，直至步長(zhǎng)為1，步長(zhǎng)選擇是關(guān)鍵。
7.2 動(dòng)圖
?
7.3 核心程序（函數(shù)）
//下面是插入排序 void InsertSort( int array[], int n) {int i,j,temp;for( i=0;i<n;i++ ){if(array[i]<array[i-1]){temp=array[i];for( j=i-1;array[j]>temp;j--){array[j+1]=array[j];}array[j+1]=temp;}} } //在插入排序基礎(chǔ)上修改得到希爾排序 void SheelSort( int array[], int n) {int i,j,temp;int gap=n; //~~~~~~~~~~~~~~~~~~~~~do{gap=gap/3+1; //~~~~~~~~~~~~~~~~~~for( i=gap;i<n;i++ ){if(array[i]<array[i-gap]){temp=array[i];for( j=i-gap;array[j]>temp;j-=gap){array[j+gap]=array[j];}array[j+gap]=temp;}}}while(gap>1); //~~~~~~~~~~~~~~~~~~~~~~}8 桶排序（基數(shù)排序和基數(shù)排序的思想）
8.1 過(guò)程
桶排序是計(jì)數(shù)排序的變種，把計(jì)數(shù)排序中相鄰的m個(gè)”小桶”放到一個(gè)”大桶”中，在分完桶后，對(duì)每個(gè)桶進(jìn)行排序（一般用快排），然后合并成最后的結(jié)果。
8.2 圖解
8.3 核心程序
#include <stdio.h> int main() {int a[11],i,j,t;for(i=0;i<=10;i++)a[i]=0; //初始化為0for(i=1;i<=5;i++) //循環(huán)讀入5個(gè)數(shù){scanf("%d",&t); //把每一個(gè)數(shù)讀到變量t中a[t]++; //進(jìn)行計(jì)數(shù)(核心行)}for(i=0;i<=10;i++) //依次判斷a[0]~a[10]for(j=1;j<=a[i];j++) //出現(xiàn)了幾次就打印幾次printf("%d ",i);getchar();getchar(); //這里的getchar();用來(lái)暫停程序，以便查看程序輸出的內(nèi)容//也可以用system("pause");等來(lái)代替return 0; }9 計(jì)數(shù)排序
9.1 過(guò)程
算法的步驟如下：?
- 找出待排序的數(shù)組中最大和最小的元素?
- 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)?
- 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加）?
- 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1
9.2 圖解
9.3 核心程序（函數(shù)）
程序1： #define NUM_RANGE (100) //預(yù)定義數(shù)據(jù)范圍上限，即K的值void counting_sort(int *ini_arr, int *sorted_arr, int n) //所需空間為 2*n+k { int *count_arr = (int *)malloc(sizeof(int) * NUM_RANGE); int i, j, k; //初始化統(tǒng)計(jì)數(shù)組元素為值為零 for(k=0; k<NUM_RANGE; k++){ count_arr[k] = 0; } //統(tǒng)計(jì)數(shù)組中，每個(gè)元素出現(xiàn)的次數(shù) for(i=0; i<n; i++){ count_arr[ini_arr[i]]++; } //統(tǒng)計(jì)數(shù)組計(jì)數(shù)，每項(xiàng)存前N項(xiàng)和，這實(shí)質(zhì)為排序過(guò)程for(k=1; k<NUM_RANGE; k++){ count_arr[k] += count_arr[k-1]; } //將計(jì)數(shù)排序結(jié)果轉(zhuǎn)化為數(shù)組元素的真實(shí)排序結(jié)果for(j=n-1 ; j>=0; j--){ int elem = ini_arr[j]; //取待排序元素int index = count_arr[elem]-1; //待排序元素在有序數(shù)組中的序號(hào)sorted_arr[index] = elem; //將待排序元素存入結(jié)果數(shù)組中count_arr[elem]--; //修正排序結(jié)果，其實(shí)是針對(duì)算得元素的修正} free(count_arr); } 程序2：C++(最大最小壓縮桶數(shù)) public static void countSort(int[] arr) {if (arr == null || arr.length < 2) {return;}int min = arr[0];int max = arr[0];for (int i = 1; i < arr.length; i++) {min = Math.min(arr[i], min);max = Math.max(arr[i], max);}int[] countArr = new int[max - min + 1];for (int i = 0; i < arr.length; i++) {countArr[arr[i] - min]++;}int index = 0;for (int i = 0; i < countArr.length; i++) {while (countArr[i]-- > 0) {arr[index++] = i + min;} }10 基數(shù)排序
10.1 過(guò)程
基數(shù)排序是基于數(shù)據(jù)位數(shù)的一種排序算法。?
它有兩種算法?
①LSD–Least Significant Digit first 從低位（個(gè)位）向高位排。?
②MSD– Most Significant Digit first 從高位向低位（個(gè)位）排。?
時(shí)間復(fù)雜度O(N*最大位數(shù))。?
空間復(fù)雜度O(N)。
10.2 圖解
?
對(duì)a[n]按照個(gè)位0~9進(jìn)行桶排序：?
?
對(duì)b[n]進(jìn)行累加得到c[n]，用于b[n]中重復(fù)元素計(jì)數(shù)?
！！！b[n]中的元素為temp中的位置！！！跳躍的用++補(bǔ)上：?
?
temp數(shù)組為排序后的數(shù)組，寫(xiě)回a[n]。temp為按順序倒出桶中的數(shù)據(jù)（聯(lián)合b[n],c[n],a[n]得到），重復(fù)元素按順序輸出：?
10.3 核心程序
//基數(shù)排序 //LSD 先以低位排，再以高位排 //MSD 先以高位排，再以低位排 void LSDSort(int *a, int n) { assert(a); //判斷a是否為空，也可以a為空||n<2返回int digit = 0; //最大位數(shù)初始化for (int i = 0; i < n; ++i) { //求最大位數(shù)while (a[i] > (pow(10,digit))) //pow函數(shù)要包含頭文件math.h，pow(10,digit)=10^digit{ digit++; } } int flag = 1; //位數(shù)for (int j = 1; j <= digit; ++j) { //建立數(shù)組統(tǒng)計(jì)每個(gè)位出現(xiàn)數(shù)據(jù)次數(shù)（Digit[n]為桶排序b[n]） int Digit[10] = { 0 }; for (int i = 0; i < n; ++i) { Digit[(a[i] / flag)%10]++; //flag=1時(shí)為按個(gè)位桶排序} //建立數(shù)組統(tǒng)計(jì)起始下標(biāo)（BeginIndex[n]為個(gè)數(shù)累加c[n]，用于記錄重復(fù)元素位置//flag=1時(shí)，下標(biāo)代表個(gè)位數(shù)值，數(shù)值代表位置，跳躍代表重復(fù)）int BeginIndex[10] = { 0 }; for (int i = 1; i < 10; ++i) { //累加個(gè)數(shù)BeginIndex[i] = BeginIndex[i - 1] + Digit[i - 1]; } //建立輔助空間進(jìn)行排序 //下面兩條可以用calloc函數(shù)實(shí)現(xiàn)int *tmp = new int[n]; memset(tmp, 0, sizeof(int)*n);//初始化 //聯(lián)合各數(shù)組求排序后的位置存在temp中for (int i = 0; i < n; ++i) { int index = (a[i] / flag)%10; //桶排序和位置數(shù)組中的下標(biāo)//計(jì)算temp相應(yīng)位置對(duì)應(yīng)a[i]中的元素，++為BeginIndex數(shù)組數(shù)值加1//跳躍間隔用++來(lái)補(bǔ)，先用再++tmp[BeginIndex[index]++] = a[i]; } //將數(shù)據(jù)重新寫(xiě)回原空間 for (int i = 0; i < n; ++i) { a[i] = tmp[i]; } flag = flag * 10; delete[] tmp; } }附：
1 完整程序框架（冒泡排序舉例）
1.1 VS2010程序
#include "stdafx.h" #include "stdio.h" #include <stdlib.h>void BubbleSort(int array[], int n){int i,j,k,count1=0, count2=0;for(i=0; i<n-1; i++)for(j=n-1; j>i; j--){count1++;if(array[j-1]>array[j]){count2++;k=array[j-1];array[j-1]=array[j];array[j]=k;}}printf("總共的循環(huán)次序?yàn)?#xff1a;%d, 總共的交換次序?yàn)?#xff1a;%d\n\n", count1, count2); }int main(int argc, _TCHAR* argv[]) {int as[]={0,1,2,3,4,6,8,5,9,7};BubbleSort(as, 10);for(int i=0; i<10; i++){printf("%d", as[i]);}printf("\n\n");system("pause");return 0; }1.2 執(zhí)行程序（OJ）
#include <stdio.h>void BubbleSort(int array[], int n){int i,j,k,count1=0, count2=0;for(i=0; i<n-1; i++)for(j=n-1; j>i; j--){count1++;if(array[j-1]>array[j]){count2++;k=array[j-1];array[j-1]=array[j];array[j]=k;}}printf("總共的循環(huán)次序?yàn)?#xff1a;%d, 總共的交換次序?yàn)?#xff1a;%d\n\n", count1, count2); }int main() {int as[]={0,1,2,3,4,6,8,5,9,7};BubbleSort(as, 10);int i=0;for(i=0; i<10; i++){printf("%d", as[i]);}return 0; }2 關(guān)于交換的優(yōu)化
不用中間變量進(jìn)行交換
if(A[j] <= A[i]){A[j] = A[j] + A[i];A[i] = A[j] - A[i];A[j] = A[j] - A[i]; }3 C語(yǔ)言實(shí)現(xiàn)數(shù)組動(dòng)態(tài)輸入
#include <stdio.h> #include <assert.h> //斷言頭文件 #include <stdlib.h> int main(int argc, char const *argv[]) { int size = 0; scanf("%d", &size); //首先輸入數(shù)組個(gè)數(shù)assert(size > 0); //判斷數(shù)組個(gè)數(shù)是否非法int *array = (int *)calloc(size, sizeof(int)); //動(dòng)態(tài)分配數(shù)組if(!R1) { return; //申請(qǐng)空間失敗 } int i = 0; for (i = 0; i < size; ++i) { scanf("%d", &array[i]); } mergeSort(array, size); printArray(array, size); free(array); return 0; }注：?
1.colloc與malloc類(lèi)似,但是主要的區(qū)別是存儲(chǔ)在已分配的內(nèi)存空間中的值默認(rèn)為0,使用malloc時(shí),已分配的內(nèi)存中可以是任意的值.?
2.colloc需要兩個(gè)參數(shù),第一個(gè)是需要分配內(nèi)存的變量的個(gè)數(shù),第二個(gè)是每個(gè)變量的大小.
歡迎關(guān)注微信公眾號(hào)：嵌入式Linux??
?
總結(jié)
以上是生活随笔為你收集整理的排序算法时间复杂度、空间复杂度、稳定性比较的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： js上传文件并预览文件内容
- 下一篇： linux源码（含有kfifo）下载