冒泡排序（Bubble Sort）是一种简单直观的排序算法，其基本思想是通过多次遍历待排序的序列，比较相邻元素并交换它们的位置，使较大的元素逐渐“冒泡”到序列的末尾。尽管效率较低，但它是介绍排序算法时常用的例子之一，适合对小规模数据的排序。

冒泡排序的原理

  1. 从序列的第一个元素开始，依次比较相邻的两个元素。如果前面的元素大于后面的元素，就交换它们的位置。
  2. 每次遍历后，最大的元素会被交换到当前未排序部分的末尾。
  3. 对未排序部分重复上述过程，直到没有元素需要交换为止。

冒泡排序的特点

  • 时间复杂度：
    • 最坏情况： $O(n^2)$（数组逆序）
    • 最好情况： $O(n)$（数组已经有序，只需一次遍历）
    • 平均情况： $O(n^2)$
  • 空间复杂度： $O(1)$（只需常数级的额外空间）
  • 稳定性：起泡排序是稳定的排序算法，即相同的元素在排序后不会改变相对顺序。

冒泡排序的实现

C++ 实现

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
37
38
39
40
41
42
43
#include <iostream>
using namespace std;

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]) {
                // 交换相邻元素
                swap(arr[j], arr[j + 1]);
                swapped = true;  // 记录交换发生
            }
        }
        
        // 如果本轮没有发生交换，数组已排序，提前退出
        if (!swapped) {
            break;
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

    cout << "排序后的数组: ";
    printArray(arr, n);

    return 0;
}

快速排序（Quick Sort）是一种高效的基于分治法的排序算法，它通过递归地将数组分成两个子数组来排序。快速排序通常是实际应用中最快的排序算法之一，适用于大规模数据排序。

快速排序的原理

  1. 选取基准（pivot）：从数组中选择一个元素作为基准，可以是第一个元素、最后一个元素、中间元素或随机选择。
  2. 分区（Partition）：将数组分成两部分，使得左侧子数组的所有元素都小于基准，而右侧子数组的所有元素都大于或等于基准。
  3. 递归排序：对左右两个子数组分别递归地应用快速排序。
  4. 合并：由于在分区的过程中数组已经部分有序，所以不需要额外的合并操作。

快速排序的特点

  • 时间复杂度：
    • 最坏情况： $O(n^2)$（当数组基本有序或基准选择不当时）
    • 最好情况： $O(n \log n)$（理想情况下，基准能将数组均匀分割）
    • 平均情况： $O(n \log n)$
  • 空间复杂度： $O(\log n)$，用于递归栈空间。
  • 不稳定性：快速排序是不稳定的排序算法，即相同的元素在排序后可能会改变相对顺序。

快速排序的实现

下面是快速排序的经典实现，其中基准选取最后一个元素。

C++ 实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
using namespace std;

// 分区函数，将基准放到正确位置，并返回基准的最终位置索引
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++;  // 增加边界索引
            swap(arr[i], arr[j]);  // 交换当前元素与边界元素
        }
    }
    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);
    }
}

// 辅助函数：打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    cout << "排序后的数组: ";
    printArray(arr, n);

    return 0;
}

快速排序的优化

  1. 三数取中：选择基准时，可以取头、中、尾三个元素的中间值，避免数组本身有序时出现最坏情况。
  2. 随机选择基准：通过随机选择基准位置，打乱输入数组，减少最坏情况发生的概率。
  3. 小数组插入排序：当子数组长度较小时（如10以下），可以使用插入排序代替快速排序，以提高效率。

快速排序的性能分析

$$
快速排序的性能在很大程度上取决于分区是否平衡。
$$

$$
平衡的分区能保证时间复杂度接近 O(n \log n)，而极端不平衡的分区会导致最坏的 O(n^2)复杂度。因此，优化基准的选择非常重要。
$$

简单选择排序（Selection Sort）是一种排序算法，通过反复找到未排序部分中的最小元素，将其放到数组的起始位置，逐步构建有序序列。这个算法适合数据量较小的情况，时间复杂度为 $O(n^2)$。

算法步骤

  1. 从数组的第一个元素开始，假设它是最小元素。
  2. 遍历数组的剩余部分，找到比当前最小元素更小的值并更新最小元素。
  3. 遍历完成后，将找到的最小值和当前未排序部分的第一个元素交换。
  4. 移动到下一个位置，重复上述步骤，直到整个数组排序完毕。

实现代码（C++）

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
37
38
39
#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    // 逐一确定数组中每一个位置的最终元素
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i; // 假设当前索引 i 是最小元素的位置
        // 查找从 i+1 到 n-1 中比 arr[minIndex] 更小的元素
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) { // 更新最小元素的位置
                minIndex = j;
            }
        }
        // 交换最小元素到当前的 i 位置
        if (minIndex != i) { // 避免自身交换
            swap(arr[i], arr[minIndex]);
        }
    }
}

// 打印数组函数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n); // 对数组进行选择排序

    cout << "排序后的数组: ";
    printArray(arr, n); // 输出排序结果

    return 0;
}

堆排序（Heap Sort）是一种基于二叉堆的数据结构实现的排序算法，具有时间复杂度为 $O(n \log n)$，可以被认为是一种改进的选择排序。堆排序的特点是无论数据情况如何，其时间复杂度都能保持稳定，是一种不稳定的原地排序算法。

二叉堆简介

堆排序使用最大堆或最小堆来辅助排序：

  • 最大堆：父节点的值总是大于或等于子节点的值。
  • 最小堆：父节点的值总是小于或等于子节点的值。

在堆排序中，通常使用最大堆来实现升序排序。

堆排序算法步骤

  1. 构建最大堆：将数组视为一个完全二叉树，从最后一个非叶子节点开始，对每个节点进行堆调整，使整个数组满足最大堆的性质。
  2. 排序：
    • 将堆顶元素（最大值）与数组末尾元素交换，这样最大值就处于正确的最终位置。
    • 将堆的大小减一，对新的堆顶元素进行堆调整，以重新保持最大堆的性质。
    • 重复上述过程，直到堆的大小减为 1，排序完成。

堆排序代码实现（C++）

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
using namespace std;

// 将以 root 为根的子树调整为最大堆
void heapify(int arr[], int n, int root) {
    int largest = root;         // 将根节点设为最大值
    int left = 2 * root + 1;    // 左子节点
    int right = 2 * root + 2;   // 右子节点

    // 如果左子节点存在且大于根节点
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点存在且大于当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点，则交换并递归调整
    if (largest != root) {
        swap(arr[root], arr[largest]);
        heapify(arr, n, largest);  // 递归调整受影响的子树
    }
}

// 堆排序主函数
void heapSort(int arr[], int n) {
    // 1. 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 2. 逐一取出元素并调整堆
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);    // 将最大元素移动到末尾
        heapify(arr, i, 0);      // 调整剩下的元素形成最大堆
    }
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// 主函数
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "排序后的数组: ";
    printArray(arr, n);

    return 0;
}

示例执行过程

假设我们对数组 {12, 11, 13, 5, 6, 7} 进行堆排序：

  1. 构建最大堆：

    • 选择非叶子节点 5 和 6，调整以 5 和 6 为根的子树。
    • 继续调整上层节点，最后整个数组满足最大堆的结构：{13, 11, 12, 5, 6, 7}。

  2. 排序过程：

    • 将堆顶元素 13 与最后一个元素交换：{7, 11, 12, 5, 6, 13}，缩小堆的范围到 [0, n-2]，再对堆顶进行堆调整。
    • 重复此过程直到排序完成，最终结果为：{5, 6, 7, 11, 12, 13}。

时间复杂度

堆排序的时间复杂度为 $O(n \log n)$，因为：

  • 建堆操作的时间复杂度为 $O(n)$。
  • 排序过程中需要 $O(\log n)$ 的时间进行堆调整，总体复杂度为 $O(n \log n)$。

归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）的排序算法。它将数组分成较小的子数组，分别排序后再合并，最终完成排序。

1. 算法原理

归并排序的核心思想是：

  1. 分：将待排序数组分成两个子数组，分别对这两个子数组进行排序。
  2. 治：通过递归将子数组继续分割，直到每个子数组的长度为 1。
  3. 合：将两个有序子数组合并成一个有序数组。

2. 算法步骤

  1. 递归分割数组：
    • 将数组从中间分成两部分，直到每部分只剩一个元素。
  2. 合并子数组：
    • 合并两个已排序的子数组为一个有序数组。

3. 时间复杂度

  • 时间复杂度：$O(n \log n)$
    • 每次分割数组的时间复杂度为 $O(\log n)$，合并数组的时间复杂度为 $O(n)$。
  • 空间复杂度：$O(n)$
    • 归并排序需要额外的数组空间来存储合并后的结果。

4. C++ 实现

以下是归并排序的完整代码：

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
using namespace std;

// 合并两个有序数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1; // 左子数组大小
    int n2 = right - mid;    // 右子数组大小

    // 创建临时数组
    int L[n1], R[n2];

    // 拷贝数据到临时数组
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int i = 0; i < n2; i++)
        R[i] = arr[mid + 1 + i];

    // 合并两个有序数组
    int i = 0, j = 0, k = left; // 初始索引
    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 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 printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// 主函数
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "原始数组: ";
    printArray(arr, n);

    mergeSort(arr, 0, n - 1);

    cout << "排序后的数组: ";
    printArray(arr, n);

    return 0;
}

输出结果

1
2
原始数组: 12 11 13 5 6 7 
排序后的数组: 5 6 7 11 12 13

代码说明

  1. merge 函数：

    • 将两个有序数组（L 和 R）合并为一个有序数组。
    • 使用两个指针遍历子数组，同时更新原数组中的值。

  2. mergeSort 函数：

    • 递归分割数组为两部分，直到每部分只剩一个元素。
    • 调用 merge 函数将子数组合并。

  3. 递归基线条件：

    • 当 left >= right 时，数组无法再分割，递归结束。

优缺点

优点

  1. 稳定性：归并排序是一种稳定的排序算法。
  2. 性能稳定：时间复杂度始终为 $O(n \log n)$，无论最佳、最差或平均情况。

缺点

  1. 空间复杂度较高：需要额外的数组空间来辅助合并操作。
  2. 递归开销：递归调用会增加时间和空间的开销。

应用场景

归并排序适用于需要稳定排序的场景，特别是在处理大规模数据集或链表时（链表中归并排序的空间复杂度为 $O(1)$）。