C语言：排序算法

一、排序算法分类

1. 按时间复杂度分类

• O(n²)算法：冒泡排序、选择排序、插入排序

• O(n log n)算法：快速排序、归并排序、堆排序

• O(n)算法：计数排序、桶排序、基数排序（线性排序，有特定条件）

2. 按稳定性分类

• 稳定排序：冒泡、插入、归并、计数、桶、基数

• 不稳定排序：选择、快速、堆

3. 按空间复杂度分类

• 原地排序：冒泡、选择、插入、快速、堆

• 非原地排序：归并、计数、桶、基数

二、基础排序算法实现与解析

1. 冒泡排序（Bubble Sort）

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        // 每次遍历将最大的元素"冒泡"到最后
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换相邻元素
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

特点：

• 时间复杂度：最好O(n)（已排序），最差O(n²)

• 空间复杂度：O(1)

• 稳定排序

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

2. 选择排序（Selection Sort）

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        // 找到未排序部分的最小元素
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 将最小元素交换到已排序部分的末尾
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

特点：

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

• 空间复杂度：O(1)

• 不稳定排序

• 交换次数少（最多n-1次）

3. 插入排序（Insertion Sort）

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(1)

• 稳定排序

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

三、高效排序算法实现与解析

1. 快速排序（Quick Sort）

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = low - 1; // i是小于基准的元素的边界
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            // 交换arr[i]和arr[j]
            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)（递归调用栈）

• 不稳定排序

• 实际应用中通常是最快的排序算法

2. 归并排序（Merge Sort）

// 合并两个有序数组
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    
    // 创建临时数组
    int L[n1], R[n2];
    
    // 拷贝数据到临时数组
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    
    // 合并临时数组
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    // 拷贝剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
}

特点：

• 时间复杂度：始终O(n log n)

• 空间复杂度：O(n)（需要额外空间）

• 稳定排序

• 适合链表排序和大规模数据

3. 堆排序（Heap Sort）

// 调整堆
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;
    
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;
    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
        heapify(arr, i, 0);
    }
}

特点：

• 时间复杂度：始终O(n log n)

• 空间复杂度：O(1)

• 不稳定排序

• 适合优先级队列实现

四、线性时间排序算法

1. 计数排序（Counting Sort）

void countingSort(int arr[], int n) {
    // 找出数组中的最大值
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    // 创建计数数组并初始化
    int count[max+1];
    for (int i = 0; i <= max; i++) {
        count[i] = 0;
    }
    
    // 统计每个元素出现次数
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    
    // 修改计数数组为累计计数
    for (int i = 1; i <= max; i++) {
        count[i] += count[i-1];
    }
    
    // 创建输出数组
    int output[n];
    
    // 构建输出数组
    for (int i = n-1; i >= 0; i--) {
        output[count[arr[i]]-1] = arr[i];
        count[arr[i]]--;
    }
    
    // 拷贝回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

特点：

• 时间复杂度：O(n+k)（k是数据范围）

• 空间复杂度：O(n+k)

• 稳定排序

• 仅适用于整数且范围不大的情况

2. 基数排序（Radix Sort）

// 获取数字的某一位
int getDigit(int num, int digit) {
    int divisor = 1;
    for (int i = 0; i < digit; i++) {
        divisor *= 10;
    }
    return (num / divisor) % 10;
}

void radixSort(int arr[], int n) {
    // 找出最大值确定位数
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    // 计算最大位数
    int digits = 0;
    while (max > 0) {
        digits++;
        max /= 10;
    }
    
    // 对每一位进行计数排序
    for (int d = 0; d < digits; d++) {
        int count[10] = {0};
        int output[n];
        
        // 统计当前位的数字出现次数
        for (int i = 0; i < n; i++) {
            count[getDigit(arr[i], d)]++;
        }
        
        // 计算累计计数
        for (int i = 1; i < 10; i++) {
            count[i] += count[i-1];
        }
        
        // 构建输出数组（从后向前保持稳定性）
        for (int i = n-1; i >= 0; i--) {
            int digit = getDigit(arr[i], d);
            output[count[digit]-1] = arr[i];
            count[digit]--;
        }
        
        // 拷贝回原数组
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }
}

特点：

• 时间复杂度：O(d*(n+k))（d是位数，k是基数）

• 空间复杂度：O(n+k)

• 稳定排序

• 适用于整数或字符串排序

五、排序算法比较与选择指南

1. 小规模数据（n < 100）：插入排序通常表现最好

2. 中等规模数据（100 < n < 10,000）：快速排序是首选

3. 大规模数据（n > 10,000）：考虑归并排序或堆排序

4. 特定条件（小范围整数）：计数排序或基数排序可能更优