排序算法

第二部分：排序算法

---

第8讲：冒泡排序

🔑 知识点讲解

核心思想：相邻元素两两比较，每轮将最大的"冒泡"到末尾。

过程（升序）：
第1轮：比较 n-1 次，最大值到 a[n-1]
第2轮：比较 n-2 次，次大值到 a[n-2]
...

优化：如果某一轮没有发生交换，说明已经有序，可以提前终止。

时间复杂度：
    最好：O(n)   —— 已经有序
    最坏：O(n²)  —— 逆序
    平均：O(n²)
空间复杂度：O(1)
稳定性：稳定（相等元素不交换）

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;  // 优化标志
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;  // 没有交换，提前退出
    }
}

---

第9讲：选择排序

🔑 知识点讲解

核心思想：每轮从未排序部分选出最小值，放到已排序部分的末尾。

过程：
第1轮：在 a[0..n-1] 找最小值，与 a[0] 交换
第2轮：在 a[1..n-1] 找最小值，与 a[1] 交换
...

时间复杂度：始终 O(n²)（不管是否有序）
空间复杂度：O(1)
稳定性：不稳定（如 [5a, 5b, 2] -> [2, 5b, 5a]）

void selectionSort(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;
        }
        if (minIdx != i) {
            int temp = a[i];
            a[i] = a[minIdx];
            a[minIdx] = temp;
        }
    }
}

---

第10讲：插入排序

🔑 知识点讲解

核心思想：像打扑克牌一样，将新元素插入已排序序列的正确位置。

过程：
a[0] 默认有序
将 a[1]，插入到 a[0..0] 中的合适位置
将 a[2]，插入到 a[0..1] 中的合适位置
...

时间复杂度：
    最好：O(n)   —— 已经有序
    最坏：O(n²)  —— 逆序
空间复杂度：O(1)
稳定性：稳定

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];  // 后移
            j--;
        }
        a[j + 1] = key;  // 插入
    }
}

---

第11讲：快速排序 ⭐（重点）

🔑 知识点讲解

核心思想：分治法
1. 选一个基准元素（pivot）
2. 将数组分成两部分：小于 pivot 的在左，大于 pivot 的在右
3. 递归排序左右两部分

选 pivot 策略：
    - 取第一个元素（简单但可能退化）
    - 取中间元素
    - 三数取中法（推荐）
    - 随机选择

时间复杂度：
    最好/平均：O(nlogn)
    最坏：O(n²) —— 每次 pivot 都是最小/最大
空间复杂度：O(logn)（递归栈）
稳定性：不稳定

#include <stdio.h>
void quickSort(int a[], int left, int right) {
    if (left >= right) return;
    
    int pivot = a[left];  // 选第一个作为基准
    int i = left, j = right;
    
    while (i < j) {
        // 从右往左找小于 pivot 的元素
        while (i < j && a[j] >= pivot) j--;
        a[i] = a[j];
        // 从左往右找大于 pivot 的元素
        while (i < j && a[i] <= pivot) i++;
        a[j] = a[i];
    }
    a[i] = pivot;  // pivot 归位
    quickSort(a, left, i - 1);   // 排左半部分
    quickSort(a, i + 1, right);  // 排右半部分
}

int main() {
    int a[] = {5, 3, 8, 1, 9, 2, 7};
    int n = sizeof(a) / sizeof(a[0]);
    
    quickSort(a, 0, n - 1);
    
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
    
    return 0;
}

✏️ 练习：排序综合

题目：输入 n 个整数，分别用冒泡、选择、插入、快排四种方法排序，并输出每种排序的比较次数。

#include <stdio.h>
#include <string.h>

long long cmpCount;

void bubbleSortCount(int a[], int n) {
    cmpCount = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            cmpCount++;
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j+1]; a[j+1] = t;
            }
        }
    }
}

void selectionSortCount(int a[], int n) {
    cmpCount = 0;
    for (int i = 0; i < n - 1; i++) {
        int m = i;
        for (int j = i + 1; j < n; j++) {
            cmpCount++;
            if (a[j] < a[m]) m = j;
        }
        int t = a[i]; a[i] = a[m]; a[m] = t;
    }
}

void insertionSortCount(int a[], int n) {
    cmpCount = 0;
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0) {
            cmpCount++;
            if (a[j] > key) { a[j+1] = a[j]; j--; }
            else break;
        }
        a[j+1] = key;
    }
}

void quickSortCount(int a[], int l, int r) {
    if (l >= r) return;
    int pivot = a[l], i = l, j = r;
    while (i < j) {
        while (i < j) { cmpCount++; if (a[j] >= pivot) j--; else break; }
        a[i] = a[j];
        while (i < j) { cmpCount++; if (a[i] <= pivot) i++; else break; }
        a[j] = a[i];
    }
    a[i] = pivot;
    quickSortCount(a, l, i-1);
    quickSortCount(a, i+1, r);
}

int main() {
    int n;
    scanf("%d", &n);
    int orig[10000], a[10000];
    for (int i = 0; i < n; i++) scanf("%d", &orig[i]);
    
    memcpy(a, orig, n * sizeof(int));
    bubbleSortCount(a, n);
    printf("冒泡排序比较次数: %lld\n", cmpCount);
    
    memcpy(a, orig, n * sizeof(int));
    selectionSortCount(a, n);
    printf("选择排序比较次数: %lld\n", cmpCount);
    
    memcpy(a, orig, n * sizeof(int));
    insertionSortCount(a, n);
    printf("插入排序比较次数: %lld\n", cmpCount);
    
    memcpy(a, orig, n * sizeof(int));
    cmpCount = 0;
    quickSortCount(a, 0, n-1);
    printf("快速排序比较次数: %lld\n", cmpCount);
    
    return 0;
}

---

第12讲：归并排序 ⭐

🔑 知识点讲解

核心思想：分治法
1. 将数组分成两半
2. 分别递归排序
3. 合并两个有序数组（Merge 操作是关键）

合并过程：
    用两个指针分别指向两个有序子数组的头部
    比较，较小的放入临时数组
    最后把剩余的放入

时间复杂度：始终 O(nlogn)（比快排稳定）
空间复杂度：O(n)（需要临时数组）
稳定性：稳定 ⭐（这是归并排序的重要优势）

#include <stdio.h>

int temp[100000];  // 临时数组

void merge(int a[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    
    while (i <= mid && j <= right) {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
    while (i <= mid)   temp[k++] = a[i++];
    while (j <= right) temp[k++] = a[j++];
    
    // 拷贝回原数组
    for (int i = left; i <= right; i++)
        a[i] = temp[i];
}

void mergeSort(int a[], int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(a, left, mid);
    mergeSort(a, mid + 1, right);
    merge(a, left, mid, right);
}

int main() {
    int a[] = {38, 27, 43, 3, 9, 82, 10};
    int n = 7;
    
    mergeSort(a, 0, n - 1);
    
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

---

第13讲：堆排序 ⭐⭐

🔑 知识点讲解

核心思想：利用堆（完全二叉树）的性质排序

大顶堆：父节点 >= 子节点，用于升序排序
小顶堆：父节点 <= 子节点，用于降序排序

完全二叉树的数组表示（下标从 0 开始）：
    父节点: (i-1)/2
    左子节点: 2*i+1
    右子节点: 2*i+2

过程：
1. 建堆：从最后一个非叶节点开始，自底向上调整（heapify）
2. 排序：
   - 将堆顶（最大值）与末尾元素交换
   - 堆大小减 1
   - 对堆顶做 heapify
   - 重复

时间复杂度：O(nlogn)
空间复杂度：O(1)
稳定性：不稳定

#include <stdio.h>

void heapify(int a[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && a[left] > a[largest])
        largest = left;
    if (right < n && a[right] > a[largest])
        largest = right;
    
    if (largest != i) {
        int temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;
        heapify(a, n, largest);  // 递归调整
    }
}

void heapSort(int a[], int n) {
    // 1. 建大顶堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(a, n, i);
    
    // 2. 排序
    for (int i = n - 1; i > 0; i--) {
        int temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        heapify(a, i, 0);  // 注意堆大小是 i
    }
}

int main() {
    int a[] = {12, 11, 13, 5, 6, 7};
    int n = 6;
    heapSort(a, n);
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

---

📊 排序算法总结对比

排序算法	最好	平均	最坏	空间	稳定
冒泡	O(n)	O(n²)	O(n²)	O(1)	是
选择	O(n²)	O(n²)	O(n²)	O(1)	否
插入	O(n)	O(n²)	O(n²)	O(1)	是
快排	O(nlogn)	O(nlogn)	O(n²)	O(logn)	否
归并	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	是
堆排	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	否

🎯 面试必问：快排为什么平均最快？什么时候退化？怎么优化？