[5, 3, 8, 4, 2]
  ↓比較
[3, 5, 8, 4, 2]  交換 5>3
  ↓比較
[3, 5, 8, 4, 2]  不交換 5<8
  ↓比較
[3, 4, 8, 5, 2]  交換 8>4
  ↓比較
[3, 4, 2, 8, 5]  交換 8>2
第一趟結(jié)束，最大值8沉到最右

[3, 4, 2, 8, 5]
  ↓比較
[3, 4, 2, 8, 5]  不交換 3<4
  ↓比較
[2, 4, 3, 8, 5]  交換 4>2
  ↓比較
[2, 3, 4, 8, 5]  交換 4>3
第二趟結(jié)束，次大值5在8左邊

[2, 3, 4, 8, 5]
  ↓比較
[2, 3, 4, 8, 5]  不交換 2<3
  ↓比較
[2, 3, 4, 8, 5]  不交換 3<4
第三趟結(jié)束，無(wú)需交換，數(shù)組已有序

void Swap(int* a, int* b)
{
    int c = *a;
    *a = *b;
    *b = c;
}

void maopao(int* arr, int r)
{
    for (int i = 0; i < r - 1; i++)           // 趟數(shù)
    {
        int flag = 1;
        for (int j = 0; j < r - 1 - i; j++)   // 兩兩比較
        {
            if (arr[j] > arr[j + 1])
            {
                flag = 0;
                Swap(&arr[j], &arr[j + 1]);
            }
        }
        if (flag == 1) return;               // 提前結(jié)束優(yōu)化
    }
}

原始完全二叉樹(shù)：
        4
      /   \
    10      3
   /  \
  5    1

建堆過(guò)程（從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始向下調(diào)整）：
節(jié)點(diǎn)(10)是最后一個(gè)非葉子節(jié)點(diǎn)，比較10與孩子5、1，10最大無(wú)需交換
節(jié)點(diǎn)(4)與孩子10、3比較，4<10，交換
        10
      /    \
     4      3
    / \
   5   1

再調(diào)整節(jié)點(diǎn)(4)，與孩子5比較，4<5，交換
        10
      /    \
     5      3
    / \
   4   1

void Swap(int* a, int* b)
{
    int c = *a;
    *a = *b;
    *b = c;
}

// 向下調(diào)整算法 —— 構(gòu)建大堆
void AdjustDown(int* arr, int r, int parent)
{
    int child = parent * 2 + 1;
    while (child < r)
    {
        if (child + 1 < r && arr[child + 1] > arr[child])
        {
            child++;
        }
        if (arr[parent] < arr[child])
        {
            Swap(&arr[parent], &arr[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void Heappai(int* arr, int r)
{
    // 建堆 —— 從第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始向下調(diào)整
    for (int i = (r - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(arr, r, i);
    }

    // 排序：不斷將堆頂（最大值）與末尾交換，再調(diào)整堆
    int end = r;
    while (end)
    {
        Swap(&arr[0], &arr[--end]);
        AdjustDown(arr, end, 0);
    }
}

初始：已排序[4]，待插入[5, 2, 7, 1]

插入5：tep=5，end=0，4<5 不挪，插入到位置1
已排序[4, 5]，待插入[2, 7, 1]

插入2：tep=2，end=1，5>2 挪到位置2，end=0
              4>2 挪到位置1，end=-1
              插入到位置0
已排序[2, 4, 5]，待插入[7, 1]

插入7：tep=7，end=2，5<7 不挪，插入到位置3
已排序[2, 4, 5, 7]，待插入[1]

插入1：tep=1，end=3，7>1 挪，end=2
              5>1 挪，end=1
              4>1 挪，end=0
              2>1 挪，end=-1
              插入到位置0
最終：[1, 2, 4, 5, 7]

void insertsort(int a[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int end = i;
        int tep = a[end + 1];          // 保存待插入元素
        while (end >= 0)
        {
            if (a[end] > tep)          // 比待插入元素大，往后挪
            {
                a[end + 1] = a[end];
                end--;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tep;              // 插入到正確位置
    }
}

gap = 3 時(shí)，分組情況：
索引：  0  1  2  3  4  5  6  7
數(shù)據(jù)： 9  5  1  7  3  6  4  8
組別：  A  B  A  B  A  B  A  B

A組 [9, 1, 3, 4] 排序后：[1, 3, 4, 9]
B組 [5, 7, 6, 8] 排序后：[5, 6, 7, 8]

gap = 1 時(shí)，整體插入排序，此時(shí)數(shù)組已接近有序，效率極高

void shellsort(int a[], int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;            // 保證最后一次 gap=1
        for (int i = 0; i < n - gap; i++)
        {
            int end = i;
            int tep = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > tep)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tep;
        }
    }
}

初始：[3, 5, 1, 4, 2]
       ↑          ↑
      mini       maxi

第一輪找最小最大：
遍歷 [3,5,1,4,2]，發(fā)現(xiàn) mini=2（在索引4），maxi=5（在索引1）
交換 min 到開(kāi)頭，max 到末尾：
[2, 5, 1, 4, 3] ←→ [2, 3, 1, 4, 5]
  begin=1, end=3

第二輪：
遍歷 [5,1,4,3]，發(fā)現(xiàn) mini=1（在索引2），maxi=5（在索引0，但開(kāi)頭已處理）
因?yàn)?maxi==begin，需要將 maxi 修正為 mini（索引2）
交換：
[1, 3, 5, 4, 2]
  begin=2, end=2，結(jié)束

void SelectSort(int* arr, int n)
{
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; i++)
        {
            if (arr[i] < arr[mini]) mini = i;
            if (arr[i] > arr[maxi]) maxi = i;
        }
        // 注意：若最大值在開(kāi)頭，先交換會(huì)覆蓋 mini 的位置，需要修正
        if (maxi == begin) maxi = mini;
        Swap(&arr[mini], &arr[begin]);
        Swap(&arr[maxi], &arr[end]);
        begin++;
        end--;
    }
}

int GetMid(int* a, int left, int right)
{
    int mid = (left + right) / 2;
    if (a[left] > a[right])
    {
        if (a[right] > a[mid]) return right;
        else if (a[mid] > a[left]) return left;
        else return mid;
    }
    else
    {
        if (a[mid] < a[left]) return left;
        else if (a[mid] > a[right]) return right;
        else return mid;
    }
}

int Quicksort(int* a, int left, int right)
{
    int mid = GetMid(a, left, right);
    Swap(&a[left], &a[mid]);           // 三數(shù)取中優(yōu)化
    int key = left;
    int begin = left, end = right;
    while (begin < end)
    {
        while (begin < end && a[end] >= a[key]) end--;
        while (begin < end && a[begin] <= a[key]) begin++;
        Swap(&a[begin], &a[end]);
    }
    Swap(&a[key], &a[begin]);
    return begin;
}

void QuickSort(int* a, int left, int right)
{
    if (left >= right) return;
    int key = Quicksort(a, left, right);
    QuickSort(a, left, key - 1);
    QuickSort(a, key + 1, right);
}

void Quicksort2(int* a, int left, int right)
{
    if (left >= right) return;
    if (right - left + 1 < 10)         // 小區(qū)間優(yōu)化
    {
        insertsort(a + left, right - left + 1);
        return;
    }
    int key = Quicksort(a, left, right);
    Quicksort2(a, left, key - 1);
    Quicksort2(a, key + 1, right);
}

void QuickSortNonR(int* a, int left, int right)
{
    ST st;
    STInit(&st);
    STPush(&st, right);
    STPush(&st, left);
    while (!STEmpty(&st))
    {
        int begin = STTop(&st); STPop(&st);
        int end = STTop(&st);   STPop(&st);
        int key = partQuickSort(a, begin, end);
        if (key + 1 < end) { STPush(&st, end); STPush(&st, key + 1); }
        if (begin < key - 1) { STPush(&st, key - 1); STPush(&st, begin); }
    }
    STDestory(&st);
}

遞歸拆分：
[6, 5, 3, 1, 8, 7, 2, 4]
[6, 5, 3, 1]    [8, 7, 2, 4]
[6, 5]  [3, 1]  [8, 7]  [2, 4]
[6] [5] [3] [1] [8] [7] [2] [4]   ← 單個(gè)元素，遞歸終止

兩兩合并（歸并）：
[5, 6]  [1, 3]  [7, 8]  [2, 4]
[1, 3, 5, 6]    [2, 4, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]   ← 完全有序

void _MergeSort(int* a, int* tmp, int begin, int end)
{
    if (begin == end) return;
    int mid = (begin + end) / 2;
    _MergeSort(a, tmp, begin, mid);
    _MergeSort(a, tmp, mid + 1, end);

    // 歸并
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int i = begin;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] <= a[begin2]) tmp[i++] = a[begin1++];
        else                        tmp[i++] = a[begin2++];
    }
    while (begin1 <= end1) tmp[i++] = a[begin1++];
    while (begin2 <= end2) tmp[i++] = a[begin2++];
    memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    _MergeSort(a, tmp, 0, n - 1);
    free(tmp);
}

void _MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    int gap = 1;
    while (gap < n)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            if (begin2 >= n) break;
            if (end2 >= n) end2 = n - 1;
            int j = begin1;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] <= a[begin2]) tmp[j++] = a[begin1++];
                else                        tmp[j++] = a[begin2++];
            }
            while (begin1 <= end1) tmp[j++] = a[begin1++];
            while (begin2 <= end2) tmp[j++] = a[begin2++];
            memcpy(a + i, tmp + i, (end2 - begin1 + 1) * sizeof(int));
        }
        gap *= 2;
    }
    free(tmp);
}

Step 1：找最小最大值
min=1, max=4，range = 4-1+1 = 4

Step 2：創(chuàng)建計(jì)數(shù)數(shù)組（長(zhǎng)度4，全0）
count: [0, 0, 0, 0]
        ↓
       index

Step 3：遍歷原數(shù)組，統(tǒng)計(jì)并映射
a[0]=4 → count[4-1]=count[3]++
a[1]=2 → count[2-1]=count[1]++
a[2]=4 → count[3]++
a[3]=1 → count[1-1]=count[0]++
a[4]=3 → count[3-1]=count[2]++

count: [1, 1, 1, 2]
         ↑  ↑  ↑  ↑
        1   2   3   4  （+min還原）

Step 4：遍歷計(jì)數(shù)數(shù)組，回寫(xiě)原數(shù)組
count[0]=1 → a[0]=1+1=2
count[1]=1 → a[1]=2+1=3
count[2]=1 → a[2]=3+1=4
count[3]=2 → a[3]=4+1=5, a[4]=5+1=6
最終：[2, 3, 4, 5, 6]

void contsort(int* a, int n)
{
    int min = a[0], max = a[0];
    for (int i = 1; i < n; i++)
    {
        if (a[i] < min) min = a[i];
        if (a[i] > max) max = a[i];
    }
    int range = max - min + 1;
    int* cout = (int*)calloc(range, sizeof(int));

    // 統(tǒng)計(jì)次數(shù)
    for (int i = 0; i < n; i++)
    {
        cout[a[i] - min]++;           // 映射到計(jì)數(shù)數(shù)組下標(biāo)
    }

    // 回寫(xiě)
    int j = 0;
    for (int i = 0; i < range; i++)
    {
        while (cout[i]--)
        {
            a[j++] = i + min;
        }
    }
    free(cout);
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

int main()
{
    srand((unsigned int)time(NULL));
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a2 = (int*)malloc(sizeof(int) * N);
    int* a3 = (int*)malloc(sizeof(int) * N);
    int* a4 = (int*)malloc(sizeof(int) * N);
    int* a5 = (int*)malloc(sizeof(int) * N);
    int* a6 = (int*)malloc(sizeof(int) * N);
    int* a7 = (int*)malloc(sizeof(int) * N);

    for (int i = 0; i < N; ++i)
    {
        a1[i] = rand() + i;
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        a5[i] = a1[i];
        a6[i] = a1[i];
        a7[i] = a1[i];
    }

    int begin7 = clock(); MergeSort(a7, N);        int end7 = clock();
    int begin6 = clock(); QuickSortNonR(a6, 0, N - 1); int end6 = clock();
    int begin5 = clock(); shellsort(a5, N);         int end5 = clock();
    int begin4 = clock(); Heappai(a4, N);          int end4 = clock();
    int begin3 = clock(); maopao(a3, N);           int end3 = clock();
    int begin2 = clock(); qsort(a2, N, sizeof(int), paixu); int end2 = clock();
    int begin1 = clock(); Quicksort2(a1, 0, N - 1); int end1 = clock();

    printf("排序 %d 個(gè)隨機(jī)數(shù)，各算法用時(shí)（毫秒）：\n", N);
    printf("MergeSort:       %d\n", end7 - begin7);
    printf("QuickSortNonR:   %d\n", end6 - begin6);
    printf("shellsort:       %d\n", end5 - begin5);
    printf("Heapsort:        %d\n", end4 - begin4);
    printf("bubblesort:      %d\n", end3 - begin3);
    printf("qsort:           %d\n", end2 - begin2);
    printf("Quicksort2:      %d\n", end1 - begin1);

    free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7);
    return 0;
}

排序 100000 個(gè)隨機(jī)數(shù)，各算法用時(shí)（毫秒）：
MergeSort:       4
QuickSortNonR:   4
shellsort:       6
Heapsort:        6
bubblesort:      3000+
qsort:           8
Quicksort2:      4

初始狀態(tài):  [5a, 3, 5b, 1, 3]
          a在b前，都是5

原始大文件（太大，無(wú)法一次讀入內(nèi)存）
        ↓
每次讀一塊數(shù)據(jù)進(jìn)內(nèi)存（比如 1GB）
        ↓
用內(nèi)排算法（快排/歸并排）排好這一塊
        ↓
寫(xiě)回磁盤(pán)，得到若干有序的小文件（稱(chēng)為"歸并段"）

多個(gè)有序小文件
        ↓
每次從各文件讀一個(gè)數(shù)（或一小批），選最小/最大的輸出
        ↓
繼續(xù)讀、繼續(xù)選，直到所有文件處理完畢
        ↓
最終得到完全有序的大文件

【階段一：分段內(nèi)排】
內(nèi)存每次最多3個(gè)數(shù)，分3次讀入：

讀入 [8, 3, 9] → 內(nèi)排 → [3, 8, 9] → 寫(xiě)回 temp1
讀入 [2, 7, 1] → 內(nèi)排 → [1, 2, 7] → 寫(xiě)回 temp2
讀入 [5, 4, 6] → 內(nèi)排 → [4, 5, 6] → 寫(xiě)回 temp3

得到三個(gè)有序文件：temp1=[3,8,9]  temp2=[1,2,7]  temp3=[4,5,6]

【階段二：多路歸并】
三路歸并：每次從 temp1/temp2/temp3 各讀一個(gè)數(shù)出來(lái)比較

第一輪：
比較 3(t1)、1(t2)、4(t3) → 選 1 → 輸出 [1]，從 temp2 補(bǔ)一個(gè)數(shù)
比較 3(t1)、2(t2)、4(t3) → 選 2 → 輸出 [1,2]，從 temp2 補(bǔ)一個(gè)數(shù)
比較 3(t1)、7(t2)、4(t3) → 選 3 → 輸出 [1,2,3]，從 temp1 補(bǔ)一個(gè)數(shù)
比較 8(t1)、7(t2)、4(t3) → 選 4 → 輸出 [1,2,3,4]，從 temp3 補(bǔ)一個(gè)數(shù)
比較 8(t1)、7(t2)、5(t3) → 選 5 → 輸出 [1,2,3,4,5]，從 temp3 補(bǔ)一個(gè)數(shù)
比較 8(t1)、7(t2)、6(t3) → 選 6 → 輸出 [1,2,3,4,5,6]，從 temp3 補(bǔ)一個(gè)數(shù)
...繼續(xù)，最終輸出 [1,2,3,4,5,6,7,8,9]