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

注意： 希尔排序的时间复杂度估算比较复杂，取决于 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^2)，空间复杂度 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 于 1962 年提出的一种二叉树结构的交换排序方法。其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程。

2.3.2.1 Hoare 版本

创建左右指针，确定基准值。right 从右向左找出比基准值小的数据，left 从左向右找出比基准值大的数据，左右指针数据交换。

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

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

提示： 如果基准值找得不好或者数组本身有序，时间复杂度可能退化为 n^2。

2.3.2.2 挖坑法

思路：先从右向左找出比基准小的数据，放入左边坑中，当前位置变为新的"坑"，然后从左向右找出比基准大的数据，放入右边坑中，最后将分界值放入当前的"坑"中。

2.3.2.3 Lomuto 前后指针

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

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 或 Hoare 实现
        // ... 此处省略具体单趟代码以保持篇幅，逻辑同上 ...
        // 入栈逻辑：if(keyi + 1 < end) { STPush(&st, end); STPush(&st, keyi + 1); }
        // ... 同理处理左侧 ...
    }
    STDestroy(&st);
}

快速排序特性总结：

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

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);
    // 初始化多个副本用于不同算法测试...
    // 分别调用 InsertSort, ShellSort, QuickSort 等
    // 使用 clock() 计算耗时
    free(a1);
    // 释放其他内存...
}

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);
    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)，稳定。

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

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

4. 完整代码参考

以下整理了核心函数的实现，包含辅助结构如栈的实现，供实战参考。

// Sort.h
#include <stdio.h>
#include <stdlib.h>
#include <string.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 MergeSort(int* arr, int n);
void CountSort(int* arr, int n);

// Stack.h
typedef int STDataType;
typedef struct Stack {
    STDataType* arr;
    int top;
    int capacity;
} ST;

void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
bool STEmpty(ST* ps);

// 辅助函数
void Swap(int* x, int* y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

在实际开发中，建议优先使用标准库提供的排序函数（如 qsort），但在面试或底层优化场景中，掌握上述手写实现至关重要。