八种排序算法的原理与实现要点

它的属性是：

• 时间复杂度：取决于增量序列，Knuth 增量下通常认为约为 O(n^1.3)
• 空间复杂度：O(1)
• 稳定性：不稳定

选择排序

简单选择排序

每一轮从未排序区间里挑出最小值，放到前面。思路很朴素，代码也直白，但代价是比较次数基本固定，数据一大就不太划算。

void SelectSort(int* a, int n) {
    int begin = 0, end = n - 1;
    while (begin < end) {
        int minn = begin, maxx = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (a[i] < a[minn]) minn = i;
            if (a[i] > a[maxx]) maxx = i;
        }
        Swap(&a[minn], &a[begin]);
        if (maxx == begin) maxx = minn;
        Swap(&a[maxx], &a[end]);
        begin++; end--;
    }
}

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

它的特点：

• 时间复杂度：始终 O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定

堆排序

堆排序利用堆这种完全二叉树结构，每次都能快速拿到最大值或最小值。它的好处是时间复杂度稳定，空间也省，适合对内存比较敏感的场景。

void AdjustDown(int* a, int parent, int n) {
    int maxChild = (parent << 1) + 1;
    while (maxChild < n) {
        if (maxChild + 1 < n && a[maxChild + 1] > a[maxChild]) {
            maxChild += 1;
        }
        if (a[parent] >= a[maxChild]) return;
        Swap(&a[parent], &a[maxChild]);
        parent = maxChild;
        maxChild = (parent << 1) + 1;
    }
}

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

属性如下：

• 时间复杂度：O(n log n)
• 空间复杂度：O(1)
• 稳定性：不稳定

交换排序

冒泡排序

冒泡排序靠相邻元素比较，把较大的值一轮一轮往后推。写法简单，教学场景里很常见，但性能确实一般，更多是帮助理解交换和循环控制。

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

它的特点：

• 时间复杂度：最坏 O(n²)，最好 O(n)
• 稳定性：稳定

快速排序

快速排序的核心是分治：选一个基准，把数组分成两边，再递归处理。这个算法在工程里很常见，快是真的快，但最怕极端数据把它拖进最坏情况，所以基准的选取很关键。

分区策略常见三种：

1. Hoare 对撞指针：左右指针向中间扫，最后在相遇位置放基准。
2. Lomuto 快慢指针：快指针遍历，慢指针维护'小于基准'的边界。
3. 挖坑法：左右交替填坑，最后把基准放回去。

递归实现如下：

int PartSort3(int* a, int left, int right) {
    int mid = GetMid(a, left, right);
    Swap(&a[left], &a[mid]);
    int key = a[left];
    int hole = left;
    int begin = left, end = right;
    while (begin < end) {
        while (begin < end && a[end] >= key) end--;
        a[hole] = a[end]; hole = end;
        while (begin < end && a[begin] <= key) begin++;
        a[hole] = a[begin]; hole = begin;
    }
    a[hole] = key;
    return hole;
}

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

非递归版本一般用栈模拟递归过程，主要是为了避免递归太深时的栈溢出问题。这个版本更稳一点，代价是代码会啰嗦些。

它的属性：

• 时间复杂度：平均 O(n log n)，最坏 O(n²)
• 空间复杂度：O(log n)
• 稳定性：不稳定

归并排序

归并排序也是分治法，但它的节奏和快速排序相反：先不断拆分，拆到长度为 1，再一层层合并回去。它的优势是时间复杂度很稳，稳定性也好，缺点就是要额外数组。

void _MergeSort(int* a, int* tmp, int begin, int end) {
    if (begin >= end) return;
    int mid = begin + ((end - begin) >> 1);
    _MergeSort(a, tmp, begin, mid);
    _MergeSort(a, tmp, mid + 1, end);
    
    int begin1 = begin, end1 = mid;
    int begin2 = mid + 1, end2 = end;
    int pos = begin;
    
    while (begin1 <= end1 && begin2 <= end2) {
        if (a[begin1] <= a[begin2]) tmp[pos++] = a[begin1++];
        else tmp[pos++] = a[begin2++];
    }
    while (begin1 <= end1) tmp[pos++] = a[begin1++];
    while (begin2 <= end2) tmp[pos++] = a[begin2++];
    memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

void MergeSort(int* a, int n) {
    int* tmp = (int*)malloc(n * sizeof(int));
    if (!tmp) { perror("malloc fail"); return; }
    _MergeSort(a, tmp, 0, n - 1);
    free(tmp);
}

它的特点：

• 时间复杂度：始终 O(n log n)
• 空间复杂度：O(n)
• 稳定性：稳定

计数排序

计数排序不比较元素本身，而是统计每个值出现了多少次，再按次数回填。它快得很直接，但前提是数值范围不能太大，不然计数数组会把内存吃掉。

void CountSort(int* a, int n) {
    int minn = a[0], maxx = a[0];
    for (int i = 0; i < n; i++) {
        if (a[i] < minn) minn = a[i];
        if (a[i] > maxx) maxx = a[i];
    }
    int range = maxx - minn + 1;
    int* count = (int*)calloc(range, sizeof(int));
    if (!count) { perror("calloc fail"); return; }
    
    for (int i = 0; i < n; i++) count[a[i] - minn]++;
    
    int pos = 0;
    for (int i = 0; i < range; i++) {
        while (count[i]--) a[pos++] = i + minn;
    }
    free(count);
}

属性如下：

• 时间复杂度：O(n + k)
• 空间复杂度：O(n + k)
• 稳定性：稳定

这几种排序怎么选

实际选型时，别只盯着时间复杂度。数据规模、是否稳定、内存够不够，这三个条件通常比'理论上谁更快'更有决定性。