目录

一、排序基础概念

二、七大经典排序算法实现

1. 插入排序

2. 希尔排序（优化插入排序）

3. 选择排序

4. 堆排序

5. 冒泡排序

6. 快速排序（Hoare版本）

7. 归并排序

三、算法性能对比

四、应用场景建议

五、选择题精析

---

排序是计算机科学中最基础且重要的算法之一，本博客将系统梳理各类经典排序算法的核心原理、实现方式及性能分析。

一、排序基础概念

1. 排序定义：将一组记录按关键字大小递增或递减重新排列的操作

2. 稳定性：相同关键字的记录排序后相对位置不变

3. 分类：

   • 内部排序：数据全部在内存中（本章重点）

   • 外部排序：数据量过大需分批处理

二、七大经典排序算法实现

1. 插入排序

核心思想：将元素插入已排序序列的合适位置

void InsertSort(int* a, int n) {
    for(int i=1; i<n; i++) {
        int tmp = a[i], j=i-1;
        while(j>=0 && a[j]>tmp) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = tmp;
    }
}

特性：

• 时间复杂度：O(n²)（最优O(n)）

• 空间复杂度：O(1)

• 稳定排序

• 适用于小规模或基本有序数据

2. 希尔排序（优化插入排序）

核心思想：按增量分组进行插入排序，逐步缩小增量

void ShellSort(int* a, int n) {
    int gap = n;
    while(gap > 1) {
        gap = gap/3 + 1; // Knuth增量序列
        for(int i=gap; i<n; i++) {
            int tmp = a[i], j=i-gap;
            while(j>=0 && a[j]>tmp) {
                a[j+gap] = a[j];
                j -= gap;
            }
            a[j+gap] = tmp;
        }
    }
}

特性：

• 时间复杂度：O(n¹·²⁵) ~ O(1.6n¹·²⁵)

• 空间复杂度：O(1)

• 不稳定排序

3. 选择排序

核心思想：每次选择最小元素放到已排序序列末尾

void SelectSort(int* a, int n) {
    for(int i=0; i<n-1; i++) {
        int minIdx = i;
        for(int j=i+1; j<n; j++)
            if(a[j] < a[minIdx]) minIdx = j;
        swap(&a[i], &a[minIdx]);
    }
}

特性：

• 时间复杂度：O(n²)

• 空间复杂度：O(1)

• 不稳定排序

4. 堆排序

核心思想：建立大顶堆，将堆顶元素交换到末尾后调整

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

void HeapSort(int* a, int n) {
    // 建堆
    for(int i=(n-2)/2; i>=0; i--) 
        AdjustDown(a, n, i);
    
    // 排序
    for(int i=n-1; i>0; i--) {
        swap(&a[0], &a[i]);
        AdjustDown(a, i, 0);
    }
}

特性：

• 时间复杂度：O(nlogn)

• 空间复杂度：O(1)

• 不稳定排序

5. 冒泡排序

核心思想：相邻元素两两比较并交换

void BubbleSort(int* a, int n) {
    for(int i=0; i<n-1; i++) {
        bool swapped = false;
        for(int j=0; j<n-1-i; j++) {
            if(a[j] > a[j+1]) {
                swap(&a[j], &a[j+1]);
                swapped = true;
            }
        }
        if(!swapped) break;
    }
}

特性：

• 时间复杂度：O(n²)（最优O(n)）

• 空间复杂度：O(1)

• 稳定排序

6. 快速排序（Hoare版本）

核心思想：分治法，选取基准值分割序列

int PartSort(int* a, int left, int right) {
    int keyi = left;
    while(left < right) {
        while(left<right && a[right]>=a[keyi]) right--;
        while(left<right && a[left]<=a[keyi]) left++;
        swap(&a[left], &a[right]);
    }
    swap(&a[keyi], &a[left]);
    return left;
}

void QuickSort(int* a, int left, int right) {
    if(left >= right) return;
    
    // 三数取中优化（避免最坏情况）
    int mid = (left+right)/2;
    if(a[left] > a[right]) swap(&a[left], &a[right]);
    if(a[mid] > a[right]) swap(&a[mid], &a[right]);
    if(a[mid] > a[left]) swap(&a[mid], &a[left]);
    
    int div = PartSort(a, left, right);
    QuickSort(a, left, div-1);
    QuickSort(a, div+1, right);
}

特性：

• 时间复杂度：O(nlogn)

• 空间复杂度：O(logn)（递归栈）

• 不稳定排序

7. 归并排序

核心思想：分治法，合并两个有序序列

void Merge(int* a, int left, int mid, int right) {
    int* tmp = (int*)malloc((right-left+1)*sizeof(int));
    int i=left, j=mid+1, k=0;
    while(i<=mid && j<=right)
        tmp[k++] = a[i]<=a[j] ? a[i++] : a[j++];
    while(i<=mid) tmp[k++] = a[i++];
    while(j<=right) tmp[k++] = a[j++];
    memcpy(a+left, tmp, k*sizeof(int));
    free(tmp);
}

void MergeSort(int* a, int left, int right) {
    if(left >= right) return;
    int mid = (left+right)/2;
    MergeSort(a, left, mid);
    MergeSort(a, mid+1, right);
    Merge(a, left, mid, right);
}

特性：

• 时间复杂度：O(nlogn)

• 空间复杂度：O(n)

• 稳定排序

• 是外部排序的基础

三、算法性能对比

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
直接插入排序	O(n²)	O(n²)	O(1)	稳定
希尔排序	O(n¹·²⁵)	O(n²)	O(1)	不稳定
选择排序	O(n²)	O(n²)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(1)	不稳定
冒泡排序	O(n²)	O(n²)	O(1)	稳定
快速排序	O(nlogn)	O(n²)	O(logn)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(n)	稳定

⚠️ 实测性能（10万随机数，单位ms）：

  text

InsertSort: 4862
ShellSort: 24
SelectSort: 15236
HeapSort: 18
QuickSort: 12
MergeSort: 15

四、应用场景建议

1. 小规模数据：插入排序（稳定且实现简单）

2. 通用场景：快速排序（综合性能最优）

3. 内存敏感场景：堆排序（空间复杂度O(1)）

4. 稳定排序需求：归并排序（时间复杂度稳定O(nlogn)）

5. 数据范围集中：计数排序（时间复杂度O(n+k)）

核心结论：没有绝对最优的排序算法，需根据具体场景选择合适算法。理解各算法特性才能在实际问题中灵活运用。

五、选择题精析

1. 快速排序基于（ A.分治法 ）

2. 插入45需比较（ C.5次 ）

3. 占用O(n)空间的是（ D.归并排序 ）

4. 稳定且O(n²)的是（ B.冒泡排序 ）

5. 错误说法（ D.堆排序空间O(logn) ）→ 实际O(1)

6. 最坏时间复杂度最小的是（ A.堆排序 ）→ 恒为O(nlogn)

7. 一趟快排结果（ A.34,56,25,65,86,99,72,66 ）

完整代码实现：https://github.com/bit-tech/sort-algorithmshttps://github.com/bit-tech/sort-algorithms

通过系统实现七大经典排序算法，我们不仅掌握了它们的核心原理，更理解了不同场景下的适用策略。在实际开发中，应结合数据规模、有序程度、稳定性需求等因素选择最优算法。