了解十大排序算法

十種常見排序算法可以分為兩大類：

比較類排序：通過比較來決定元素間的相對次序，由于其時間複雜度不能突破O(nlogn)，是以也稱為非線性時間比較類排序。

非比較類排序：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運作，是以也稱為線性時間非比較類排序。

了解十大排序算法

1、冒泡排序

1.1 算法描述

比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；
針對所有的元素重複以上的步驟，除了最後一個；
重複步驟1~3，直到排序完成。

void bubbleSort(vector<int> &arr)
{
    auto len = arr.size();
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[i], arr[j]);
            }
        }
    }
}

2、選擇排序

選擇排序(Selection-sort)是一種簡單直覺的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

2.1 具體算法描述如下：

初始狀态：無序區為R[1…n]，有序區為空；
第i趟排序(i=1,2,3…n-1)開始時，目前有序區和無序區分别為R[1…i-1]和R(i…n）。該趟排序從目前無序區中-選出關鍵字最小的記錄 R[k]，将它與無序區的第i個記錄R交換，使R[1…i]和R[i+1…n)分别變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；
n-1趟結束，數組有序化了。

void selectionSort(vector<int> &arr)
{
    auto len = arr.size();
    int min_index = 0;
    for (int i = 0; i < len - 1; ++i) {
        min_index = i;  // 需要找到的第i個元素
        for (int j = i + 1; j < len; ++j) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        // 交換到最小位置
        swap(arr[i], arr[min_index]);
    }
}

3、插入排序

選擇排序(Selection-sort)是一種簡單直覺的排序算法。它的工作原理：通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。

3.1 具體算法描述如下：

一般來說，插入排序都采用in-place在數組上實作。具體算法描述如下：

從第一個元素開始，該元素可以認為已經被排序；
取出下一個新元素，在已經排序的元素序列中從後向前掃描；
如果該元素（已排序）大于新元素，将該元素移到下一位置；
重複步驟3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到該位置後；
重複步驟2~5。

void insertionSort(vector<int> &arr)
{
    auto len = arr.size();
    for (int i = 1; i < len; ++i) {
        int preIndex = i - 1;  // 0-i已經排序，取出已排序的最後一個位置
        int current = arr[i];   // 新元素
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex]; // 将preIndex位置的元素向後挪一個位置
            preIndex--;   // preIndex永遠指向待比較的元素
        }
        // 此時preIndex的元素小于current，需要把current插入到preIndex後面
        arr[preIndex + 1] = current;
    }
}

4、希爾排序

希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。

4.1 具體算法描述如下：

先将整個待排序的記錄序列分割成為若幹子序列分别進行直接插入排序，具體算法描述：

選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1，把檔案的全部記錄分組。所有距離為t1的的記錄放在同一個組中.
先在各組内進行直接插入排序;
然後，取第二個增量t2<t1重複上述的分組和排序，直至所取的增量為1，即所有記錄放在同一組中進行直接插入排序為止

void shellSort(vector<int> &arr)
{
    auto len = arr.size();
    int gap = len;
    while (gap > 1) {
        gap = gap / 3 + 1;
        for (int i = 0; i < len - gap; ++i)//i可取到size-1-gap
        {
            // 插入排序
            int tmp = arr[i + gap];
            int preIndex = i;  // 假設第i個位置的元素有序，将tmp與arr[i]放在正确位置
            while (preIndex >= 0 && arr[preIndex] > tmp) {
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap;// 退gap位
            }
            arr[preIndex + gap] = tmp;
        }
    }
}

希爾排序的精華就是，将較小的記錄，不是一步步往前移，而是跳躍式地往前移動。

5、歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為2-路歸并。

5.1 具體算法描述如下：

先将整個待排序的記錄序列分割成為若幹子序列分别進行直接插入排序，具體算法描述：

把長度為n的輸入序列分成兩個長度為n/2的子序列；
對這兩個子序列分别采用歸并排序；
将兩個排序好的子序列合并成一個最終的排序序列。

vector<int> merge(vector<int> left, vector<int> right)
{
    vector<int> result;
    while (!left.empty() && !right.empty()) {
        if (left[0] <= right[0]) {
            result.push_back(left.front());
            left.erase(left.begin());
        } else {
            result.push_back(right.front());
            right.erase(right.begin());
        }
    }

    while (!left.empty()) {
        result.push_back(left.front());
        left.erase(left.begin());
    }

    while (!right.empty()) {
        result.push_back(right.front());
        right.erase(right.begin());
    }
    return result;
}

vector<int> mergeSort(vector<int> &arr)
{
    auto len = arr.size();
    if (len <= 1) {
        return arr;
    }
    int middle = floor(len / 2);
    vector<int> left(arr.begin(), arr.begin() + middle);
    vector<int> right(arr.begin() + middle, arr.end());
    return merge(mergeSort(left), mergeSort(right));
}

6、快速排序

快速排序的基本思想：通過一趟排序将待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分别對這兩部分記錄繼續進行排序，以達到整個序列有序。

6.1 具體算法描述如下：

快速排序使用分治法來把一個串（list）分為兩個子串（sub-lists）。具體算法描述如下：

從數列中挑出一個元素，稱為 “基準”（pivot）；
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

void quickSort(int left, int right, vector<int> &arr)
{
    if (left >= right)
        return;
    int i, j, base;
    i = left, j = right;
    base = arr[left];  //取最左邊的數為基準數
    while (i < j) {
        while (arr[j] >= base && i < j)
            j--;
        while (arr[i] <= base && i < j)
            i++;
        if (i < j) {
            swap(arr[i], arr[j]);
        }
    }
    //基準數歸位
    arr[left] = arr[j];
    arr[j] = base;
    quickSort(left, j - 1, arr);  //遞歸左邊
    quickSort(j + 1, right, arr); //遞歸右邊
}

7、堆排序

堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。

7.1 算法描述

将初始待排序關鍵字序列(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，則整個排序過程完成。

// 遞歸方式建構大根堆(len是arr的長度，index是第一個非葉子節點的下标)
void adjust(vector<int> &arr, int len, int index)
{
    int left = 2 * index + 1; // index的左子節點
    int right = 2 * index + 2;// index的右子節點

    int maxIdx = index; // 父節點
    if (left < len && arr[left] > arr[maxIdx]) {
        maxIdx = left;  // 将左節點大值往上移
    }
    if (right < len && arr[right] > arr[maxIdx])  {
        maxIdx = right; // 将右節點大值往上移
    }
    if (maxIdx != index) {
        swap(arr[maxIdx], arr[index]); // 堆頂現在是maxIdx
        adjust(arr, len, maxIdx);  // 繼續下一輪上浮
    }
}

// 堆排序
void heapSort(vector<int> &arr, int size)
{
    // 建構大根堆（從最後一個非葉子節點向上）
    for (int i = size / 2 - 1; i >= 0; i--) {
        adjust(arr, size, i);
    }
    // 獲得到大頂堆
    // 調整大根堆
    for (int i = size - 1; i >= 1; i--) {
        swap(arr[0], arr[i]);           // 将目前最大的放置到數組末尾
        adjust(arr, i, 0);              // 将未完成排序的部分繼續進行堆排序
    }
}
heapSort(arr, arr.size());

8、計數排序

計數排序不是基于比較的排序算法，其核心在于将輸入的資料值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間複雜度的排序，計數排序要求輸入的資料必須是有确定範圍的整數。

8.1 算法描述

找出待排序的數組中最大和最小的元素；
統計數組中每個值為i的元素出現的次數，存入數組C的第i項；
對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；
反向填充目标數組：将每個元素i放在新數組的第C(i)項，每放一個元素就将C(i)減去1。

void countingSort(vector<int> &arr, int maxValue)
{
    vector<int> bucket(maxValue + 1, 0);  // 總共建立maxValue個桶
    int sortedIndex = 0;
    int arrLen = arr.size();
    int bucketLen = maxValue + 1;

    for (int i = 0; i < arrLen; i++) {
        bucket[arr[i]]++;
    }

    for (int j = 0; j < bucketLen; j++) {  // 每個桶存的元素數值是j
        while (bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
}

9、桶排序

桶排序是計數排序的更新版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的确定。桶排序 (Bucket sort)的工作的原理：假設輸入資料服從均勻分布，将資料分到有限數量的桶裡，每個桶再分别排序（有可能再使用别的排序算法或是以遞歸方式繼續使用桶排序進行排）。

9.1 算法描述

設定一個定量的數組當作空桶；
周遊輸入資料，并且把資料一個一個放到對應的桶裡去；
對每個不是空的桶進行排序；
從不是空的桶裡把排好序的資料拼接起來。

vector<int> bucketSort(vector<int> arr, int bucketSize)
{
    if (arr.size() <= 1) {
        return arr;
    }

    int minValue = arr[0];
    int maxValue = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] < minValue) {
            minValue = arr[i];                // 輸入資料的最小值
        } else if (arr[i] > maxValue) {
            maxValue = arr[i];                // 輸入資料的最大值
        }
    }

    // 桶的初始化
    const int DEFAULT_BUCKET_SIZE = 5;             // 設定桶中的數目為5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    int bucketCount = floor((maxValue - minValue) / bucketSize) + 1; // 總共的桶數量
    vector<vector<int>> buckets(bucketCount);

    // 利用映射函數将資料配置設定到各個桶中，桶與桶之前是有序的
    for (int i : arr) {
        buckets[floor((i - minValue) / bucketSize)].push_back(i);
    }

    arr.clear();
    for (int i = 0; i < bucketCount; i++) {
        auto t = bucketSort(buckets[i], 5);   // 對每個桶進行排序
        for (const auto &j : t) {
            arr.push_back(j);
        }
    }
    return arr;
}

桶排序最好情況下使用線性時間O(n)，桶排序的時間複雜度，取決與對各個桶的資料進行排序的時間複雜度，因為其它部分的時間複雜度都為O(n)。很顯然，桶劃分的越多，各個桶的資料越少，排序所用的時間也會越少。但相應的空間消耗就會增大。

10、基數排序

基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最後的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。

10.1算法描述

取得數組中的最大數，并取得位數；
arr為原始數組，從最低位開始取每個位組成radix數組；
對radix進行計數排序（利用計數排序适用于小範圍數的特點）

void radixSort(vector<int> &arr, int maxDigit)
{
    int mod = 10;
    int dev = 1;
    vector<vector<int>> counter(maxDigit);
    for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for (int j = 0; j < arr.size(); j++) {
            int bucket = ((arr[j] % mod) / dev);
            counter[bucket].push_back(arr[j]);
        }
        int pos = 0;
        for (int j = 0; j < counter.size(); j++) {
            if (!counter[j].empty()) {
                int value;
                while (!counter[j].empty() && (value = counter[j].front())) {
                    arr[pos++] = value;
                }
            }
        }
    }
}

了解十大排序算法

1、冒泡排序

2、選擇排序

3、插入排序

4、希爾排序

5、歸并排序

6、快速排序

7、堆排序

8、計數排序

9、桶排序

10、基數排序

繼續閱讀

C語言第四章自述2第四章選擇結構程式設計

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

C++ 多線程用條件變量确定線程的執行順序而不是使用 sleep(1)

POJ 1284 Primitive Roots (歐拉函數&原根定理)

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

成員函數初始化清單

2021-08-13c++——類之操作符重載

swmm與lisflood-fp源碼如何一起編譯 CMake指令

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述