排序算法

作者： /

1. 排序算法概述

排序算法是将一组数据按照特定顺序（通常是升序或降序）重新排列的过程。根据不同的实现方式和效率特性，排序算法可以分为以下几类：

  • 比较排序：通过比较元素来决定它们的相对顺序
  • 非比较排序：不通过比较来决定元素顺序
  • 稳定排序：相等元素的相对顺序在排序前后保持不变
  • 不稳定排序：相等元素的相对顺序可能改变

2. 常见排序算法详解

2.1 冒泡排序 (Bubble Sort)

​​原理​​：重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

​​时间复杂度​​：

  • 最优：O(n)（已经有序的情况）
  • 平均：O(n²)
  • 最差：O(n²)

​​空间复杂度​​：O(1)

​​稳定性​​：稳定

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        bool swapped = false;
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                std::swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        // 如果没有发生交换，说明已经有序
        if (!swapped) break;
    }
}

2.2 选择排序 (Selection Sort)

​​原理​​：每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。

​​时间复杂度​​：O(n²)（所有情况）

​​空间复杂度​​：O(1)

​​稳定性​​：不稳定

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;
            }
        }
        std::swap(arr[i], arr[min_idx]);
    }
}

2.3 插入排序 (Insertion Sort)

​​原理​​：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

​​时间复杂度​​：

  • 最优：O(n)（已经有序的情况）
  • 平均：O(n²)
  • 最差：O(n²)

​​空间复杂度​​：O(1)

​​稳定性​​：稳定

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;
    }
}

2.4 归并排序 (Merge Sort)

​​原理​​：采用分治法，将数组分成两半分别排序，然后将两个有序数组合并成一个有序数组。

​​时间复杂度​​：O(n log n)（所有情况）

​​空间复杂度​​：O(n)

​​稳定性​​：稳定

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);
    }
}

2.5 快速排序 (Quick Sort)

​​原理​​：采用分治法，选择一个基准元素，将数组分为两部分，一部分小于基准，一部分大于基准，然后递归地对两部分进行排序。

​​时间复杂度​​：

  • 最优：O(n log n)
  • 平均：O(n log n)
  • 最差：O(n²)（当数组已经有序或逆序时）

​​空间复杂度​​：O(log n)（递归栈空间）

​​稳定性​​：不稳定

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j <= high-1; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i+1], arr[high]);
    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);
    }
}

2.6 堆排序 (Heap Sort)

​​原理​​：利用堆这种数据结构设计的一种排序算法，将数组构建为大顶堆，然后依次取出堆顶元素。

​​时间复杂度​​：O(n log n)（所有情况）

​​空间复杂度​​：O(1)

​​稳定性​​：不稳定

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) {
        std::swap(arr[i], arr[largest]);
        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--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

3. 非比较排序算法

3.1 计数排序 (Counting Sort)

​​原理​​：统计每个元素出现的次数，然后根据统计信息将元素放回正确位置。

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

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

​​稳定性​​：稳定

void countingSort(int arr[], int n) {
    if (n == 0) return;
    
    // 找到最大值确定计数数组大小
    int max_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }
    
    int count[max_val + 1] = {0};
    
    // 统计每个元素出现次数
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    
    // 修改计数数组为累计计数
    for (int i = 1; i <= max_val; 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];
    }
}

3.2 基数排序 (Radix Sort)

​​原理​​：按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

​​时间复杂度​​：O(nk)（k是最大数字的位数）

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

​​稳定性​​：稳定

// 获取数组中最大数的位数
int getMaxDigits(int arr[], int n) {
    int max_num = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_num) {
            max_num = arr[i];
        }
    }
    
    int digits = 0;
    while (max_num != 0) {
        digits++;
        max_num /= 10;
    }
    return digits;
}

// 使用计数排序对指定位数进行排序
void countingSortForRadix(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};
    
    for (int i = 0; i < n; i++) {
        count[(arr[i]/exp)%10]++;
    }
    
    for (int i = 1; i < 10; i++) {
        count[i] += count[i-1];
    }
    
    for (int i = n-1; i >= 0; i--) {
        output[count[(arr[i]/exp)%10]-1] = arr[i];
        count[(arr[i]/exp)%10]--;
    }
    
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

void radixSort(int arr[], int n) {
    int max_digits = getMaxDigits(arr, n);
    
    for (int exp = 1; max_digits > 0; exp *= 10, max_digits--) {
        countingSortForRadix(arr, n, exp);
    }
}

4. 排序算法比较与选择

算法平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景
冒泡排序O(n²)O(n²)O(1)稳定小规模数据或基本有序数据
选择排序O(n²)O(n²)O(1)不稳定小规模数据
插入排序O(n²)O(n²)O(1)稳定小规模或基本有序数据
归并排序O(n log n)O(n log n)O(n)稳定大规模数据，需要稳定排序
快速排序O(n log n)O(n²)O(log n)不稳定大规模数据，通用排序
堆排序O(n log n)O(n log n)O(1)不稳定大规模数据，空间有限
计数排序O(n + k)O(n + k)O(n + k)稳定整数排序，范围不大
基数排序O(nk)O(nk)O(n + k)稳定整数排序，位数不多

​​选择建议​​：

  1. 小规模数据：插入排序或冒泡排序
  2. 大规模通用数据：快速排序（默认选择）
  3. 需要稳定排序：归并排序
  4. 空间有限：堆排序
  5. 整数排序且范围不大：计数排序或基数排序

5. C++ STL中的排序算法

C++标准库提供了高效的排序实现：

#include &lt;algorithm>
#include &lt;vector>

void stlSortExample() {
    std::vector&lt;int> vec = {5, 2, 9, 1, 5, 6};
    
    // 默认升序排序
    std::sort(vec.begin(), vec.end());
    
    // 降序排序
    std::sort(vec.begin(), vec.end(), std::greater&lt;int>());
    
    // 稳定排序（保持相等元素的相对顺序）
    std::stable_sort(vec.begin(), vec.end());
    
    // 部分排序（前n个元素）
    std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
}

STL的std::sort通常实现为快速排序、堆排序和插入排序的混合（Introsort），在大多数情况下是最优选择。

Introsort（内省排序）

std::sort 的核心算法是 Introsort，这是一种混合排序算法，结合了三种经典算法的优点：

  1. ​​快速排序​​：主排序算法，平均性能最好
  2. ​​堆排序​​：作为快速排序的”安全网”，防止最坏情况
  3. ​​插入排序​​：处理小规模数据

算法选择策略

数据规模使用的算法原因
n ≤ 16-32插入排序小数据量常数因子小
递归深度 < 2log₂n快速排序平均性能最优
递归深度 ≥ 2log₂n堆排序防止O(n²)最坏情况

相关文章

滚动至顶部