数据结构：深入理解八种常见排序算法

注意：希尔排序的时间复杂度与 gap 的选取有关，理论上较难精确计算，通常认为优于 O(n²)。

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;
        }
    }
}

2.3.2 快速排序

快速排序是 Hoare 提出的一种二叉树结构的交换排序方法，平均性能最好，是实际应用中的首选。

主框架

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 版本

思路 左右指针分别向中间移动，找到逆序对后交换。最后将基准值放到正确位置。

代码实现

int _QuickSort(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(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 前后指针

思路 用 prev 和 cur 两个指针，cur 遍历，prev 指向小于基准值的区域边界。遇到小的就交换。

代码实现

int _QuickSort(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;
}

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);
        
        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 归并排序

核心思路 采用分治法。先将序列二分，直到每个子序列只有一个元素，然后两两合并成有序序列。

代码实现

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 begin1 = clock(); InsertSort(a1, N); int end1 = clock();
    int begin2 = clock(); ShellSort(a2, N); int end2 = clock();
    // ... 其他算法测试 ...
    
    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
    // ... 输出结果 ...
    
    free(a1); free(a2); // 释放内存
}

2.6 非比较排序

2.6.1 计数排序

核心思路 统计相同元素出现的次数，然后根据统计结果将序列回收到原数组。适用于数据范围集中的场景。

代码实现

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*)calloc(range, sizeof(int));
    if (count == NULL) { perror("malloc fail"); exit(1); }
    
    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. 排序算法复杂度及稳定性分析

稳定性定义 若排序后，相同关键字记录的相对次序保持不变，则为稳定排序。否则为不稳定。

在实际开发中，选择排序算法时，除了考虑时间复杂度，还要关注数据规模、是否允许额外空间以及对稳定性的要求。例如，对于大规模数据且需要稳定性的场景，归并排序是不错的选择；而对于内存受限的场景，堆排序或快速排序可能更合适。