rk3588's 小破站 - csp
type: channel
link: http://8.162.1.103/index.php/tag/csp/
items: [算法重构]排序

[算法重构]排序
type: item
date: 2026-03-02T21:28:00+08:00
description: 趁着这学期学数据结构，还有某神秘CSP认证，对过往算法进行系统复习和完善，顺便记录下笔者理解插入排序思想：遍历数组元素，依次把每个元素插入到前面排好的数组中，最基础的排序了最优O(n)，最坏O(n2)void sort_insertion(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; } }希尔排序思想：直接插入排序的进一步优化，通过适当的隔一段采样分组再使用插入排序使得比较大或者比较小的数更快交换到合适位置平均O(n^{3/2})，最坏O(n2)void sort_shell(vector<int> &arr) { int n = arr.size(); for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { //对每个分组分别排序 int key = arr[i]; int j = i; // 注意比较的是 j - gap 位置 while (j >= gap && arr[j - gap] > key) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = key; } } }冒泡排序思想：相邻比较最好O(n),最坏O(n2)void sort_bubble_optimized(vector<int> &arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { bool sign = 0; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); sign = 1; } } // 如果本轮没有交换，说明已经有序 if (!sign) break; } }快速排序思想：选择一个基准，把比基准大的和小的放在基准的两边，对两边再递归，这里基准值的选取非常关键，虽然大多数情况下随机取一个或者取头尾就够用了，但是如果希望进一步优化可以考虑取几个数拿到中值再去做比较，这也是工程常用的一种手段。最好O(nlogn),最坏O(n2)int partition(vector<int>& arr, int low, int high) { int mid = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= mid) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); return i + 1; } void sort_quick(vector<int>& arr,int low,int high) { if (low < high) { int mid = partition(arr, low, high); sort_quick(arr, low, mid-1); sort_quick(arr, mid+1, high); } }堆排序思想：利用堆的特性进行排序。首先将待排序数组构建成一个大顶堆，此时堆顶元素为最大值。将堆顶与堆末尾元素交换，堆大小减1，然后对堆顶进行下沉调整，重复此过程直到堆为空。核心操作是下沉和建堆。时间复杂度：最好 O(n log n)最坏 O(n log n)平均 O(n log n)空间复杂度：O(1)（原地排序，不依赖递归）稳定性：不稳定（堆调整过程中可能改变相同元素的相对顺序）void heapify(vector<int>& arr, int n, int root) { int largest = root; int left = 2 * root + 1; int right = 2 * root + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != root) { swap(arr[root], arr[largest]); heapify(arr, n, largest); //…