冒泡排序

冒泡排序是一种简单直观的算法>排序算法，它通过多次遍历列表，逐步将最大（或最小）的元素“冒泡”到列表的末尾。其名称源于算法的运行方式：较大的元素逐渐向上浮动，就像水中的气泡一样。

工作原理

1. 遍历数组：从数组的第一个元素开始，依次比较相邻的两个元素。
2. 比较并交换：如果前一个元素大于后一个元素，交换它们的位置。这样大的元素会向右移动。
3. 重复步骤：继续进行这样的遍历，直到不需要再交换为止。在每次遍历中，最大的元素会冒泡到数组的末尾。
4. 优化：如果在一次遍历中没有发生任何交换，则说明数组已经是有序的，可以提前终止排序过程。

冒泡排序的步骤举例

假设我们有一个数组 [5, 1, 4, 2, 8]，使用冒泡排序对其排序：

1. 第一次遍历：

   • 比较 5 和 1，交换，数组变成 [1, 5, 4, 2, 8]。
   • 比较 5 和 4，交换，数组变成 [1, 4, 5, 2, 8]。
   • 比较 5 和 2，交换，数组变成 [1, 4, 2, 5, 8]。
   • 比较 5 和 8，不交换。
   • 第一次遍历结束，最大值 8 冒泡到数组末尾。

2. 第二次遍历：

   • 比较 1 和 4，不交换。
   • 比较 4 和 2，交换，数组变成 [1, 2, 4, 5, 8]。
   • 比较 4 和 5，不交换。
   • 第二次遍历结束，次大值 5 已经排好位置。

3. 后续遍历：

   • 剩下的元素会依次比较并排序，最终数组变为 [1, 2, 4, 5, 8]。

冒泡排序的特点

• 时间复杂度：

  • 最坏情况：O(n^2)（数组逆序时，需要最多的比较和交换）。
  • 最好情况：O(n)（数组已经有序时，只需一次遍历）。
  • 平均情况：O(n^2)。

• 空间复杂度：O(1)，因为它是原地排序，不需要额外的存储空间。

• 稳定性：冒泡排序是稳定的，即相等的元素在排序后相对顺序不会改变。

优缺点

• 优点：
  • 实现简单，易于理解。
  • 当数组接近有序时，性能较好，尤其是优化版冒泡排序可以提前终止。
• 缺点：
  • 对于较大规模的数据集，效率不高，时间复杂度为 O(n^2)。

适用场景

冒泡排序通常用于教学目的或小数据集，因为它的实现和理解都比较简单，但在实际应用中，效率低于其他高级算法>排序算法（如快速排序、归并排序等）。

#include <iostream>
#include <vector>
using namespace std;class Sorter {
public:// 冒泡算法>排序算法void bubbleSort(vector<int>& arr) {int n = arr.size();  // 获取数组的长度for (int i = 0; i < n - 1; ++i) {  // 控制遍历次数，总共需要遍历 n-1 轮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;  // 如果没有发生交换，说明数组已经有序，提前结束}}
};int main() {vector<int> arr = {64, 34, 25, 12, 22, 11, 90};  // 初始化一个待排序的数组Sorter sorter;  // 创建 Sorter 类的对象cout << "原数组: ";for (int i : arr) cout << i << " ";  // 输出排序前的数组cout << endl;sorter.bubbleSort(arr);  // 调用冒泡算法>排序算法进行排序cout << "冒泡排序后数组: ";for (int i : arr) cout << i << " ";  // 输出排序后的数组cout << endl;return 0;
}

快速排序

快速排序（QuickSort）是一种基于分治法（divide and conquer）的高效算法>排序算法。它通过不断将数组分成两部分，递归地对两部分分别进行排序，从而达到整体有序的效果。相比于冒泡排序和选择排序，快速排序的平均时间复杂度为 O(n log n)，具有更高的效率。

快速排序的步骤

1. 选取基准元素（Pivot）：

   • 从数组中选择一个元素作为基准（Pivot）。这个基准元素可以是数组的任意元素，常见的选法包括选择数组的第一个元素、最后一个元素、或随机选择一个元素。

2. 划分数组：

   • 遍历数组，将数组中的元素根据与基准的大小进行划分：
     • 所有小于基准的元素放在基准的左边；
     • 所有大于基准的元素放在基准的右边。

3. 递归排序：

   • 对划分后的左右两部分数组，递归地继续执行上述步骤，直到每部分只有一个或零个元素（此时数组已经有序）。

4. 合并结果：

   • 递归结束后，左部分、基准元素和右部分已经各自有序，组合起来即可得到完整的有序数组。

快速排序的原理示例

假设我们有一个数组 [8, 3, 1, 7, 0, 10, 2]，使用快速排序的过程如下：

1. 选择基准：

   • 选择第一个元素 8 作为基准。

2. 划分数组：

   • 遍历数组，将元素划分为两部分：
     • 小于 8 的元素：[3, 1, 7, 0, 2]
     • 大于 8 的元素：[10]
     • 划分结果：[3, 1, 7, 0, 2] 8 [10]

3. 递归排序：

   • 对左边部分 [3, 1, 7, 0, 2] 递归进行快速排序：
     • 选择基准 3，划分为 [1, 0, 2] 和 [7]，递归继续。
   • 对右边部分 [10]，无需再排序。

4. 合并结果：

   • 合并左边已排序的部分、基准 8、右边已排序的部分，最终结果是 [0, 1, 2, 3, 7, 8, 10]。

#include <iostream>
#include <vector>
using namespace std;class QuickSorter {
public:// 快速排序的主函数void quickSort(vector<int>& arr, int low, int high) {if (low < high) {// 获取划分点int pivotIndex = partition(arr, low, high);// 递归地对左右两部分排序quickSort(arr, low, pivotIndex - 1);  // 排序左半部分quickSort(arr, pivotIndex + 1, high); // 排序右半部分}}private:// 划分函数，返回基准的最终位置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;  // 返回基准的最终位置}
};int main() {vector<int> arr = {8, 3, 1, 7, 0, 10, 2};  // 初始化待排序数组QuickSorter sorter;cout << "原数组: ";for (int i : arr) cout << i << " ";cout << endl;sorter.quickSort(arr, 0, arr.size() - 1);  // 调用快速排序cout << "快速排序后数组: ";for (int i : arr) cout << i << " ";cout << endl;return 0;
}

代码细节解释：

1. quickSort()：

   • 这是快速排序的主函数。它通过递归调用，持续地对数组进行划分，并对每一部分分别排序。
   • 参数 low 和 high 指定当前要排序的数组区间。
   • 当 low < high 时，意味着当前区间内有多个元素需要排序，否则直接返回。

2. partition()：

   • 这是快速排序的核心部分，用于将数组划分为两部分。
   • 选择基准：在这里，我们选择数组最后一个元素 arr[high] 作为基准。
   • 双指针法：i 指针用于标记小于基准的部分，j 指针用于遍历数组。
   • 交换：每当找到小于基准的元素时，将其与 i 位置的元素交换，确保小于基准的元素都位于数组的前半部分。
   • 最后，将基准元素 arr[high] 放到正确的位置 i + 1，并返回这个位置。

3. 递归调用：

   • quickSort(arr, low, pivotIndex - 1) 对基准左边的部分进行排序。
   • quickSort(arr, pivotIndex + 1, high) 对基准右边的部分进行排序。

快速排序的复杂度分析

• 时间复杂度：

  • 最好情况：O(n log n)，这是当每次划分都能将数组均匀分割时的情况。
  • 平均情况：O(n log n)，大多数情况下，快速排序的性能接近最好情况。
  • 最坏情况：O(n^2)，这是当数组每次划分极不均匀时的情况，如数组已经有序时。

• 空间复杂度：

  • 快速排序是原地算法>排序算法，空间复杂度为 O(log n)，这是由于递归调用栈的开销。

快速排序的特点

• 快：快速排序的平均时间复杂度为 O(n log n)，因此它在大多数情况下比冒泡排序、选择排序、插入排序等效率高得多。
• 不稳定：快速排序不是稳定的算法>排序算法，因为相同的元素在排序后可能改变相对位置。
• 分治法：它通过递归不断划分问题，使得复杂问题转化为较小的问题。

适用场景

快速排序适用于大规模数据集，尤其是当对随机数据进行排序时，它的效率非常高。然而，对于小数据集或几乎有序的数据集，插入排序等可能更为高效。

归并排序

归并排序（Merge Sort）也是一种基于分治法（Divide and Conquer）的高效算法>排序算法。它通过将数组逐步划分成更小的子数组，然后将这些子数组排序并合并，最终得到有序的数组。归并排序的时间复杂度为 O(n log n)，且是一种稳定排序，即相等的元素在排序后保持相对顺序不变。

归并排序的步骤

1. 分割数组：

   • 将数组从中间一分为二，递归地将每个子数组再一分为二，直到每个子数组中只有一个元素（因为单个元素自然是有序的）。

2. 合并数组：

   • 递归到最小子数组后，开始合并。从每个子数组中选择最小的元素，合并成有序的数组，逐步返回到上一层，最终将整个数组合并成一个有序的数组。

归并排序的示例

假设我们要对数组 [38, 27, 43, 3, 9, 82, 10] 进行排序，归并排序的过程如下：

1. 分割数组：

   • 首先将数组分为两半：[38, 27, 43] 和 [3, 9, 82, 10]。
   • 继续将每一半再分为两部分，直到每个部分只包含一个元素：
     • [38, 27, 43] 分为 [38] 和 [27, 43]，再分为 [27] 和 [43]。
     • [3, 9, 82, 10] 分为 [3, 9] 和 [82, 10]，再分为 [3] 和 [9]，以及 [82] 和 [10]。

2. 合并排序：

   • 从最小的子数组开始合并：
     • [27] 和 [43] 合并为 [27, 43]。
     • [38] 和 [27, 43] 合并为 [27, 38, 43]。
     • [3] 和 [9] 合并为 [3, 9]，[82] 和 [10] 合并为 [10, 82]。
     • [3, 9] 和 [10, 82] 合并为 [3, 9, 10, 82]。
   • 最后，将两部分 [27, 38, 43] 和 [3, 9, 10, 82] 合并为最终的有序数组 [3, 9, 10, 27, 38, 43, 82]。

#include <iostream>
#include <vector>
using namespace std;class MergeSorter {
public:// 归并排序的主函数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);}}private:// 合并函数，用于合并两个有序的子数组void merge(vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1;  // 左半部分的长度int n2 = right - mid;     // 右半部分的长度// 创建临时数组用于存放两个子数组vector<int> L(n1), R(n2);// 复制数据到临时数组 L 和 Rfor (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++;}}
};int main() {vector<int> arr = {38, 27, 43, 3, 9, 82, 10};  // 初始化待排序数组MergeSorter sorter;cout << "原数组: ";for (int i : arr) cout << i << " ";cout << endl;sorter.mergeSort(arr, 0, arr.size() - 1);  // 调用归并排序cout << "归并排序后数组: ";for (int i : arr) cout << i << " ";cout << endl;return 0;
}

代码细节解释：

1. mergeSort()：

   • 这是归并排序的主函数。它通过递归将数组划分为两个部分，然后递归地对每个部分进行排序。
   • 参数 left 和 right 指定当前需要排序的数组区间。
   • 当 left < right 时，继续递归分割数组；当 left == right 时，数组中只有一个元素，不需要再分割。

2. merge()：

   • 这是归并排序的核心部分，用于合并两个有序的子数组。
   • 临时数组：我们使用两个临时数组 L 和 R 分别存储待合并的左右两部分数据。
   • 归并操作：使用两个指针 i 和 j 分别遍历左半部分 L 和右半部分 R，将较小的元素复制回原数组 arr。
   • 处理剩余元素：当其中一个数组的所有元素都已经合并到 arr 中时，剩余的部分直接复制到 arr。

3. 递归调用：

   • mergeSort(arr, left, mid) 对数组的左半部分进行排序。
   • mergeSort(arr, mid + 1, right) 对数组的右半部分进行排序。
   • 最后，使用 merge() 将已经排序的左右两部分合并。

归并排序的复杂度分析

• 时间复杂度：
  • 归并排序的时间复杂度为 O(n log n)，其中 n 是数组长度，log n 是由于递归将数组分成两半的次数，n 是每次合并时的比较和复制操作。
• 空间复杂度：
  • 归并排序需要 O(n) 的辅助空间，因为在合并时需要创建临时数组来存储左右两部分数据。

归并排序的特点

• 稳定性：归并排序是稳定的算法>排序算法，即相等的元素在排序后依然保持它们的相对顺序。
• 适用于大规模数据：由于其时间复杂度为 O(n log n)，归并排序适用于大规模数据的排序任务。
• 额外空间：归并排序需要额外的存储空间来进行合并操作，相比快速排序，空间开销较大，因此在空间敏感的场景中可能不如快速排序合适。

归并排序的应用场景

• 需要稳定排序的场景：如果在排序过程中需要保持相等元素的相对顺序，归并排序是不错的选择。
• 链表排序：归并排序由于不需要随机访问数据，因此在链表等数据结构上表现非常好，不需要额外的空间来合并节点。
• 大数据集：适合用于大规模数据集的排序。