十大經典排序算法大梳理 (動圖+代碼)

2021-02-15 CodeSheep

以前也零零碎碎發過一些排序算法，但排版都不太好，這次重新整理一次，排序算法是數據結構的重要部分，面試必問，系統地學習很有必要！

時間、空間複雜度比較排序算法平均時間複雜度最差時間複雜度空間複雜度數據對象穩定性冒泡排序O(n2)O(n2)O(1)穩定選擇排序O(n2)O(n2)O(1)數組不穩定、鍊表穩定插入排序O(n2)O(n2)O(1)穩定快速排序O(n*log2n)O(n2)O(log2n)不穩定堆排序O(n*log2n)O(n*log2n)O(1)不穩定歸併排序O(n*log2n)O(n*log2n)O(n)穩定希爾排序O(n*log2n)O(n2)O(1)不穩定計數排序O(n+m)O(n+m)O(n+m)穩定桶排序O(n)O(n)O(m)穩定基數排序O(k*n)O(n2)
穩定1 冒泡排序

算法思想：

比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。冒泡排序動圖演示代碼：
void bubbleSort(int a[], int n)
{
  for(int i =0 ; i< n-1; ++i)
  {
    for(int j = 0; j < n-i-1; ++j)
    {
      if(a[j] > a[j+1])
      {
        int tmp = a[j] ;  //交換
        a[j] = a[j+1] ;
        a[j+1] = tmp;
      }
    }
  }
}
2 選擇排序
算法思想：
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾選擇排序動圖演示代碼：
function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 尋找最小的數
                minIndex = j;                 // 將最小數的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}
3 插入排序
算法思想：
取出下一個元素，在已經排序的元素序列中從後向前掃描如果該元素（已排序）大於新元素，將該元素移到下一位置重複步驟3，直到找到已排序的元素小於或者等於新元素的位置插入排序動圖演示代碼：
void print(int a[], int n ,int i){
  cout<<i <<":";
  for(int j= 0; j<8; j++){
    cout<<a[j] <<" ";
  }
  cout<<endl;
}
void InsertSort(int a[], int n)
{
  for(int i= 1; i<n; i++){
    if(a[i] < a[i-1]){   //若第i個元素大於i-1元素，直接插入。小於的話，移動有序表後插入
      int j= i-1;
      int x = a[i];     //複製為哨兵，即存儲待排序元素
      a[i] = a[i-1];           //先後移一個元素
      while(x < a[j]){   //查找在有序表的插入位置
        a[j+1] = a[j];
        j--;     //元素後移
      }
      a[j+1] = x;     //插入到正確位置
    }
    print(a,n,i);      //列印每趟排序的結果
  }

}

int main(){
  int a[15] = {2，3,4,5,15，19，16，27，36，38，44，46，47，48，50};
  InsertSort(a,15);
  print(a,15,15);
}
4 快速排序
算法思想：
快速排序動圖演示代碼：
void QuickSort(vector<int>& v, int low, int high) {
	if (low >= high)		// 結束標誌
		return;
	int first = low;		// 低位下標
	int last = high;		// 高位下標
	int key = v[first];		// 設第一個為基準

	while (first < last)
	{
		// 將比第一個小的移到前面
		while (first < last && v[last] >= key)
			last--;
		if (first < last)
			v[first++] = v[last];

		// 將比第一個大的移到後面
		while (first < last && v[first] <= key)
			first++;
		if (first < last)
			v[last--] = v[first];
	}
	//
	v[first] = key;
	// 前半遞歸
	QuickSort(v, low, first - 1);
	// 後半遞歸
	QuickSort(v, first + 1, high);
}
5 堆排序
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。
算法思想：
將初始待排序關鍵字序列(R1,R2….Rn)構建成大頂堆，此堆為初始的無序區；將堆頂元素R[1]與最後一個元素R[n]交換，此時得到新的無序區(R1,R2,……Rn-1)和新的有序區(Rn),且滿足R[1,2…n-1]<=R[n]；由於交換後新的堆頂R[1]可能違反堆的性質，因此需要對當前無序區(R1,R2,……Rn-1)調整為新堆，然後再次將R[1]與無序區最後一個元素交換，得到新的無序區(R1,R2….Rn-2)和新的有序區(Rn-1,Rn)。不斷重複此過程直到有序區的元素個數為n-1，則整個排序過程完成。代碼：
#include <iostream>
#include <algorithm>
using namespace std;

// 堆排序：（最大堆，有序區）。從堆頂把根卸出來放在有序區之前，再恢復堆。

void max_heapify(int arr[], int start, int end) {
	//建立父節點指標和子節點指標
	int dad = start;
	int son = dad * 2 + 1;
	while (son <= end) { //若子節點在範圍內才做比較
		if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節點指標，選擇最大的
			son++;
		if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完成，直接跳出函數
			return;
		else { //否則交換父子內容再繼續子節點與孫節點比較
			swap(arr[dad], arr[son]);
			dad = son;
			son = dad * 2 + 1;
		}
	}
}

void heap_sort(int arr[], int len) {
	//初始化，i從最後一個父節點開始調整
	for (int i = len / 2 - 1; i >= 0; i--)
		max_heapify(arr, i, len - 1);
	//先將第一個元素和已經排好的元素前一位做交換，再從新調整(剛調整的元素之前的元素)，直到排序完成
	for (int i = len - 1; i > 0; i--) {
		swap(arr[0], arr[i]);
		max_heapify(arr, 0, i - 1);
	}
}

int main() {
	int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
	int len = (int) sizeof(arr) / sizeof(*arr);
	heap_sort(arr, len);
	for (int i = 0; i < len; i++)
		cout << arr[i] << ' ';
	cout << endl;
	return 0;
}
6 歸併排序
歸併排序是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為2-路歸併。
算法思想：1.把長度為n的輸入序列分成兩個長度為n/2的子序列；2. 對這兩個子序列分別採用歸併排序；3. 將兩個排序好的子序列合併成一個最終的排序序列。
歸併排序動圖演示代碼：
void print(int a[], int n){
  for(int j= 0; j<n; j++){
    cout<<a[j] <<"  ";
  }
  cout<<endl;
}

//將r[i…m]和r[m +1 …n]歸併到輔助數組rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
  int j,k;
  for(j=m+1,k=i; i<=m && j <=n ; ++k){
    if(r[j] < r[i]) rf[k] = r[j++];
    else rf[k] = r[i++];
  }
  while(i <= m)  rf[k++] = r[i++];
  while(j <= n)  rf[k++] = r[j++];
  print(rf,n+1);
}

void MergeSort(ElemType *r, ElemType *rf, int lenght)
{
  int len = 1;
  ElemType *q = r ;
  ElemType *tmp ;
  while(len < lenght) {
    int s = len;
    len = 2 * s ;
    int i = 0;
    while(i+ len <lenght){
      Merge(q, rf,  i, i+ s-1, i+ len-1 ); //對等長的兩個子表合併
      i = i+ len;
    }
    if(i + s < lenght){
      Merge(q, rf,  i, i+ s -1, lenght -1); //對不等長的兩個子表合併
    }
    tmp = q; q = rf; rf = tmp; //交換q,rf，以保證下一趟歸併時，仍從q 歸併到rf
  }
}


int main(){
  int a[10] = {2，3,4，5,15,19,26,27,36,38,44,46,47,48,50};
  int b[10];
  MergeSort(a, b, 15);
  print(b,15);
  cout<<"結果：";
  print(a,10);
}
7 希爾排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序.
算法思想：
選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。希爾排序動圖演示代碼：
void shell_sort(T array[], int length) {
    int h = 1;
    while (h < length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
                std::swap(array[j], array[j - h]);
            }
        }
        h = h / 3;
    }
}
8 計數排序
計數排序統計小於等於該元素值的元素的個數i，於是該元素就放在目標數組的索引i位（i≥0）。
計數排序基於一個假設，待排序數列的所有數均為整數，且出現在（0，k）的區間之內。如果 k（待排數組的最大值） 過大則會引起較大的空間複雜度，一般是用來排序 0 到 100 之間的數字的最好的算法，但是它不適合按字母順序排序人名。計數排序不是比較排序，排序的速度快於任何比較排序算法。
算法思想：
統計數組中每個值為 i 的元素出現的次數，存入數組 C 的第 i 項；對所有的計數累加（從 C 中的第一個元素開始，每一項和前一項相加）；向填充目標數組：將每個元素 i 放在新數組的第 C[i] 項，每放一個元素就將 C[i] 減去 1；計數排序動圖演示代碼：
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 計數排序
void CountSort(vector<int>& vecRaw, vector<int>& vecObj)
{
	// 確保待排序容器非空
	if (vecRaw.size() == 0)
		return;

	// 使用 vecRaw 的最大值 + 1 作為計數容器 countVec 的大小
	int vecCountLength = (*max_element(begin(vecRaw), end(vecRaw))) + 1;
	vector<int> vecCount(vecCountLength, 0);

	// 統計每個鍵值出現的次數
	for (int i = 0; i < vecRaw.size(); i++)
		vecCount[vecRaw[i]]++;
	
	// 後面的鍵值出現的位置為前面所有鍵值出現的次數之和
	for (int i = 1; i < vecCountLength; i++)
		vecCount[i] += vecCount[i - 1];

	// 將鍵值放到目標位置
	for (int i = vecRaw.size(); i > 0; i--)	// 此處逆序是為了保持相同鍵值的穩定性
		vecObj[--vecCount[vecRaw[i - 1]]] = vecRaw[i - 1];
}

int main()
{
	vector<int> vecRaw = { 0,5,7,9,6,3,4,5,2,8,6,9,2,1 };
	vector<int> vecObj(vecRaw.size(), 0);

	CountSort(vecRaw, vecObj);

	for (int i = 0; i < vecObj.size(); ++i)
		cout << vecObj[i] << "  ";
	cout << endl;

	return 0;
}
9 桶排序
將值為i的元素放入i號桶，最後依次把桶裡的元素倒出來。
算法思想：
桶排序動圖演示代碼：
function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }
 
    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 輸入數據的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 輸入數據的最大值
      }
    }
 
    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 設置桶的默認數量為5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }
 
    // 利用映射函數將數據分配到各個桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }
 
    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 對每個桶進行排序，這裡使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);
        }
    }
 
    return arr;
}
10 基數排序
一種多關鍵字的排序算法，可用桶排序實現。
算法思想：
arr為原始數組，從最低位開始取每個位組成radix數組；對radix進行計數排序（利用計數排序適用於小範圍數的特點）基數排序動圖演示代碼：
int maxbit(int data[], int n) //輔助函數，求數據的最大位數
{
    int maxData = data[0];		///< 最大數
    /// 先求出最大數，再求其位數，這樣有原先依次每個數判斷其位數，稍微優化點。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        //p *= 10; // Maybe overflow
        maxData /= 10;
        ++d;
    }
    return d;
/*    int d = 1; //保存最大的位數
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;*/
}
void radixsort(int data[], int n) //基數排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //計數器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //進行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空計數器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //統計每個桶中的記錄數
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個桶
        for(j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //將臨時數組的內容複製到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}
© 2020 GitHub, Inc.
參考資料https://www.cnblogs.com/onepixel/p/7674659.html(部分動圖來源)

相關焦點

  • 十大經典排序算法(動圖+代碼)
    下個月又將舉行信息奧賽了，一起來複習十大經典排序算法。
  • 《數據結構與算法》十大經典排序算法動圖演示(2019最新Python代碼)
    算法步驟首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。重複第二步，直到所有元素均排序完畢。2. 動圖演示從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的後面。）2. 動圖演示
  • JS家的排序算法 十大經典算法排序總結
    我相信以下的代碼裡一定會有某些bug或錯誤或語法不規範等問題是我自己無法發現的，所以敬請各位大神能夠指出錯誤，因為只有在不斷改錯的道路上我才能取得長久的進步。✦ ✦ ✦十大經典算法排序總結對比一張圖概括：
  • 十大經典排序算法(動態演示+代碼)！乾貨收藏
    冒泡排序動圖演示代碼歸併排序動圖演示代碼：但希爾排序是非穩定排序算法。先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序.一種多關鍵字的排序算法，可用桶排序實現。基數排序動圖演示代碼：int maxbit(int data[], int n) //輔助函數
  • 十大經典排序算法最強總結(含JAVA代碼實現)
    2.1 算法描述n 個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體算法描述如下：2.2 動圖演示歸併排序是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法（Divide and Conquer）的一個非常典型的應用。歸併排序是一種穩定的排序方法。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為2-路歸併。5.1 算法描述5.2 動圖演示
  • 十大經典排序算法最強總結
    2.1 算法描述n 個記錄的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。具體算法描述如下：2.2 動圖演示歸併排序是建立在歸併操作上的一種有效的排序算法。該算法是採用分治法（Divide and Conquer）的一個非常典型的應用。歸併排序是一種穩定的排序方法。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合併成一個有序表，稱為2-路歸併。5.1 算法描述5.2 動圖演示
  • Java面試之排序算法篇(動圖)
    算法是編程的基礎，是面試過程中經常問到的熱點問題之一，尤其是排序算法。但是大部分的網際網路公司只要回答出基本的思路或者原理即可，點到為止，除了華為社招有機試寫代碼，其他公司不多見。下面我們就整理了常見的八大排序算法，供大家參考。
  • 排序算法---基數排序,動圖詳解,Java實現!
    根據動圖可以看到桶應該是個二維數組，既要有編號（0-9），又要存數據（0-arr.length）。最後arr數組就會按照升序排序結束。在此只展示代碼不同的地方，其餘地方完全一樣。//算法：取出十位的數字int digitOfElement = arr[j] / 10 % 10;
  • 【第3篇 | 數據結構與算法】一舉消滅十大常見(常考)排序算法(原理+動圖+代碼+)
    第1篇 | 算法複雜度分析（必會）第2篇 | 一文複習完7種數據結構（原理+代碼）正文共計6000+字，19張講解算法圖片，14張代碼截圖，所有代碼均可在筆者的GitHub（https://github.com/econe-zhangwei
  • 經典排序算法三 選擇排序(JAVA實現)
    選擇排序原理：每一趟從待排序的記錄中選出最小的元素，順序放在已排好序的序列最後，直到全部記錄排序完畢。也就是：每一趟在n-i+1(i=1，2，…n-1)個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。基於此思想的算法主要有簡單選擇排序、樹型選擇排序和堆排序。
  • 十大經典排序算法之希爾排序算法
    希爾排序之前我們講過冒泡排序、選擇排序、插入排序，它們的時間複雜度都是 這就是希爾排序的思想。代碼實現#!random.randint(min_number, max_number) for _ in range(num)]    print(array)    shell_sort_original(array)    print(array)乍一看，這個程序一共有四層循環，是不是覺得這個程序怎麼可能是插入排序的優化算法呢
  • 八十七、Python|十大排序算法系列(上篇)
    辣雞的我決定繼續更新Python教程，今天就開始了八十七、Python | 十大排序算法系列（上篇）。還有不到區區的十三篇，我快完成了。如果把基礎的數據結構與算法都自己親自實現一遍，那麼你已經比 90% 的 Python 程式設計師更優秀了。
  • 統治世界的十大排序算法!
    算法步驟首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。重複第二步，直到所有元素均排序完畢。2. 動圖演示3.3.2.
  • JavaScript 數據結構與算法之美 - 十大經典排序算法匯總(上)
    筆者寫的 JavaScript 數據結構與算法之美系列用的語言是 JavaScript ，旨在入門數據結構與算法和方便以後複習。文中包含了十大經典排序算法的思想、代碼實現、一些例子、複雜度分析、動畫、還有算法可視化工具。
  • 八大經典排序算法詳解
    我把最經典的八大排序算法原理和代碼也都整理出來了，內容如下，希望對大家能有所幫助。插入排序•基本思想：每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。•算法適用於少量數據的排序，時間複雜度為O(n^2)。是穩定的排序方法。
  • Python實現八大經典排序算法
    一、前言在面試題中可能會遇到排序算法，畢竟作為程式設計師內功心法，熟練掌握排序算法是很重要的，本文總結了八大經典排序算法的 Python 實現。排序算法是《數據結構與算法》中最基本的算法之一。動圖演示過程如下：
  • 數據挖掘領域十大經典算法之—C4.5算法(超詳細附代碼)
    C4 5是決策樹算法的一種。決策樹算法作為一種分類算法，目標就是將具有p維特徵的n個樣本分到c個類別中去。
  • 程式設計師必知必會的十大排序算法
    緒論身為程式設計師，十大排序是所有合格程式設計師所必備和掌握的，並且熱門的算法比如快排、歸併排序還可能問得比較細緻，對算法性能和複雜度的掌握都有要求。本文將帶你捋一捋常見的十大排序算法，讓你輕輕鬆鬆掌握！首先對於排序來說，大多數人對排序的概念停留在冒泡排序或者JDK中的Arrays.sort()，手寫各種排序對很多人來說都是一種奢望，更別說十大排序算法了。對於排序的分類，可以根據不同的維度比如複雜度、內外部、比較非比較等維度來分類。
  • Java實現冒泡排序算法
    學習方法推薦：#學習方法1.從基礎開始，系統化學習2.多動手，每一種數據結構與算法，都自己用代碼實現出來3.思路更重要：理解實現思想，不要背代碼4.與日常開發結合，對應應用場景學習內容推薦：數據結構與算法內容比較多，我們本著實用原則，學習經典的、常用的數據結構、與常用算法#學習內容：1.數據結構的定義2.算法的定義3.複雜度分析4
  • 十大經典排序算法(下)
    （Heapsort）是指利用堆這種數據結構所設計的一種排序算法。作為一種線性時間複雜度的排序，計數排序要求輸入的數據必須是有確定範圍的整數。計數排序(Counting sort)是一種穩定的排序算法。計數排序使用一個額外的數組C，其中第i個元素是待排序數組A中值等於i的元素的個數。然後根據數組C來將A中的元素排到正確的位置。它只能對整數進行排序。