C++ 实现所有排序算法
2024-11-013.2k 阅读
排序算法概述
排序算法是计算机科学中最基本且重要的算法之一，其目的是将一组数据按照特定的顺序（如升序或降序）进行排列。在实际应用中，排序算法广泛用于数据处理、搜索算法优化、数据分析等众多领域。不同的排序算法在时间复杂度、空间复杂度、稳定性等方面存在差异，了解并掌握这些算法，能帮助开发者根据具体的应用场景选择最合适的排序方法。
冒泡排序（Bubble Sort）
原理
冒泡排序是一种简单的比较排序算法。它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序排列）。
代码实现
#include <iostream>
#include <vector>
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < n - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
复杂度分析
- 时间复杂度：在最坏情况下，即初始序列是逆序的，需要进行(n(n - 1)/2)次比较和交换，时间复杂度为(O(n^2))。在最好情况下，即初始序列已经有序，只需进行(n - 1)次比较，时间复杂度为(O(n))。平均时间复杂度为(O(n^2))。
- 空间复杂度：冒泡排序只需要常数级别的额外空间用于交换元素，空间复杂度为(O(1))。
- 稳定性：冒泡排序是稳定的排序算法，因为当两个相等元素相邻时，不会交换它们的位置。
选择排序（Selection Sort）
原理
选择排序是一种简单直观的排序算法。它的工作原理是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
代码实现
#include <iostream>
#include <vector>
void selectionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
std::swap(arr[i], arr[minIndex]);
}
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
selectionSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
复杂度分析
- 时间复杂度：无论初始序列如何，选择排序都需要进行(n(n - 1)/2)次比较，所以时间复杂度始终为(O(n^2))。
- 空间复杂度：选择排序同样只需要常数级别的额外空间，空间复杂度为(O(1))。
- 稳定性：选择排序是不稳定的排序算法。例如序列([5, 5, 3])，在选择最小元素交换时，可能会改变两个(5)的相对顺序。
插入排序（Insertion Sort）
原理
插入排序是一种简单的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in - place排序（即只需用到(O(1))的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
代码实现
#include <iostream>
#include <vector>
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
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;
}
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
insertionSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
复杂度分析
- 时间复杂度：在最坏情况下，即初始序列是逆序的，需要进行(n(n - 1)/2)次比较和移动，时间复杂度为(O(n^2))。在最好情况下，即初始序列已经有序，只需进行(n - 1)次比较，时间复杂度为(O(n))。平均时间复杂度为(O(n^2))。
- 空间复杂度：插入排序只需要常数级别的额外空间，空间复杂度为(O(1))。
- 稳定性：插入排序是稳定的排序算法，因为在插入过程中，相等元素不会交换相对顺序。
希尔排序（Shell Sort）
原理
希尔排序是插入排序的一种改进版本，也称为缩小增量排序。它的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。希尔排序通过将原始数据集合分成不同间隔的子序列，对每个子序列进行插入排序，随着间隔逐渐减小，最后以间隔为1进行一次插入排序，使得整个序列有序。
代码实现
#include <iostream>
#include <vector>
void shellSort(std::vector<int>& arr) {
int n = arr.size();
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; ++i) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
shellSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
复杂度分析
- 时间复杂度：希尔排序的时间复杂度依赖于所选择的增量序列。对于常用的增量序列，如Knuth序列，时间复杂度约为(O(n^{1.5}))。
- 空间复杂度：希尔排序只需要常数级别的额外空间，空间复杂度为(O(1))。
- 稳定性：希尔排序是不稳定的排序算法，因为在不同间隔的插入排序过程中，可能会改变相等元素的相对顺序。
归并排序（Merge Sort）
原理
归并排序是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序的基本思想是将一个序列分成两个子序列，分别对这两个子序列进行排序，然后将排好序的子序列合并成一个最终的有序序列。
代码实现
#include <iostream>
#include <vector>
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector<int> L(n1), R(n2);
for (int i = 0; i < n1; ++i) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = arr[mid + 1 + j];
}
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(std::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);
}
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
mergeSort(arr, 0, arr.size() - 1);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
复杂度分析
- 时间复杂度：归并排序在任何情况下的时间复杂度都是(O(nlogn))，因为它始终将序列分成两部分，然后进行合并操作。
- 空间复杂度：归并排序在合并过程中需要额外的空间来存储临时数据，空间复杂度为(O(n))。
- 稳定性：归并排序是稳定的排序算法，因为在合并过程中，相等元素的相对顺序不会改变。
快速排序（Quick Sort）
原理
快速排序是一种分治的排序算法。它采用了一种称为“基准元素（pivot）”的策略，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
代码实现
#include <iostream>
#include <vector>
int partition(std::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;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(std::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);
}
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr, 0, arr.size() - 1);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
复杂度分析
- 时间复杂度：在平均情况下，快速排序的时间复杂度为(O(nlogn))。在最坏情况下，如每次选择的基准元素都是最大或最小元素，时间复杂度会退化为(O(n^2))。
- 空间复杂度：快速排序的空间复杂度主要取决于递归调用的深度。平均情况下，空间复杂度为(O(logn))；在最坏情况下，空间复杂度为(O(n))。
- 稳定性：快速排序是不稳定的排序算法，因为在划分过程中，可能会改变相等元素的相对顺序。
堆排序（Heap Sort）
原理
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序的基本思想是先将待排序的序列构造成一个大顶堆（升序排序）或小顶堆（降序排序），此时，整个序列的最大值（大顶堆）或最小值（小顶堆）就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余(n - 1)个元素重新构造成一个堆，这样会得到(n)个元素的次大值。如此反复执行，便能得到一个有序序列。
代码实现
#include <iostream>
#include <vector>
void heapify(std::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) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(std::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) {
std::swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
heapSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
复杂度分析
- 时间复杂度：堆排序的时间复杂度在任何情况下都是(O(nlogn))。因为构建堆的时间复杂度为(O(n))，而每次调整堆和交换元素的操作次数为(O(logn))，共需要(n - 1)次调整，所以总的时间复杂度为(O(nlogn))。
- 空间复杂度：堆排序只需要常数级别的额外空间，空间复杂度为(O(1))。
- 稳定性：堆排序是不稳定的排序算法，因为在调整堆的过程中，可能会改变相等元素的相对顺序。
计数排序（Counting Sort）
原理
计数排序是一种非比较排序算法，它适用于一定范围内的整数排序。其基本思想是对于每一个输入元素(x)，确定小于(x)的元素个数，然后根据这个信息将(x)直接放到它在最终有序数组中的位置上。计数排序需要额外的空间来统计每个元素出现的次数。
代码实现
#include <iostream>
#include <vector>
void countingSort(std::vector<int>& arr) {
int maxVal = *std::max_element(arr.begin(), arr.end());
int minVal = *std::min_element(arr.begin(), arr.end());
int range = maxVal - minVal + 1;
std::vector<int> count(range, 0);
std::vector<int> output(arr.size());
for (int num : arr) {
++count[num - minVal];
}
for (int i = 1; i < range; ++i) {
count[i] += count[i - 1];
}
for (int i = arr.size() - 1; i >= 0; --i) {
output[count[arr[i] - minVal] - 1] = arr[i];
--count[arr[i] - minVal];
}
for (int i = 0; i < arr.size(); ++i) {
arr[i] = output[i];
}
}
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
countingSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
复杂度分析
- 时间复杂度：计数排序的时间复杂度为(O(n + k))，其中(n)是待排序元素的个数，(k)是数据的范围。
- 空间复杂度：空间复杂度为(O(k))，因为需要额外的数组来统计每个元素的出现次数。
- 稳定性：计数排序是稳定的排序算法，因为在填充输出数组时，是从后往前遍历输入数组，保证了相等元素的相对顺序不变。
桶排序（Bucket Sort）
原理
桶排序是一种分布式排序算法，它假设输入数据服从均匀分布，将数据分配到有限数量的桶里，每个桶再分别进行排序（可以使用其他排序算法或递归地使用桶排序），最后将各个桶中的数据依次取出，得到有序序列。
代码实现
#include <iostream>
#include <vector>
#include <algorithm>
void bucketSort(std::vector<double>& arr) {
int n = arr.size();
std::vector<std::vector<double>> buckets(n);
for (double num : arr) {
int index = static_cast<int>(n * num);
buckets[index].push_back(num);
}
for (auto& bucket : buckets) {
std::sort(bucket.begin(), bucket.end());
}
int index = 0;
for (const auto& bucket : buckets) {
for (double num : bucket) {
arr[index++] = num;
}
}
}
int main() {
std::vector<double> arr = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};
bucketSort(arr);
std::cout << "排序后的数组: ";
for (double num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
复杂度分析
- 时间复杂度：在平均情况下，如果数据均匀分布，桶排序的时间复杂度为(O(n + k))，其中(n)是元素个数，(k)是桶的数量。但在最坏情况下，时间复杂度可能退化为(O(n^2))。
- 空间复杂度：空间复杂度为(O(n + k))，因为需要额外的空间来存储桶和桶内的数据。
- 稳定性：桶排序的稳定性取决于桶内使用的排序算法。如果桶内使用稳定排序算法，桶排序就是稳定的。
基数排序（Radix Sort）
原理
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序有两种方法：
- LSD（Least significant digital） - 从最低有效位开始排序。
- MSD（Most significant digital） - 从最高有效位开始排序。
代码实现（LSD 基数排序）
#include <iostream>
#include <vector>
int getMax(std::vector<int>& arr) {
return *std::max_element(arr.begin(), arr.end());
}
void countingSortByDigit(std::vector<int>& arr, int exp) {
int n = arr.size();
std::vector<int> output(n);
std::vector<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(std::vector<int>& arr) {
int maxVal = getMax(arr);
for (int exp = 1; maxVal / exp > 0; exp *= 10) {
countingSortByDigit(arr, exp);
}
}
int main() {
std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
复杂度分析
- 时间复杂度：基数排序的时间复杂度为(O(d(n + k)))，其中(d)是数字的最大位数，(n)是元素个数，(k)是基数（通常为10）。
- 空间复杂度：空间复杂度为(O(n + k))，因为需要额外的空间来存储计数数组和临时输出数组。
- 稳定性：基数排序是稳定的排序算法，因为在每一位的排序过程中，相等元素的相对顺序不会改变。
通过以上对各种排序算法的原理讲解、代码实现及复杂度分析，希望能帮助读者深入理解不同排序算法的特点和适用场景，在实际编程中能够根据具体需求选择最合适的排序方法。