C++实现常用排序算法对比与测试

排序算法的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 的数组。然后，我们使用每种排序算法对数组进行排序，并记录排序时间。结果表明，快速排序和归并排序的时间复杂度远远低于其他排序算法。 本文对常用的排序算法进行了介绍和实现，并对它们的时间和空间复杂度进行了分析。这些算法可以广泛应用于实际开发中，例如数据处理、数据库查询等领域。