C语言常见排序算法详解：写法、时间复杂度与空间复杂度

排序是编程中最基础也是最重要的算法之一。在C语言中，排序算法的实现既考察对指针和数组的掌握，也体现对算法效率的理解。本文将介绍几种常见的排序算法，包括它们的C语言实现、时间复杂度和空间复杂度，并附上稳定性说明，方便你在实际开发中做出选择。

1. 冒泡排序（Bubble Sort）

基本思想：重复遍历待排序数组，每次比较相邻两个元素，若顺序错误则交换，直到没有需要交换的元素为止。

C语言实现：

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break; // 提前退出优化
    }
}

- **时间复杂度**：最好 O(n)（已有序，带优化），平均 O(n²)，最坏 O(n²)
- **空间复杂度**：O(1)
- **稳定性**：稳定

## 2. 选择排序（Selection Sort）

**基本思想**：每一轮从未排序区间中选出最小（或最大）元素，放到已排序区间的末尾。

**C语言实现**：

```c
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

• 时间复杂度：最好/平均/最坏均为 O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定（交换可能破坏相等元素的相对顺序）

3. 插入排序（Insertion Sort）

基本思想：将数组分为已排序和未排序两部分，每次取未排序部分的第一个元素，插入到已排序部分的合适位置。

C语言实现：

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

• 时间复杂度：最好 O(n)（已有序），平均 O(n²)，最坏 O(n²)
• 空间复杂度：O(1)
• 稳定性：稳定
• 适用场景：小规模数据或基本有序的数据，实际性能往往优于冒泡和选择排序。

4. 希尔排序（Shell Sort）

基本思想：插入排序的改进版，通过设定增量序列对数组进行分组插入排序，逐步缩小增量直至为1。

C语言实现：

void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > key) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = key;
        }
    }
}

• 时间复杂度：取决于增量序列，平均约 O(n^1.3)，最坏 O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定

5. 归并排序（Merge Sort）

基本思想：分治法。将数组递归分成两半，分别排序后合并两个有序子数组。

C语言实现：

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    free(L);
    free(R);
}

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

• 时间复杂度：最好/平均/最坏均为 O(n log n)
• 空间复杂度：O(n)（需要辅助数组）
• 稳定性：稳定
• 适用场景：对稳定性有要求，或数据量大且对最坏情况性能有保证的场景。

6. 快速排序（Quick Sort）

基本思想：分治法。选取一个基准值（pivot），将数组划分为小于基准和大于基准的两部分，再递归排序。

C语言实现（以最后一个元素为基准）：

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

• 时间复杂度：最好/平均 O(n log n)，最坏 O(n²)（如已有序且基准选择不当）
• 空间复杂度：O(log n)（递归栈），最坏 O(n)
• 稳定性：不稳定
• 适用场景：通用场景下性能优秀，是实际应用中最常用的排序算法之一。

7. 堆排序（Heap Sort）

基本思想：利用堆数据结构。先构建大顶堆，然后反复将堆顶元素与末尾元素交换并调整堆。

C语言实现：

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

• 时间复杂度：最好/平均/最坏均为 O(n log n)
• 空间复杂度：O(1)（原地排序）
• 稳定性：不稳定
• 适用场景：对空间要求严格且需要最坏情况 O(n log n) 保证的场景。

复杂度与稳定性对比表

如何选择排序算法？

• 数据量小（如 n < 50）：插入排序简单高效，实际表现常优于复杂算法。
• 数据基本有序：插入排序接近 O(n)，冒泡排序（带优化）也可。
• 需要稳定排序：归并排序或插入排序。
• 内存受限：堆排序（原地、O(n log n)）。
• 通用高性能：快速排序通常是首选，注意随机化基准以避免最坏情况。
• 对最坏情况有要求：归并排序或堆排序。

小结

理解每种排序算法的实现细节、时间/空间复杂度和稳定性，是写出高效C代码的基础。实际工程中，C标准库的 qsort 通常基于快速排序实现（并做了优化），在需要稳定排序时可以考虑自己实现归并排序。建议动手实现并测试这些算法，加深对指针操作和算法思想的理解。

提示：本文示例默认对整型数组升序排序，实际使用时可根据类型泛化（如使用 void* 和比较函数）。