🐧作者主頁：king&南星
🏰專欄鏈接：c++

一、八大排序算法復(fù)雜度對(duì)比

二、基于比較的排序算法

1.冒泡排序

• 介紹：冒泡排序（Bubble Sort），是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法。

它重復(fù)地走訪過要排序的元素列，依次比較兩個(gè)相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯(cuò)誤就把他們交換過來。走訪元素的工作是重復(fù)地進(jìn)行，直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成。

這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣，故名“冒泡排序”

• 核心：

  冒泡排序:
  比較 NUM-1輪，每輪NUM-1次，
  每輪（相鄰兩個(gè)比較，不符合要求則交換）
  找出一個(gè)最大的或者一個(gè)最小的
  

//冒泡排序
void bubble_sort(int* a, int len)
{int t;for ( int i = 0;  i < len-1;  i++)          //len-1輪{for( int j = 0; j < len-1-i ; j++ )     //每輪為無序的元素個(gè)數(shù)-1次{if ( a[j] > a[j+1] )               //不符合規(guī)則交換{t = a[j];a[j] = a[j + 1];a[j + 1] = t;}}}
}

總結(jié)：

1. 冒泡排序是一種非常容易理解的排序
2. 時(shí)間復(fù)雜度：O( N²)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：穩(wěn)定

2.選擇排序

• 介紹：選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個(gè)數(shù)為零。選擇排序是不穩(wěn)定的排序方法。

• 核心：

  選擇排序：

  ? 先假設(shè)待排數(shù)組第一個(gè)為最小值

  ? 選擇NUM-1輪，每輪從待排數(shù)組中選最小的，與第一個(gè)進(jìn)行比較，決定放不放到待排數(shù)組第一個(gè)
  ? 循環(huán)從待排數(shù)組中找到最小的，記錄其下標(biāo)
  ? 交換

//選擇排序
void select_sort(int* a, int len)
{int t;int minIndex;for (int i = 0; i < len-1; i++)  //len-1輪{//從待排數(shù)組中(i ----- len-1)找到最小的minIndex = i;      //先假設(shè)待排數(shù)組中的第一個(gè)最小for (int j = i+1; j < len; j++){minIndex = a[j] > a[minIndex] ? minIndex : j;}//符合條件和待排數(shù)組中的第一個(gè)元素(i)交換if ( a[minIndex] < a[i] ){t = a[minIndex];a[minIndex] = a[i];a[i] = t;}}
}

總結(jié)：

1. 直接選擇排序思考非常好理解，但是效率不是很好。實(shí)際中很少使用
2. 時(shí)間復(fù)雜度：O(N²)
3. 空間復(fù)雜度：O(1)
4. 穩(wěn)定性：不穩(wěn)定

3.插入排序

• 介紹：插入排序，一般也被稱為直接插入排序。對(duì)于少量元素的排序，它是一個(gè)有效的算法 。插入排序是一種最簡(jiǎn)單的排序方法，它的基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而一個(gè)新的、記錄數(shù)增1的有序表。在其實(shí)現(xiàn)過程使用雙層循環(huán)，外層循環(huán)對(duì)除了第一個(gè)元素之外的所有元素，內(nèi)層循環(huán)對(duì)當(dāng)前元素前面有序表進(jìn)行待插入位置查找，并進(jìn)行移動(dòng)。

  核心：

  插入排序：
  設(shè)置第一個(gè)為有序數(shù)組，右邊NUM-1個(gè)為待插數(shù)據(jù)
  然后NUM-1輪，每輪把一個(gè)數(shù)據(jù)插入到有序數(shù)組中
  插入方式：
  1. 先臨時(shí)保存待插數(shù)據(jù)
  2. 然后從待插數(shù)據(jù)前一個(gè)開始往前循環(huán)（越界循環(huán)結(jié)束）
  比待插數(shù)據(jù)大則往后覆蓋，比待插數(shù)據(jù)小則循環(huán)結(jié)束
  3. 用待插數(shù)據(jù)覆蓋回來（第二步結(jié)束后下標(biāo)的下一個(gè)位置）

插入部分圖解

//插入排序
void insert_sort(int* a, int len)
{int j;int temp;//保存待插數(shù)據(jù)for (int i = 1; i < len; i++) //len-1輪{temp = a[i]; //待插數(shù)據(jù)前一個(gè)開始往前循環(huán)（越界循環(huán)結(jié)束）for ( j = i-1 ; j >= 0 ; j-- ) {//比待插數(shù)據(jù)大則往后覆蓋if ( a[j] > temp )  a[j + 1] = a[j];else break;}//用待插數(shù)據(jù)覆蓋回來（第二步結(jié)束后下標(biāo)的下一個(gè)位置）a[j + 1] = temp;}
}

總結(jié)：

1. 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高
2. 時(shí)間復(fù)雜度：O(N²)
3. 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法
4. 穩(wěn)定性：穩(wěn)定

4.希爾排序

• 介紹：

• 希爾排序(Shell’s Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因 D.L.Shell 于 1959 年提出而得名。

  希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至 1 時(shí)，整個(gè)文件恰被分成一組，算法便終止。

  核心：

  希爾（shell）排序：
  一個(gè)叫做shell的科學(xué)家發(fā)明的
  優(yōu)化后的插入排序
  引入步長的概念：
  一開始是 len/2 然后每次 除2 到1為止
  根據(jù)步長來分組，然后組內(nèi)作插入排序

//希爾排序
void shell_sort(int* a, int len)
{int j, temp;int step = len >> 2;while ( step )//根據(jù)步長來分組{//組內(nèi)作插入排序//從step開始  len-1-step輪for( int i = step ; i < len; i++ ){temp = a[i];//臨時(shí)保存待插數(shù)據(jù)//待插數(shù)據(jù)前一個(gè)開始往前循環(huán)（越界循環(huán)結(jié)束）for ( j = i-step; j >= 0 ; j -= step ){//比待插數(shù)據(jù)大則往后覆蓋if (a[j] > temp) a[j + step] = a[j];else break;}//用待插數(shù)據(jù)覆蓋回來（第二步結(jié)束后下標(biāo)的下一個(gè)位置）a[j + step] = temp;}step >>= 1;}
}

總結(jié)：

1. 希爾排序是對(duì)直接插入排序的優(yōu)化。
2. 當(dāng)step > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)step == 1時(shí)，數(shù)組已經(jīng)接近有序的 了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。
3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，需要進(jìn)行推導(dǎo)，推導(dǎo)出來平均時(shí)間復(fù)雜度： O(N^1.3— N²）
4. 穩(wěn)定性：不穩(wěn)定

5.直觀感受四種算法的時(shí)間復(fù)雜度

這里隨機(jī)產(chǎn)出100000個(gè)數(shù)字，利用上面4種排序算法進(jìn)行排序，結(jié)果如下，可以看到希爾排序僅僅用了16ms

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <windows.h>
//數(shù)據(jù)個(gè)數(shù)
#define NUM  100000void init(int* a, int len);
void bubble_sort(int* a, int len);
//選擇排序
void select_sort(int* a, int len);
//插入排序
void insert_sort(int* a, int len);
//希爾排序
void shell_sort(int* a, int len);int main() {ULONGLONG oldTime, newTime;srand(time(NULL));int arr[NUM];init(arr, NUM);//初始化//獲取排序前時(shí)間oldTime = GetTickCount64();bubble_sort(arr, NUM);//排序//獲取排序后時(shí)間newTime = GetTickCount64();printf("bubble_sort:%llu\n", newTime - oldTime);init(arr, NUM);oldTime = GetTickCount64();select_sort(arr, NUM);newTime = GetTickCount64();printf("select_sort:%llu\n", newTime - oldTime);init(arr, NUM);oldTime = GetTickCount64();insert_sort(arr, NUM);newTime = GetTickCount64();printf("insert_sort:%llu\n", newTime - oldTime);init(arr, NUM);oldTime = GetTickCount64();shell_sort(arr, NUM);newTime = GetTickCount64();printf("shell_sort:%llu\n", newTime - oldTime);while (1);return 0;
}
void init(int* a, int len) {for (int i = 0; i < len; i++)a[i] = rand() % 1000;
}
//希爾排序
void shell_sort(int* a, int len) {int step = len / 2;int temp;int j;while (step) {//分組//組內(nèi)做插入排序for (int i = step; i < len; i++) {//每次循環(huán)插入a[i]temp = a[i];//臨時(shí)存儲(chǔ)待插數(shù)據(jù)for (j = i - step; j >= 0 && a[j] > temp; j -= step) {//從前往后覆蓋a[j + step] = a[j];}a[j + step] = temp;}step /= 2;//每次步長變成原來的一半}
}//插入排序
void insert_sort(int* a, int len) {int temp;int j;for (int i = 1; i < len; i++) {//每次循環(huán)插入a[i]//把a(bǔ)[i] 插入到 a[0] - a[i-1] 數(shù)組中去temp = a[i];//臨時(shí)存儲(chǔ)待插數(shù)據(jù)for (j = i - 1; j >= 0 && a[j] > temp; j--) {//從前往后覆蓋a[j + 1] = a[j];}//插入進(jìn)來a[j + 1] = temp;}
}
//選擇排序
void select_sort(int* a, int len) {int min_idx;//記錄最小的元素的下標(biāo)int temp;for (int i = 0; i < len - 1; i++) {//找len-1次//每次 找出  a[i] - a[len-1] 范圍內(nèi)最小的元素 min_idx = i;//假設(shè)a[i]最小for (int j = i; j < len; j++) {min_idx = ((a[min_idx] < a[j]) ? min_idx : j);}//a[min_idx] 和 a[i]交換temp = a[i];a[i] = a[min_idx];a[min_idx] = temp;}
}void bubble_sort(int* a, int len) {int temp;for (int j = 0; j < len - 1; j++) {for (int i = 0; i < len - j - 1; i++) {//0 - len-2if (a[i] > a[i + 1]) {//不符合要求//交換temp = a[i];a[i] = a[i + 1];a[i + 1] = temp;}}}
}

三、基于非比較的排序算法

1.基數(shù)排序

• 介紹：基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達(dá)到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時(shí)間復(fù)雜度為O (nlog?m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時(shí)候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。

  核心：

  基數(shù)排序 ：O(n)
  最快的排序方式 沒有之一
  利用數(shù)組下標(biāo)天然有序的特性來進(jìn)行排序
  max:最大元素值
  限制很多：

  1. 只能排正整數(shù)（優(yōu)化后可以對(duì)所有整數(shù)排序）
  2. 不能有重復(fù)
  3. 空間可能耗費(fèi)特別大
  4. 臨時(shí)空間大小
  

//基數(shù)排序
void radix_sort(int* a, int len, int max)
{int index = 0;//先準(zhǔn)備一個(gè)臨時(shí)數(shù)組 max+1int* pTemp = (int*)malloc(sizeof(int) * (max + 1));assert(pTemp); //判斷申請(qǐng)成功沒//初始化為-1//for (int i = 0; i <= max; i++) pTemp[i] = -1;memset(pTemp, -1, sizeof(int) * (max + 1));//將待排數(shù)組放到臨時(shí)數(shù)組中，待排數(shù)組的值作為臨時(shí)數(shù)組的下標(biāo)for (int i = 0; i < len; i++) pTemp[a[i]] = a[i];//從臨時(shí)數(shù)組中把排序好的數(shù)據(jù)放回原數(shù)組中for (int i = 0; i <= max; i++) {if ( pTemp[i] != -1 ){a[index++] = pTemp[i];}}//釋放內(nèi)存free(pTemp);
}

總結(jié)：

1. 時(shí)間復(fù)雜度：O（n+k）
2. 空間復(fù)雜度：O（n+k）
3. 不能對(duì)小數(shù)進(jìn)行排序，但是速度極快

2.箱(桶)排序

• 介紹：桶排序 (Bucket sort)或所謂的箱排序，是一個(gè)排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。當(dāng)要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時(shí)候，桶排序使用線性時(shí)間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。

  核心：

  桶(箱)排序:bucket_sort
  把數(shù)據(jù)分成若干個(gè)箱子 然后箱子里用其他排序

這里是按個(gè)位十位分箱，內(nèi)部類似于基數(shù)排序

//箱排序
void bucket_sort(int* a, int len)
{int idx, k;int n = 1; int* pTemp = NULL;while ( n < AREA )//1000以內(nèi)的數(shù)字，AREA ==1000{//1 做箱子  并初始化箱子pTemp = (int*)malloc(10 * len * sizeof(int));for (int i = 0; i < 10 * len; i++) pTemp[i] = -1;//2 根據(jù)特性(對(duì)應(yīng)位作為箱子的編號(hào))放入箱子中for (int i = 0; i < len; i++){//獲取到數(shù)據(jù)這一輪要看的位上的數(shù)據(jù)idx = a[i] / n % 10;pTemp[idx * len + i] = a[i];}//3 從箱子中取出，覆蓋a數(shù)組k = 0;for (int i = 0; i < 10*len; i++){if ( pTemp[i] != -1 )a[k++] = pTemp[i];}//4 銷毀箱子free(pTemp);pTemp = NULL;n *= 10;}
}

四、遞歸比較排序算法

1.快速排序

• 介紹：快速排序（Quicksort），計(jì)算機(jī)科學(xué)詞匯，適用領(lǐng)域Pascal，c++等語言，是對(duì)冒泡排序算法的一種改進(jìn)。

  核心：

  快速排序：就是分組排序
  把數(shù)據(jù)分成兩組
  確定中間值，左邊都比中間值小 右邊都比中間值大
  遞歸(遞推)持續(xù)分組 到 不可再分(一組只有一個(gè)數(shù)據(jù))為止

void Quick_sort(int* a, int len)
{quick_sort(a, 0, len - 1);
}
void quick_sort(int* a, int Left, int Right)
{int L = Left, R = Right;if ( L >= R ) return; //遞歸結(jié)束// 先假設(shè)a[left]是中間數(shù)據(jù),并臨時(shí)保存int temp = a[L];// 循環(huán)挪動(dòng)l和r并覆蓋  循環(huán)結(jié)束后 L==Rwhile ( L < R ){// 先挪右邊的while ( L < R && a[R] > temp)   R--;a[L] = a[R];// 再挪左邊的while (L<R && a[L] < temp )    L++;a[R] = a[L];}// 用中間數(shù)據(jù)覆蓋回來a[L] = temp; //a[R] = temp;quick_sort(a, Left, R - 1);quick_sort(a, L + 1, Right);
}

2.歸并排序

• 介紹：歸并排序是建立在歸并操作上的一種有效，穩(wěn)定的排序算法，該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。

1.普通歸并

• 核心：兩個(gè)有序數(shù)組合并成一個(gè)有序數(shù)組

void Merge_sort(int* a, int L, int M, int R)
{int Left = L, Right = M + 1;if (L >= R) return;//開臨時(shí)內(nèi)存int* pTemp = (int*)malloc(sizeof(int) * (R - L + 1));int k = 0;//兩個(gè)中有一個(gè)放完了while ( Left <= M && Right <= R ){if (a[Left] < a[Right]) pTemp[k++] = a[Left++];else pTemp[k++] = a[Right++];}//左邊還沒放完if (Left <= M) memcpy(pTemp + k, a + Left, sizeof(int) * (M - Left + 1));//右邊還沒放完else  memcpy(pTemp + k, a +Right, sizeof(int) * (R - Right + 1));//覆蓋回去memcpy( a + L , pTemp, sizeof(int) * (R - L + 1));//釋放內(nèi)存free(pTemp);
}

2.歸并遞歸

• 核心：把無序數(shù)組完全拆開，再進(jìn)行歸并排序

void Merge_Sort(int* a, int len)
{merge__sort(a, 0, len - 1);
}
void merge__sort(int* a, int L, int R)
{// L和R不相等，說明還沒拆到只剩一個(gè)，繼續(xù)拆if (L < R){int m = L + (R - L) / 2;merge__sort(a, L, m);        //左邊一半merge__sort(a, m + 1, R);    //右邊一半Merge_sort(a, L, m, R);      //拆到無法拆了就合并}
}

🎉歡迎各位→點(diǎn)贊👏 + 收藏💞 + 留言🔔?
💬總結(jié)：希望你看完之后，能對(duì)你有所幫助，不足請(qǐng)指正！共同學(xué)習(xí)交流 🐾