幹貨收藏：一文掌握十大經典排序算法(動态示範+代碼)（er ）

7 希爾排序

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。先将整個待排序的記錄序列分割成為若幹子序列分别進行直接插入排序.

算法思想：

選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；

按增量序列個數k，對序列進行k 趟排序；

每趟排序，根據對應的增量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;
}