十大排序算法

排序算法 插入排序冒泡排序选择排序希尔排序计数排序快速排序1经典 Lomuto 分区法2经典 Lomuto 分区法3随机快排 堆排序归并排序桶排序基数排序

插入排序

从i=1开始，判断nums[i-1]和nums[i]的大小，一直到nums[i]插入到自己的位置。模拟抓扑克牌的过程：将元素插入到已排序的部分，使其有序

void insertionSort(vector<int>& nums) { for (int i = 1; i < nums.size(); i++) { int key = nums[i]; // 选出当前元素 int j = i - 1; // 将比 key 大的元素往后移动 while (j >= 0 && nums[j] > key) { nums[j + 1] = nums[j]; j--; } nums[j + 1] = key; // 插入 key } } 冒泡排序

两两比较相邻元素并交换，每一轮将最大（或最小）值冒泡到最后

void bubbleSort(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n - 1; i++) { bool swapped = false; // 优化点：如果没有交换，就提前结束 for (int j = 0; j < n - i - 1; j++) { if (nums[j] > nums[j + 1]) { swap(nums[j], nums[j + 1]); swapped = true; } } if (!swapped) break; // 如果没有发生交换，说明已排序，提前结束 } } 选择排序

每轮都选一个最小值放到前面，类似“挑选最小的牌放到前面”。

void selectionSort(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n - 1; i++) { int minIdx = i; for (int j = i + 1; j < n; j++) { if (nums[j] < nums[minIdx]) { minIdx = j; // 记录最小元素位置 } } swap(nums[i], nums[minIdx]); // 交换最小值 } } 希尔排序 • 先将数据分成多个间隔为 gap 的子序列，每个子序列进行插入排序。 • 逐步缩小 gap，直到 gap = 1 时，相当于进行一次普通的插入排序。 • 避免插入排序的相邻移动问题，提升性能。 void shellSort(vector<int>& nums) { int n = nums.size(); for (int gap = n / 2; gap > 0; gap /= 2) { // 逐步缩小 gap for (int i = gap; i < n; i++) { int key = nums[i]; int j = i; while (j >= gap && nums[j - gap] > key) { nums[j] = nums[j - gap]; // 远距离插入排序 j -= gap; } nums[j] = key; } } } 计数排序 1. 统计频次：遍历数组，统计每个数出现的次数，并存入计数数组 count[]。 2. 前缀和计算：构造 count[i] 的前缀和，表示小于等于 i 的元素个数，这样可以确定 i 的最终位置。 3. 回填结果：倒序遍历原数组，根据 count[] 计算元素的最终位置，并存入 output[]，完成排序。 #include <iostream> #include <vector> using namespace std; void countingSort(vector<int>& nums) { if (nums.empty()) return; int maxVal = *max_element(nums.begin(), nums.end()); int minVal = *min_element(nums.begin(), nums.end()); int range = maxVal - minVal + 1; // 计算数据范围 vector<int> count(range, 0); // 计数数组 vector<int> output(nums.size()); // 1️⃣ 统计每个数出现的次数 for (int num : nums) { count[num - minVal]++; // 映射到 0 ~ range-1 } // 2️⃣ 计算前缀和，计算元素最终位置 for (int i = 1; i < count.size(); i++) { count[i] += count[i - 1]; } // 3️⃣ 倒序遍历原数组，填充输出数组 for (int i = nums.size() - 1; i >= 0; i--) { output[count[nums[i] - minVal] - 1] = nums[i]; // 定位到排序后的位置 count[nums[i] - minVal]--; // 位置减 1 } // 4️⃣ 复制回原数组 nums = output; } int main() { vector<int> nums = {4, 2, 2, 8, 3, 3, 1}; countingSort(nums); for (int num : nums) cout << num << " "; return 0; } 快速排序 1经典 Lomuto 分区法 • 选择最右边元素作为 基准值（pivot）。 • 维护一个 小于 pivot 的区域（指针 i）。 • 遍历数组，遇到比 pivot 小的元素，就交换到前面，最后 i 和 pivot 交换位置。 #include <iostream> #include <vector> using namespace std; int partition(vector<int>& nums, int left, int right) { int pivot = nums[right]; // 选取最右元素作为基准 int i = left; // i 指向小于 pivot 的区域的边界 for (int j = left; j < right; j++) { if (nums[j] < pivot) { swap(nums[i], nums[j]); i++; // 扩大小于 pivot 的区域 } } swap(nums[i], nums[right]); // 把 pivot 放到正确位置 return i; // 返回 pivot 的索引 } void quickSort(vector<int>& nums, int left, int right) { if (left >= right) return; // 递归终止条件 int pivotIndex = partition(nums, left, right); quickSort(nums, left, pivotIndex - 1); quickSort(nums, pivotIndex + 1, right); } int main() { vector<int> nums = {4, 2, 6, 9, 1, 3}; quickSort(nums, 0, nums.size() - 1); for (int num : nums) cout << num << " "; return 0; } 2经典 Lomuto 分区法

Hoare 方法避免了Lomuto 的额外交换，一般在实际应用中更快： 1. 选择左边界的元素作为 pivot。 2. 左右双指针，左指针找比 pivot 大的元素，右指针找比 pivot 小的元素，然后交换。 3. 直到 left >= right，然后 right 作为新的 pivot 位置。

int partition(vector<int>& nums, int left, int right) { int pivot = nums[left]; // 选取最左元素作为基准 int i = left - 1, j = right + 1; while (true) { do { i++; } while (nums[i] < pivot); // 找到大于等于 pivot 的元素 do { j--; } while (nums[j] > pivot); // 找到小于等于 pivot 的元素 if (i >= j) return j; // 交叉时返回分区点 swap(nums[i], nums[j]); // 交换元素 } } 3随机快排

最坏情况下（如输入数组已经有序），快排可能退化到 O(n²)。随机化基准可以避免这种情况：

int partition(vector<int>& nums, int left, int right) { int randomIndex = left + rand() % (right - left + 1); // 随机选取 pivot swap(nums[randomIndex], nums[right]); // 交换到右端 return lomuto_partition(nums, left, right); // 仍然使用 Lomuto 方法 } 堆排序 1. 构建最大堆（Max Heap）： • 将数组调整为最大堆，保证根节点最大。 2. 交换根节点与最后一个元素： • 每次取出堆顶（最大值）并放入数组末尾，形成有序部分。 3. 堆调整（Heapify）： • 交换后，重新调整剩余部分为最大堆，保证继续取最大值。 堆排序使用二叉堆（Binary Heap），通常是 最大堆（Max Heap）： • 最大堆：A[i] ≥ A[2*i+1] && A[i] ≥ A[2*i+2]（根节点比子节点大）。 • 最小堆：A[i] ≤ A[2*i+1] && A[i] ≤ A[2*i+2]（根节点比子节点小）。

堆的性质 • 完全二叉树（Complete Binary Tree）。 • 根节点存储最大/最小值。 • 数组存储（i 位置的子节点：2i+1, 2i+2）。

#include <iostream> #include <vector> using namespace std; // **堆调整（维护最大堆）** void heapify(vector<int>& arr, int n, int i) { int largest = i; // 假设当前 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(); // **1. 构建最大堆** for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // **2. 交换最大值，并调整堆** for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); // 最大值放到最后 heapify(arr, i, 0); // 重新调整堆 } } // **测试** int main() { vector<int> arr = {4, 10, 3, 5, 1}; heapSort(arr); for (int num : arr) cout << num << " "; return 0; } 归并排序 1. 分割（Divide）： • 递归地将数组从中间拆分成两个子数组，直到每个子数组只包含一个元素（单个元素天然有序）。 2. 合并（Merge）： • 将两个已排序的子数组合并成一个有序数组。 #include <iostream> #include <vector> using namespace std; // 合并两个有序子数组 void merge(vector<int>& arr, int left, int mid, int right) { vector<int> temp(right - left + 1); // 临时数组存储合并后的有序数组 int i = left; // 左子数组起点 int j = mid + 1; // 右子数组起点 int k = 0; // 临时数组索引 // 逐个比较左右子数组的元素，选择较小的放入临时数组 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // 处理左子数组剩余元素 while (i <= mid) { temp[k++] = arr[i++]; } // 处理右子数组剩余元素 while (j <= right) { temp[k++] = arr[j++]; } // 将临时数组拷贝回原数组 for (int p = 0; p < temp.size(); p++) { arr[left + p] = temp[p]; } } // 归并排序递归函数 void mergeSort(vector<int>& arr, int left, int right) { if (left >= right) return; // 递归终止条件：当子数组只有一个元素时返回 int mid = left + (right - left) / 2; // 计算中间索引 mergeSort(arr, left, mid); // 递归排序左半部分 mergeSort(arr, mid + 1, right); // 递归排序右半部分 merge(arr, left, mid, right); // 合并两个有序子数组 } // 测试归并排序 int main() { vector<int> arr = {8, 4, 3, 12, 25, 6, 13, 10}; cout << "排序前："; for (int num : arr) cout << num << " "; cout << endl; mergeSort(arr, 0, arr.size() - 1); cout << "排序后："; for (int num : arr) cout << num << " "; cout << endl; return 0; } 桶排序 1. 创建桶：根据数据范围创建适当数量的桶，每个桶存储一定范围内的数据。 2. 数据分配：遍历原始数组，将元素分配到对应的桶中。 3. 桶内排序：对每个桶内部的数据进行排序（可以使用插入排序、快速排序或STL的sort）。 4. 合并数据：按照顺序依次合并所有桶中的数据。 #include <iostream> #include <vector> #include <algorithm> using namespace std; // 桶排序函数 void bucketSort(vector<float>& arr) { int n = arr.size(); if (n <= 1) return; // 1. 创建 n 个桶 vector<vector<float>> buckets(n); // 2. 把元素分配到不同的桶中 for (int i = 0; i < n; i++) { int index = n * arr[i]; // 映射到对应桶 buckets[index].push_back(arr[i]); } // 3. 对每个桶内部进行排序 for (int i = 0; i < n; i++) { sort(buckets[i].begin(), buckets[i].end()); // 使用 STL 的 sort 进行排序 } // 4. 合并所有桶的数据 int idx = 0; for (int i = 0; i < n; i++) { for (float num : buckets[i]) { arr[idx++] = num; } } } // 测试桶排序 int main() { vector<float> arr = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68}; cout << "排序前: "; for (float num : arr) cout << num << " "; cout << endl; bucketSort(arr); cout << "排序后: "; for (float num : arr) cout << num << " "; cout << endl; return 0; } 基数排序 基数排序简介 基数排序（Radix Sort）是一种非比较排序算法，它基于按位分配的思想，逐位对数据进行排序。通常用于整数或字符串的排序，尤其适用于数据范围较大的情况。基数排序的基本思路 基数排序的核心思想是： 按照个位、十位、百位……的顺序，从低位到高位依次进行排序（LSD 方式）。使用稳定排序（通常是计数排序或桶排序）在每一位上对数据进行排序。最终得到有序数组。 基数排序的实现步骤 假设有一组数字：{170, 45, 75, 90, 802, 24, 2, 66} #include <iostream> #include <vector> #include <algorithm> using namespace std; // 计数排序，按指定的 digit 进行排序 void countingSort(vector<int>& arr, int exp) { int n = arr.size(); vector<int> output(n); // 存储排序后的结果 vector<int> count(10, 0); // 计数数组，存储 0~9 的个数 // 统计当前位数字出现的次数 for (int i = 0; i < n; i++) { int digit = (arr[i] / exp) % 10; // 获取当前位的数字 count[digit]++; } // 计算累积和，确定数字在 output 数组中的位置 for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } // 从右往左遍历原数组，将元素放入正确的位置（确保稳定排序） for (int i = n - 1; i >= 0; i--) { int digit = (arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; count[digit]--; } // 复制回原数组 for (int i = 0; i < n; i++) { arr[i] = output[i]; } } // 基数排序 void radixSort(vector<int>& arr) { int maxVal = *max_element(arr.begin(), arr.end()); // 找到最大值 // 依次按照个位、十位、百位等进行排序 for (int exp = 1; maxVal / exp > 0; exp *= 10) { countingSort(arr, exp); } } // 测试代码 int main() { vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66}; cout << "排序前: "; for (int num : arr) cout << num << " "; cout << endl; radixSort(arr); cout << "排序后: "; for (int num : arr) cout << num << " "; cout << endl; return 0; }