排序算法的C++实现
排序算法是计算机科学中最基本和重要的算法之一，在实际应用中广泛使用。C++作为一门强大的编程语言，提供了多种排序算法的实现。本文将对常用的排序算法进行介绍和实现，包括冒泡排序、选择排序、插入排序、堆排序、快速排序、归并排序等，并对它们的时间和空间复杂度进行分析。
一、冒泡排序
冒泡排序是一种简单的排序算法，通过不断地比较相邻的元素，将最大的元素“冒泡”到数组的末尾。该算法的时间复杂度为O(n^2)，空间复杂度为O(1)。以下是冒泡排序的C++实现代码：
```cpp
void bubble_sort(vector<int>& v) {
int n = v.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (v[j] > v[j + 1]) {
swap(v[j], v[j + 1]);
}
}
}
}
```
二、选择排序
选择排序是一种简单的排序算法，通过选择最小或最大的元素，将其置于数组的开头。该算法的时间复杂度为O(n^2)，空间复杂度为O(1)。以下是选择排序的C++实现代码：
```cpp
void select_sort(vector<int>& v) {
int n = v.size();
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (v[j] < v[min_idx]) {
min_idx = j;
}
}
swap(v[i], v[min_idx]);
}
}
```
三、插入排序
插入排序是一种简单的排序算法，通过将每个元素插入到已排序的数组中。该算法的时间复杂度为O(n^2)，空间复杂度为O(1)。以下是插入排序的C++实现代码：
```cpp
void insert_sort(vector<int>& v) {
int n = v.size();
for (int i = 1; i < n; i++) {
int key = v[i];
int j = i - 1;
while (j >= 0 && v[j] > key) {
v[j + 1] = v[j];
j--;
}
v[j + 1] = key;
}
}
```
四、堆排序
堆排序是一种高效的排序算法，通过构建堆将元素排序。该算法的时间复杂度为O(n log n)，空间复杂度为O(1)。以下是堆排序的C++实现代码：
```cpp
void heap_sort(vector<int>& v) {
int n = v.size();
build_heap(v);
for (int i = n - 1; i > 0; i--) {
swap(v[0], v[i]);
heapify(v, 0, i);
}
}
void build_heap(vector<int>& v) {
int n = v.size();
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(v, i, n);
}
}
void heapify(vector<int>& v, int i, int n) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && v[l] > v[largest]) {
largest = l;
}
if (r < n && v[r] > v[largest]) {
largest = r;
}
if (largest != i) {
swap(v[i], v[largest]);
heapify(v, largest, n);
}
}
```
五、快速排序
快速排序是一种高效的排序算法，通过递归地将数组分成两个部分，分别排序。该算法的时间复杂度为O(n log n)，空间复杂度为O(log n)。以下是快速排序的C++实现代码：
```cpp
void quick_sort(vector<int>& v) {
quick_sort_recursive(v, 0, v.size() - 1);
}
void quick_sort_recursive(vector<int>& v, int low, int high) {
if (low < high) {
int pivot = partition(v, low, high);
quick_sort_recursive(v, low, pivot - 1);
quick_sort_recursive(v, pivot + 1, high);
}
}
int partition(vector<int>& v, int low, int high) {
int pivot = v[low];
int i = low + 1;
int j = high;
while (i <= j) {
while (i <= j && v[i] <= pivot) {
i++;
}
while (i <= j && v[j] > pivot) {
j--;
}
if (i <= j) {
swap(v[i], v[j]);
}
}
swap(v[low], v[j]);
return j;
}
```
六、归并排序
归并排序是一种高效的排序算法，通过将数组分成两个部分，分别排序，然后合并。该算法的时间复杂度为O(n log n)，空间复杂度为O(n)。以下是归并排序的C++实现代码：
```cpp
void merge_sort(vector<int>& v) {
int n = v.size();
if (n <= 1) {
return;
}
int mid = n / 2;
vector<int> left(v.begin(), v.begin() + mid);
vector<int> right(v.begin() + mid, v.end());
merge_sort(left);
merge_sort(right);
merge(left, right, v);
}
void merge(vector<int>& left, vector<int>& right, vector<int>& v) {
int i = 0;
int j = 0;
int k = 0;
while (i < left.size() && j < right.size()) {
if (left[i] <= right[j]) {
v[k++] = left[i++];
} else {
v[k++] = right[j++];
}
}
while (i < left.size()) {
v[k++] = left[i++];
}
while (j < right.size()) {
v[k++] = right[j++];
}
}
```
七、测试和对比
为了测试和对比这些排序算法，我们使用了 vector 容器来存储要排序的数据，并使用随机数 generator 生成了一个大小为 1000000 的数组。然后，我们使用每种排序算法对数组进行排序，并记录排序时间。结果表明，快速排序和归并排序的时间复杂度远远低于其他排序算法。
本文对常用的排序算法进行了介绍和实现，并对它们的时间和空间复杂度进行了分析。这些算法可以广泛应用于实际开发中，例如数据处理、数据库查询等领域。
我的内容管理
展开
