C++ 基础知识 十一 排序算法
一、 介绍
1. 什么是排序算法
在计算机科学中，排序算法（Sorting Algorithm）是一种将一组数据按照指定顺序进行排列的算法。
通常情况下，这种指定的顺序是由一个排序关键字所决定的，例如，按照学生的考试成绩排序，或者按照工资大小排序等。
2. 排序算法的分类
排序算法可以按照算法的思想或实现方式进行分类，常见的分类方法包括以下几种：
-
比较排序：通过比较元素的大小关系来进行排序。常见的比较排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。
-
非比较排序：不依赖于元素之间的比较关系，而是根据元素的特殊性质来进行排序。常见的非比较排序算法有计数排序、基数排序、桶排序等。
-
内排序：所有排序操作都在待排序序列中进行，适用于数据量较小的场景。常见的内排序算法有冒泡排序、选择排序、插入排序、快速排序、归并排序等。
-
外排序：由于内存限制等原因，所有排序操作不能在待排序序列中完成，需要通过对外存进行读写，适用于数据量较大的场景。常见的外排序算法有归并排序、多路归并排序等。
-
稳定排序：在排序操作中，如果存在两个相等的元素，排序后它们的相对位置不发生改变，称为稳定排序。常见的稳定排序算法有插入排序、归并排序等。
-
不稳定排序：在排序操作中，如果存在两个相等的元素，排序后它们的相对位置可能发生改变，称为不稳定排序。常见的不稳定排序算法有选择排序、快速排序等。
二、 常见的排序算法
排序算法详解
1. 冒泡排序
1.1 算法思想
【算法描述】每次比较相邻的两个元素，如果顺序不对则交换，这样每一轮冒泡至少可以确定一个元素的位置。
1.2 代码实现
void bubbleSort(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums[j], nums[j + 1]);
}
}
}
}
1.3 时间复杂度及空间复杂度分析
【时间复杂度】最好情况下时间复杂度为 O(n)，最坏和平均时间复杂度均为 O(n^2)。
【空间复杂度】冒泡排序为原地排序，空间复杂度为 O(1)。
1.4 稳定性分析
冒泡排序是一种稳定的排序算法，因为在交换顺序时，如果相邻元素相等也会进行交换，所以相等元素的顺序不变。
2. 快速排序
2.1 算法思想
【算法描述】以一个基准数为轴，将序列分为两部分，左边比基准数小，右边比基准数大，再对左右两部分进行递归排序。
2.2 代码实现
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[left];
int i = left + 1;
int j = right;
while (i <= j) {
if (nums[i] <= pivot) {
i++;
} else if (nums[j] > pivot) {
j--;
} else {
swap(nums[i], nums[j]);
}
}
swap(nums[left], nums[j]);
return j;
}
void quickSort(vector<int>& nums, int left, int right) {
if (left < right) {
int pivotPos = partition(nums, left, right);
quickSort(nums, left, pivotPos - 1);
quickSort(nums, pivotPos + 1, right);
}
}
2.3 时间复杂度及空间复杂度分析
【时间复杂度】最好情况下时间复杂度为 O(n log n)，最坏情况下时间复杂度为 O(n^2)，平均时间复杂度为 O(n log n)。
【空间复杂度】快速排序为原地排序，空间复杂度为 O(1)。
2.4 稳定性分析
快速排序是一种不稳定的排序算法，因为在交换顺序时，相同元素的顺序可能会发生改变。
3. 插入排序
3.1 算法思想
【算法描述】将一个待排序的序列分成两部分，未排序部分和已排序部分。每次将未排序的元素取出，在已排序中从后往前找到合适的位置插入。
3.2 代码实现
void insertionSort(vector<int>& nums) {
int n = nums.size();
for (int i = 1; i < n; i++) {
int j = i - 1;
int temp = nums[i];
while (j >= 0 && nums[j] > temp) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = temp;
}
}
3.3 时间复杂度及空间复杂度分析
【时间复杂度】最好情况下时间复杂度为 O(n)，最坏和平均时间复杂度均为 O(n^2)。
【空间复杂度】插入排序为原地排序，空间复杂度为 O(1)。
3.4 稳定性分析
插入排序是一种稳定的排序算法，因为在交换顺序时，如果相邻元素相等也不会进行交换，所以相等元素的顺序不变。
4. 选择排序
4.1 算法思想
【算法描述】每次从待排序序列中选择最小（或最大）的元素放在已排序序列的末尾。
4.2 代码实现
void selectionSort(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
swap(nums[i], nums[minIndex]);
}
}
4.3 时间复杂度及空间复杂度分析
【时间复杂度】最好、最坏和平均时间复杂度均为 O(n^2)。
【空间复杂度】选择排序为原地排序，空间复杂度为 O(1)。
4.4 稳定性分析
选择排序是一种不稳定的排序算法，因为在选取最小元素时，相同元素的顺序可能会发生改变。
5. 归并排序
5.1 算法思想
【算法描述】归并排序是一种分治思想的排序算法。将待排序数组不断地二分，直到每个子数组中只剩下一个元素。然后，将这些子数组两两合并，直到最后只剩下一个有序的数组。
5.2 代码实现
void merge(vector<int>& nums, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
vector<int> L(n1);
vector<int> R(n2);
for (int i = 0; i < n1; i++) {
L[i] = nums[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = nums[mid + 1 + j];
}
int i = 0;
int j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
nums[k] = L[i];
i++;
} else {
nums[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
nums[k] = L[i];
i++;
k++;
}
while (j < n2) {
nums[k] = R[j];
j++;
k++;
}
}
void mergeSort(vector<int>& nums, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
}
5.3 时间复杂度及空间复杂度分析
【时间复杂度】最好、最坏和平均时间复杂度均为 O(n log n)。
【空间复杂度】归并排序空间复杂度主要由递归过程中需要开辟的系统栈空间决定，空间复杂度为 O(n)。
5.4 稳定性分析
归并排序是一种稳定的排序算法，因为在归并的过程中，当两个元素相等时，我们先将左边的元素插入到结果数组中，从而保证相等元素的顺序不变。
6. 堆排序
6.1 算法思想
【算法描述】利用堆的性质进行排序的方法。将待排序的序列构造成一个大根堆。然后，依次取出堆顶元素（即当前最大元素）将其置于对应位置，再调整堆结构，使其满足堆的性质。
6.2 代码实现
void heapify(vector<int>& nums, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && nums[left] > nums[largest]) {
largest = left;
}
if (right < n && nums[right] > nums[largest]) {
largest = right;
}
if (largest != i) {
swap(nums[i], nums[largest]);
heapify(nums, n, largest);
}
}
void heapSort(vector<int>& nums) {
int n = nums.size();
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(nums, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(nums[0], nums[i]);
heapify(nums, i, 0);
}
}
6.3 时间复杂度及空间复杂度分析
【时间复杂度】最好、最坏和平均时间复杂度均为 O(n log n)。
【空间复杂度】堆排序为原地排序，空间复杂度为 O(1)。
6.4 稳定性分析
堆排序是一种不稳定的排序算法，因为在进行交换时，相同元素的顺序可能会发生改变。
7. 希尔排序
7.1 算法思想
【算法描述】首先将待排序序列分组，对每个子序列进行插入排序，然后逐渐减少子序列的间距，进行插入排序，直到完成排序。
7.2 代码实现
void shellSort(vector<int>& nums) {
int n = nums.size();
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = nums[i];
int j = i - gap;
while (j >= 0 && nums[j] > temp) {
nums[j + gap] = nums[j];
j -= gap;
}
nums[j + gap] = temp;
}
}
}
7.3 时间复杂度及空间复杂度分析
【时间复杂度】最坏时间复杂度为 O(n^2)，平均时间复杂度为 O(n log n)。
【空间复杂度】希尔排序为原地排序，空间复杂度为 O(1)。
7.4 稳定性分析
希尔排序是一种不稳定的排序算法，因为在进行插入排序时，相同元素的顺序可能会发生改变。
8. 计数排序
8.1 算法思想
【算法描述】将要排序的数据分成几个桶来存储，每个桶内的数据所代表的值相同，桶内数据不做排序处理。最终结果就是所有桶的数据依次排列组合。
8.2 代码实现
void countingSort(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return;
}
int maxVal = *max_element(nums.begin(), nums.end());
vector<int> count(maxVal + 1);
for (int i = 0; i < n; i++) {
count[nums[i]]++;
}
for (int i = 1; i < maxVal + 1; i++) {
count[i] += count[i - 1];
}
vector<int> res(n);
for (int i= n - 1; i >= 0; i--) {
int index = count[nums[i]] - 1;
res[index] = nums[i];
count[nums[i]]--;
}
nums = res;
}
8.3 时间复杂度及空间复杂度分析
【时间复杂度】最好、最坏和平均时间复杂度均为 O(n + k)，其中 k 为数据范围。
【空间复杂度】计数排序需要记录每个元素出现的次数，所以空间复杂度为 O(k)。
8.4 稳定性分析
计数排序是一种稳定的排序算法，因为在进行排序时，相同元素的顺序不会发生改变。
如果你有其他关于排序算法的问题，欢迎在评论区留言，我会尽快回复并为您解答。
三、 应用场景
1. 不同场景下的排序算法选择
在实际开发中，我们需要选择最符合业务场景需求的排序算法。以下是各种排序算法的应用场景及其复杂度。
1.1 冒泡排序
冒泡排序适用于数据规模较小的情况。
【时间复杂度】
- 最优时间复杂度：O(n)
- 最坏时间复杂度：O(n^2)
- 平均时间复杂度：O(n^2)
【适用场景】
- 数据规模较小。
1.2 选择排序
选择排序适用于数据规模较小的情况。
【时间复杂度】
- 最优时间复杂度：O(n^2)
- 最坏时间复杂度：O(n^2)
- 平均时间复杂度：O(n^2)
【适用场景】
- 数据规模较小。
1.3 插入排序
插入排序适用于数据基本有序的情况。
【时间复杂度】
- 最优时间复杂度：O(n)
- 最坏时间复杂度：O(n^2)
- 平均时间复杂度：O(n^2)
【适用场景】
- 数据基本有序。
1.4 快速排序
快速排序适用于数据规模较大的情况。
【时间复杂度】
- 最优时间复杂度：O(nlogn)
- 最坏时间复杂度：O(n^2)
- 平均时间复杂度：O(nlogn)
【适用场景】
- 数据规模较大。
1.5 归并排序
归并排序适用于数据规模较大的情况。
【时间复杂度】
- 最优时间复杂度：O(nlogn)
- 最坏时间复杂度：O(nlogn)
- 平均时间复杂度：O(nlogn)
【适用场景】
- 数据规模较大。
1.6 堆排序
堆排序适用于数据规模较大的情况。
【时间复杂度】
- 最优时间复杂度：O(nlogn)
- 最坏时间复杂度：O(nlogn)
- 平均时间复杂度：O(nlogn)
【适用场景】
- 数据规模较大。
1.7 计数排序
计数排序适用于数据范围不大的情况。
【时间复杂度】
- 最优时间复杂度：O(n + k)
- 最坏时间复杂度：O(n + k)
- 平均时间复杂度：O(n + k)
【适用场景】
- 数据范围不大。
1.8 桶排序
桶排序适用于数据范围不大但数据分布不均匀的情况。
【时间复杂度】
- 最优时间复杂度：O(n)
- 最坏时间复杂度：O(n^2)
- 平均时间复杂度：O(n)
【适用场景】
- 数据范围不大但数据分布不均匀。
1.9 基数排序
基数排序适用于数据范围不大且位数不多的整数排序。
【时间复杂度】
- 最优时间复杂度：O(n * k)
- 最坏时间复杂度：O(n * k)
- 平均时间复杂度：O(n * k)
【适用场景】
- 数据范围不大且位数不多的整数排序。
2. 实际应用案例
在实际开发中，排序算法经常用于以下场景：
2.1 数据库查询排序
在数据库查询时，我们通过排序算法对查询结果进行排序，使得查询结果更加有序、易读。
2.2 购物网站商品排序
在购物网站中，我们经常需要对商品进行排序，以便让用户更快找到自己需要的商品。
2.3 游戏中的排行榜
在游戏中，我们可以通过排行榜对用户进行排名，以增加游戏可玩性。
总之，排序算法是一项非常重要的算法，在实际开发中会经常使用到。根据不同的场景需求，选择最适合的排序算法将会大大提高程序的效率和用户的体验。
四、排序常见问题及优化方案
在程序开发中，排序算法是一个非常重要的部分。然而，当数据量过大时，常规排序算法可能会因为时间复杂度而导致程序崩溃或运行效率极低。本篇文章将为你讲解针对大数据排序问题的优化方案以及排序算法优化的方法。
1. 大数据排序问题
当数据规模过大时，普通的排序算法存在时间、空间上的挑战。因此，针对于大数据数量的排序问题，我们需要进行优化。以下是几种优化方案：
1.1 外排序
- 概念：外部排序即数据量太大无法一次性全部载入内存中进行排序，必须借助外部存储器磁盘等设备进行存储与读取，再使用内部排序方法进行排序的方法。
- 思路：将大量的数据分割成若干份，每份数据先进行内部排序，再进行归并排序。
1.2 分布式排序
- 概念：将大规模数据集合分解为多个子数据集，这些子数据集可以在高速网络上交换数据、并行处理，最终将子数据集归并成有序的数据集的一种排序方式。
- 思路：将大量的数据分割成若干份，使用分布式集群计算框架将每份数据运算并排序，最后合并成单份数据。
2. 排序算法优化
在实际开发中，除了针对大量数据排序问题的优化，我们还需要对排序算法进行性能优化。以下是优化方法：
2.1 算法优化
- 优化循环次数
- 减少内存操作
- 减少函数调用
- 避免结构体赋值
2.2 多线程优化
当排序的数据量较大时，可以通过多线程并发执行，提高程序的效率。
2.3 CPU指令优化
利用CPU的SIMD指令并行执行多个操作可极大提高程序执行效率。
3. 选择合适的排序算法
除了对排序算法进行优化，选择合适的排序算法也是提高程序执行效率的一种方法。以下是各种排序算法的时间复杂度，不同的场景需要选择不同的排序算法：
- 冒泡排序 时间复杂度 O(n^2)
- 选择排序 时间复杂度 O(n^2)
- 插入排序 时间复杂度 O(n^2)
- 希尔排序 时间复杂度 O(nlogn)
- 归并排序 时间复杂度 O(nlogn)
- 快速排序 时间复杂度 O(nlogn)
- 堆排序 时间复杂度 O(nlogn)
- 计数排序 时间复杂度 O(n + k)
- 桶排序 时间复杂度 O(n)
- 基数排序 时间复杂度 O(n * k)
示例代码
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// 比较函数
bool cmp(int a, int b) {
return a < b;
}
int main() {
// 定义数据
vector<int> vec = {5, 4, 3, 2, 1};
// 使用sort排序，使用cmp作为比较函数
sort(vec.begin(), vec.end(), cmp);
// 输出排序后的结果
for (auto v : vec) {
cout << v << " ";
}
cout << endl;
return 0;
}
以上是C++排序常见问题及优化方案的介绍，希望对你有所帮助。
五、 排序总结
在计算机科学中，排序算法是非常重要的基础算法。不同的排序算法在不同的场景下起到不同的作用。本篇文章将总结c++排序算法的优缺点及未来发展趋势。
排序算法的优缺点
1. 冒泡排序
冒泡排序是一种简单的排序算法，它的时间复杂度最坏情况下可以达到 O(n²), 不适合排序大规模数据。但是其优点是实现简单、容易理解。
2. 快速排序
快速排序是一种基于分治思想的排序算法，不稳定的排序算法，其平均时间复杂度为 O(nlogn)。但是在最坏情况下会退化为O(n²)，需要优化。它在实际使用中效率很高，是最常用的排序算法之一。
3. 插入排序
插入排序适用于大部分已排序或接近已排序的数据，其平均时间复杂度为 O(n²)。但它往往比基于比较的排序算法更为高效，因为其内部操作更为简单。
4. 希尔排序
希尔排序是一种跨度序列的插入排序，时间复杂度为 O(nlogn) ~ O(n²)。相对于简单的插入排序，希尔排序的比较次数和移动次数都有减少的趋势，但仍然比不上快速排序。
5. 归并排序
归并排序是一种稳定的排序算法，其时间复杂度为 O(nlogn)。但因为需要开辟额外的空间存储中间结果，因此空间复杂度较高。
未来发展趋势
目前，对于大规模数据的排序，已经有了并行化的思路。并行排序算法具有良好的可扩展性和灵活性，能够在分布式计算系统上进行高性能的排序操作。例如，MapReduce平台提供了了一种高效的并行排序算法，在对大规模数据进行排序时，可以通过将数据划分为多个部分，在各个节点进行局部排序，最终通过全排序合并各节点的排序结果，达到高效地排序大规模数据的目的。
此外，随着人工智能的发展，对于排序算法的实时性和精确性也提出了更高的要求。现代的机器学习算法和深度学习算法，往往需要对海量的数据进行快速排序和过滤。基于此，一些新型排序算法被提出，例如，k-means算法、局部敏感哈希算法、分布式快速排序算法等等。这些新型算法将能够更好地满足人工智能领域的需求。