数据结构：八种常见排序算法详解

void ShellSort(int* arr, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1; // +1 是因为当 gap=1 时是直接插入排序
        for (int i = 0; i < n - gap; i++) {
            int end = i;
            int tmp = arr[end + gap];
            while (end >= 0) {
                if (arr[end] > tmp) {
                    arr[end + gap] = arr[end];
                    end -= gap;
                } else {
                    break;
                }
            }
            arr[end + gap] = tmp;
        }
    }
}

关于时间复杂度 希尔排序的时间复杂度估算比较复杂，因为 gap 的取值很多，导致很难去精确计算。严蔚敏《数据结构》书中给出的时间复杂度为 O(n^1.5)，但在不同 gap 选取策略下会有所波动。

2.2 选择排序

核心思路 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2.2.1 直接选择排序

// 优化后：双向选择
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[maxi]) {
                maxi = i;
            }
            if (arr[i] < arr[mini]) {
                mini = i;
            }
        }
        if (begin == maxi) {
            maxi = mini;
        }
        Swap(&arr[mini], &arr[begin]);
        Swap(&arr[maxi], &arr[end]);
        ++begin;
        --end;
    }
}

特性总结

• 思考非常好理解，但是效率不是很好，实际中很少使用。
• 时间复杂度：O(N²)。
• 空间复杂度：O(1)。

2.2.2 堆排序

核心思路 利用堆积树（堆）这种数据结构所设计的一种排序算法。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

2.3 交换排序

核心思路 根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。特点是将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

2.3.1 冒泡排序

核心思路 每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。这是最基础的交换排序。

void BubbleSort(int* arr, int n) {
    int exchange = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                exchange = 1;
                Swap(&arr[j], &arr[j + 1]);
            }
        }
        if (exchange == 0) {
            break;
        }
    }
}

特性总结

• 时间复杂度：O(N²)。
• 空间复杂度：O(1)。

2.3.2 快速排序

核心思路 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法。任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程。

主框架：

void QuickSort(int* arr, int left, int right) {
    if (left >= right) return;
    int keyi = _QuickSort(arr, left, right);
    QuickSort(arr, left, keyi - 1);
    QuickSort(arr, keyi + 1, right);
}

2.3.2.1 Hoare 版本

思路

1. 创建左右指针，确定基准值。
2. right 从右向左找出比基准值小的数据，left 从左向右找出比基准值大的数据，左右指针数据交换，进入下次循环。

注意点

• 跳出循环后 right 位置的值一定不大于 key，因为 left 扫描过的数据均不大于 key。
• 相等值参与交换确实有额外消耗，但能避免大量重复数据无法有效分割的情况。

int _QuickSort_Hoare(int* arr, int left, int right) {
    int keyi = left;
    left++;
    while (left <= right) {
        while (left <= right && arr[right] > arr[keyi]) {
            --right;
        }
        while (left <= right && arr[left] < arr[keyi]) {
            ++left;
        }
        if (left <= right)
            Swap(&arr[left++], &arr[right--]);
    }
    Swap(&arr[keyi], &arr[right]);
    return right;
}

2.3.2.2 挖坑法

思路 创建左右指针。先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"；然后从左向右找出比基准大的数据，找到后立即放入右边坑中。结束循环后将最开始存储的分界值放入当前的"坑"中。

int _QuickSort_Pit(int* arr, int left, int right) {
    int hole = left;
    int key = arr[hole];
    while (left < right) {
        while (left < right && arr[right] > key) {
            --right;
        }
        arr[hole] = arr[right];
        hole = right;
        while (left < right && arr[left] < key) {
            ++left;
        }
        arr[hole] = arr[left];
        hole = left;
    }
    arr[hole] = key;
    return hole;
}

2.3.2.3 Lomuto 前后指针

思路 创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。

int _QuickSort_Lomuto(int* arr, int left, int right) {
    int prev = left, cur = left + 1;
    int key = left;
    while (cur <= right) {
        if (arr[cur] < arr[key] && ++prev != cur) {
            Swap(&arr[cur], &arr[prev]);
        }
        ++cur;
    }
    Swap(&arr[key], &arr[prev]);
    return prev;
}

快速排序特性总结

• 平均时间复杂度：O(nlogn)。
• 空间复杂度：O(logn)（递归栈）。

2.3.2.4 非递归版本

思路 非递归版本的快速排序需要借助数据结构：栈。模拟递归调用的过程。

void QuickSortNonR(int* arr, 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);

        // 单趟逻辑（Lomuto 法）
        int keyi = begin;
        int prev = begin;
        int cur = begin + 1;
        while (cur <= end) {
            if (arr[cur] < arr[keyi] && ++prev != cur)
                Swap(&arr[prev], &arr[cur]);
            ++cur;
        }
        Swap(&arr[keyi], &arr[prev]);
        keyi = prev;

        // 入栈范围
        if (keyi + 1 < end) {
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }
        if (begin < keyi - 1) {
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
    }
    STDestroy(&st);
}

2.4 归并排序

核心思路 建立在归并操作上的一种有效的排序算法，采用分治法。将已有序的的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

代码实现 注意这里使用了辅助数组 tmp，最后需要将数据拷贝回原数组。

void _MergeSort(int* arr, int left, int right, int* tmp) {
    if (left >= right) return;
    int mid = (right + left) / 2;
    _MergeSort(arr, left, mid, tmp);
    _MergeSort(arr, mid + 1, right, tmp);

    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = begin1;

    while (begin1 <= end1 && begin2 <= end2) {
        if (arr[begin1] < arr[begin2]) {
            tmp[index++] = arr[begin1++];
        } else {
            tmp[index++] = arr[begin2++];
        }
    }
    while (begin1 <= end1) tmp[index++] = arr[begin1++];
    while (begin2 <= end2) tmp[index++] = arr[begin2++];

    for (int i = left; i <= right; i++) {
        arr[i] = tmp[i];
    }
}

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

特性总结

• 时间复杂度：O(nlogn)。
• 空间复杂度：O(n)。

2.5 测试代码：排序性能对比

为了直观感受不同算法的效率，我们可以编写一个简单的测试程序，生成随机数据并计时。

void TestOP() {
    srand(time(0));
    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(); 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 begin1 = clock(); InsertSort(a1, N); int end1 = clock();
    int begin2 = clock(); ShellSort(a2, N); int end2 = clock();
    int begin3 = clock(); SelectSort(a3, N); int end3 = clock();
    int begin4 = clock(); HeapSort(a4, N); int end4 = clock();
    int begin5 = clock(); QuickSort(a5, 0, N - 1); int end5 = clock();
    int begin6 = clock(); MergeSort(a6, N); int end6 = clock();
    int begin7 = clock(); BubbleSort(a7, N); int end7 = clock();

    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    printf("SelectSort:%d\n", end3 - begin3);
    printf("HeapSort:%d\n", end4 - begin4);
    printf("QuickSort:%d\n", end5 - begin5);
    printf("MergeSort:%d\n", end6 - end6);
    printf("BubbleSort:%d\n", end7 - begin7);

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

2.6 非比较排序

2.6.1 计数排序

核心思路 又称为鸽巢原理，是对哈希直接定址法的变形应用。

1. 统计相同元素出现次数。
2. 根据统计的结果将序列回收到原来的序列中。

void CountSort(int* arr, int n) {
    int min = arr[0], max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }

    int range = max - min + 1;
    int* count = (int*)malloc(sizeof(int) * range);
    if (count == NULL) {
        perror("malloc fail");
        exit(1);
    }

    memset(count, 0, sizeof(int) * range);

    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }

    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i]--) {
            arr[index++] = i + min;
        }
    }
    free(count);
}

特性总结

• 在数据范围集中时，效率很高，但是适用范围及场景有限。
• 时间复杂度：O(n + range)。
• 空间复杂度：O(range)。
• 稳定性：稳定。

3. 排序算法复杂度及稳定性分析

稳定性定义 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的。

各算法对比

• 稳定排序：直接插入、希尔（通常不稳定）、冒泡、归并、计数。
• 不稳定排序：直接选择、堆排序、快速排序。

注意：希尔排序的稳定性取决于具体实现和增量序列，通常视为不稳定。

完整代码参考

为了方便大家复制调试，以下是主要函数的汇总（包含头文件依赖）。

// Sort.h
#pragma once
#include<stdio.h>
#include<memory.h>
#include<stdlib.h>

void InsertSort(int* arr, int n);
void ShellSort(int* arr, int n);
void SelectSort(int* arr, int n);
void HeapSort(int* arr, int n);
void BubbleSort(int* arr, int n);
void QuickSort(int* arr, int left, int right);
void QuickSortNonR(int* arr, int left, int right);
void MergeSort(int* arr, int n);
void CountSort(int* arr, int n);
void Swap(int* x, int* y);

// Sort.c
#include"Sort.h"
#include"Stack.h"

void InsertSort(int* arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        int end = i;
        int tmp = arr[end + 1];
        while (end >= 0) {
            if (arr[end] > tmp) {
                arr[end + 1] = arr[end];
                end--;
            } else {
                break;
            }
        }
        arr[end + 1] = tmp;
    }
}

void ShellSort(int* arr, int n) {
    int gap = n;
    while (gap > 1) {
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++) {
            int end = i;
            int tmp = arr[end + gap];
            while (end >= 0) {
                if (arr[end] > tmp) {
                    arr[end + gap] = arr[end];
                    end -= gap;
                } else {
                    break;
                }
            }
            arr[end + gap] = tmp;
        }
    }
}

void Swap(int* x, int* y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

void AdjustDown(int* arr, int parent, int n) {
    int child = parent * 2 + 1;
    while (child < n) {
        if (child + 1 < n && arr[child] < arr[child + 1]) {
            child++;
        }
        if (arr[child] > arr[parent]) {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

void HeapSort(int* arr, int n) {
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(arr, i, n);
    }
    int end = n - 1;
    while (end > 0) {
        Swap(&arr[0], &arr[end]);
        AdjustDown(arr, 0, end);
        end--;
    }
}

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[maxi]) maxi = i;
            if (arr[i] < arr[mini]) mini = i;
        }
        if (begin == maxi) maxi = mini;
        Swap(&arr[mini], &arr[begin]);
        Swap(&arr[maxi], &arr[end]);
        ++begin;
        --end;
    }
}

void BubbleSort(int* arr, int n) {
    int exchange = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                exchange = 1;
                Swap(&arr[j], &arr[j + 1]);
            }
        }
        if (exchange == 0) break;
    }
}

int _QuickSort_Hoare(int* arr, int left, int right) {
    int keyi = left; left++;
    while (left <= right) {
        while (left <= right && arr[right] > arr[keyi]) --right;
        while (left <= right && arr[left] < arr[keyi]) ++left;
        if (left <= right) Swap(&arr[left++], &arr[right--]);
    }
    Swap(&arr[keyi], &arr[right]);
    return right;
}

int _QuickSort_Pit(int* arr, int left, int right) {
    int hole = left; int key = arr[hole];
    while (left < right) {
        while (left < right && arr[right] > key) --right;
        arr[hole] = arr[right]; hole = right;
        while (left < right && arr[left] < key) ++left;
        arr[hole] = arr[left]; hole = left;
    }
    arr[hole] = key;
    return hole;
}

int _QuickSort_Lomuto(int* arr, int left, int right) {
    int prev = left, cur = left + 1; int key = left;
    while (cur <= right) {
        if (arr[cur] < arr[key] && ++prev != cur) Swap(&arr[cur], &arr[prev]);
        ++cur;
    }
    Swap(&arr[key], &arr[prev]);
    return prev;
}

void QuickSort(int* arr, int left, int right) {
    if (left >= right) return;
    int keyi = _QuickSort_Lomuto(arr, left, right);
    QuickSort(arr, left, keyi - 1);
    QuickSort(arr, keyi + 1, right);
}

void QuickSortNonR(int* arr, 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 keyi = begin; int prev = begin; int cur = begin + 1;
        while (cur <= end) {
            if (arr[cur] < arr[keyi] && ++prev != cur) Swap(&arr[prev], &arr[cur]);
            ++cur;
        }
        Swap(&arr[keyi], &arr[prev]); keyi = prev;
        if (keyi + 1 < end) { STPush(&st, end); STPush(&st, keyi + 1); }
        if (begin < keyi - 1) { STPush(&st, keyi - 1); STPush(&st, begin); }
    }
    STDestroy(&st);
}

void _MergeSort(int* arr, int left, int right, int* tmp) {
    if (left >= right) return;
    int mid = (right + left) / 2;
    _MergeSort(arr, left, mid, tmp);
    _MergeSort(arr, mid + 1, right, tmp);
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = begin1;
    while (begin1 <= end1 && begin2 <= end2) {
        if (arr[begin1] < arr[begin2]) tmp[index++] = arr[begin1++];
        else tmp[index++] = arr[begin2++];
    }
    while (begin1 <= end1) tmp[index++] = arr[begin1++];
    while (begin2 <= end2) tmp[index++] = arr[begin2++];
    for (int i = left; i <= right; i++) arr[i] = tmp[i];
}

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

void CountSort(int* arr, int n) {
    int min = arr[0], max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
    int range = max - min + 1;
    int* count = (int*)malloc(sizeof(int) * range);
    if (count == NULL) { perror("malloc fail"); exit(1); }
    memset(count, 0, sizeof(int) * range);
    for (int i = 0; i < n; i++) count[arr[i] - min]++;
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i]--) arr[index++] = i + min;
    }
    free(count);
}

// Stack.c
#include"Stack.h"

void STInit(ST* ps) {
    ps->arr = NULL; ps->top = ps->capacity = 0;
}

void STDestroy(ST* ps) {
    if (ps->arr) free(ps->arr);
    ps->arr = NULL; ps->top = ps->capacity = 0;
}

void STPush(ST* ps, STDataType x) {
    assert(ps);
    if (ps->top == ps->capacity) {
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
        if (tmp == NULL) { perror("realloc"); exit(1); }
        ps->arr = tmp; ps->capacity = newCapacity;
    }
    ps->arr[ps->top++] = x;
}

void STPop(ST* ps) {
    assert(!STEmpty(ps));
    ps->top--;
}

STDataType STTop(ST* ps) {
    assert(!STEmpty(ps));
    return ps->arr[ps->top - 1];
}

int STSize(ST* ps) {
    assert(ps);
    return ps->top;
}

bool STEmpty(ST* ps) {
    assert(ps);
    return ps->top == 0;
}