排序算法详解

排序算法是计算机科学中最基础也是最重要的算法之一。本文将详细介绍几种常见的排序算法，包括它们的实现原理、时间复杂度和适用场景。本文所有代码示例使用 C++ 实现，需要包含以下头文件：

1
2
3
#include <vector>
#include <algorithm>
using namespace std;

1. 冒泡排序 (Bubble Sort)

冒泡排序是最简单的排序算法之一，它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

实现原理

  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：稳定

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool swapped;
    for(int i = 0; i < n-1; i++) {
        swapped = false;
        // 每一轮比较
        for(int j = 0; j < n-i-1; j++) {
            // 相邻元素比较并交换
            if(arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        // 如果没有发生交换，说明数组已经有序
        if(!swapped) break;
    }
}

2. 选择排序 (Selection Sort)

选择排序的工作原理是每次从待排序的数据中选出最小（或最大）的元素，存放在序列的起始位置。

实现原理

  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：不稳定

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selectionSort(vector<int>& arr) {
    int n = arr.size();
    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;
            }
        }
        // 将找到的最小值放到已排序序列的末尾
        if(min_idx != i) {
            swap(arr[i], arr[min_idx]);
        }
    }
}

3. 插入排序 (Insertion Sort)

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

实现原理

  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 稳定性：稳定

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for(int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // 将大于key的元素都向后移动
        while(j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

4. 快速排序 (Quick Sort)

快速排序是一种分治算法，它通过选择一个”基准”元素，将数组分成两个子数组，小于基准的元素放在左边，大于基准的元素放在右边。

实现原理

  • 时间复杂度：平均 O(nlogn)，最坏 O(n²)
  • 空间复杂度：O(logn)
  • 稳定性：不稳定

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int partition(vector<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++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<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);
    }
}

// 封装函数，方便调用
void quickSort(vector<int>& arr) {
    quickSort(arr, 0, arr.size() - 1);
}

5. 归并排序 (Merge Sort)

归并排序是一种分治算法，它将数组分成两半，递归地排序两半，然后将它们合并起来。

实现原理

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(n)
  • 稳定性：稳定

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    
    // 合并两个有序数组
    while(i <= mid && j <= right) {
        if(arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    // 复制剩余元素
    while(i <= mid) temp[k++] = arr[i++];
    while(j <= right) temp[k++] = arr[j++];
    
    // 将临时数组复制回原数组
    for(i = 0; i < k; i++) {
        arr[left + i] = temp[i];
    }
}

void mergeSort(vector<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);
    }
}

// 封装函数，方便调用
void mergeSort(vector<int>& arr) {
    mergeSort(arr, 0, arr.size() - 1);
}

6. 堆排序 (Heap Sort)

堆排序是利用堆这种数据结构所设计的一种排序算法。它通过构建最大堆或最小堆来进行排序。

实现原理

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

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void heapify(vector<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) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
    
    // 构建最大堆
    for(int i = n/2-1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // 一个个从堆顶取出元素
    for(int i = n-1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

排序算法的比较

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

如何选择排序算法？

  1. 数据量小（n < 50）：插入排序
  2. 数据量大：
    • 要求稳定：归并排序
    • 不要求稳定：快速排序
  3. 内存空间有限：堆排序
  4. 数据基本有序：插入排序
  5. 数据量特别大且有重复：计数排序/基数排序

总结

每种排序算法都有其特点和适用场景。在实际应用中，我们需要根据具体情况（数据规模、稳定性要求、空间限制等）来选择合适的排序算法。大多数编程语言的标准库中的排序实现都是一种改进的快速排序，它能够很好地适应各种情况。