# 怎么用C++实现十大排序算法 排序算法是计算机科学中最基础的算法之一，本文将通过C++代码示例详细讲解十大经典排序算法的实现原理，包括： - 冒泡排序 - 选择排序 - 插入排序 - 希尔排序 - 归并排序 - 快速排序 - 堆排序 - 计数排序 - 桶排序 - 基数排序 ## 1. 冒泡排序（Bubble Sort） ### 基本思想 通过重复遍历待排序序列，比较相邻元素并交换位置，使较大元素逐渐"浮"到右侧。 ### C++实现 ```cpp void bubbleSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n-1; i++) { 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; // 提前终止优化 } } 每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。
void selectionSort(vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n-1; i++) { int min_idx = i; for (int j = i+1; j < n; j++) { if (arr[j] < arr[min_idx]) { min_idx = j; } } swap(arr[i], arr[min_idx]); } } 将未排序元素逐个插入到已排序部分的正确位置。
void insertionSort(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; } } 插入排序的改进版，通过将原始列表分成多个子序列来提高效率。
void shellSort(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; } } } 分治法的典型应用，将数组分成两半分别排序，然后合并结果。
void merge(vector<int>& arr, int l, int m, int r) { vector<int> temp(r - l + 1); int i = l, j = m + 1, k = 0; while (i <= m && j <= r) { if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } while (i <= m) temp[k++] = arr[i++]; while (j <= r) temp[k++] = arr[j++]; for (int p = 0; p < k; p++) { arr[l + p] = temp[p]; } } void mergeSort(vector<int>& arr, int l, int r) { if (l < r) { int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } } 分治法，选择一个基准元素将数组分成两部分，左边小于基准，右边大于基准。
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; } void quickSort(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); } } 利用堆这种数据结构设计的排序算法，分为建堆和排序两个阶段。
void heapify(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) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(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--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } } 适用于整数排序，通过统计元素出现次数来实现排序。
void countingSort(vector<int>& arr) { int max_val = *max_element(arr.begin(), arr.end()); int min_val = *min_element(arr.begin(), arr.end()); int range = max_val - min_val + 1; vector<int> count(range), output(arr.size()); for (int num : arr) count[num - min_val]++; 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] - min_val] - 1] = arr[i]; count[arr[i] - min_val]--; } arr = output; } 将元素分到有限数量的桶里，每个桶再分别排序。
void bucketSort(vector<float>& arr) { int n = arr.size(); vector<vector<float>> buckets(n); // 将元素分配到桶中 for (float num : arr) { int bucket_idx = n * num; buckets[bucket_idx].push_back(num); } // 对每个桶排序 for (auto& bucket : buckets) { sort(bucket.begin(), bucket.end()); } // 合并桶 int index = 0; for (auto& bucket : buckets) { for (float num : bucket) { arr[index++] = num; } } } 按照低位先排序，然后收集；再按照高位排序，再收集；依次类推。
void countingSortForRadix(vector<int>& arr, int exp) { vector<int> output(arr.size()); vector<int> count(10, 0); for (int num : arr) count[(num / exp) % 10]++; for (int i = 1; i < 10; i++) count[i] += count[i - 1]; for (int i = arr.size() - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } arr = output; } void radixSort(vector<int>& arr) { int max_val = *max_element(arr.begin(), arr.end()); for (int exp = 1; max_val / exp > 0; exp *= 10) { countingSortForRadix(arr, exp); } } | 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n log n) | O(n²) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | 稳定 |
| 桶排序 | O(n + k) | O(n²) | O(n + k) | 稳定 |
| 基数排序 | O(nk) | O(nk) | O(n + k) | 稳定 |
在实际应用中，应根据数据特点选择合适的排序算法： - 小规模数据：插入排序 - 大规模随机数据：快速排序 - 需要稳定性：归并排序 - 整数排序：计数/基数排序 - 内存受限：堆排序
希望本文能帮助你理解并掌握这十大排序算法的C++实现！ “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
