洛谷 P1177 【模板】排序从入门到精通：核心算法剖析与实战代码演进-平芜编程栈

1. 排序算法入门：从洛谷P1177开始

第一次接触排序算法时，我完全被各种专业术语搞晕了。直到在洛谷刷到P1177这道排序模板题，才真正理解了算法的魅力。这道题就像算法界的"Hello World"，看似简单却能让我们掌握计算机科学中最基础也最重要的思想。

题目要求很简单：输入N个数字，输出排序后的结果。但就是这个简单的需求，背后藏着至少5种经典解法。新手最容易上手的是直接调用sort函数，只需要3行核心代码就能AC。但真正想学算法的人，一定会尝试自己实现排序逻辑。我建议初学者按照这个路线图来学习：库函数调用→冒泡排序→快速排序→归并排序，难度循序渐进。

记得我第一次提交冒泡排序时，因为没注意数组越界导致WA了3次。后来才发现是循环条件写错了，把j<n写成了j<=n。这种细节问题在初学阶段特别常见，建议大家多写注释，逐步调试。

2. 五种经典排序实现详解

2.1 偷懒但实用的sort函数

C++的库里的sort函数绝对是新手的福音。它采用类似快速排序的混合算法(IntroSort)，时间复杂度是O(NlogN)，对于1e5量级的数据完全够用。基本用法是sort(起始地址, 结束地址)，比如：

#include<bits/stdc++.h> using namespace std; int a[100005]; // 注意数组要开得比题目要求稍大 int main() { int n; cin >> n; for(int i=0; i<n; i++) cin >> a[i]; sort(a, a+n); // 关键语句 for(int i=0; i<n; i++) cout << a[i] << " "; }

进阶用法可以自定义比较函数。比如要降序排列，可以：

bool cmp(int x, int y){ return x > y; } sort(a, a+n, cmp);

2.2 冒泡排序的两种写法

虽然时间复杂度是O(n²)，但冒泡排序的逻辑最直观。我推荐先掌握这种基础版本：

for(int i=0; i<n-1; i++) for(int j=0; j<n-i-1; j++) if(a[j] > a[j+1]) swap(a[j], a[j+1]);

另一种我称为"选择式冒泡"的写法更易记忆：

for(int i=0; i<n-1; i++) for(int j=i+1; j<n; j++) if(a[i] > a[j]) swap(a[i], a[j]);

这两种写法在洛谷P1177都会超时，但作为算法入门练习很有价值。实际测试发现，当n=1e4时，冒泡排序需要约500ms，而sort函数仅需5ms。

2.3 快速排序的优化之路

快排的平均时间复杂度是O(NlogN)，但写不好会退化成O(n²)。我经历过三个阶段的优化：

最初版（效率低）：

void quickSort(int l, int r) { if(l >= r) return; int pivot = a[l], i = l, j = r; while(i < j) { while(i<j && a[j]>=pivot) j--; while(i<j && a[i]<=pivot) i++; if(i < j) swap(a[i], a[j]); } swap(a[l], a[i]); quickSort(l, i-1); quickSort(i+1, r); }

改进版（取中位数作为基准）：

void quickSort(int q[], int l, int r) { if(l >= r) return; int mid = q[(l+r)>>1], i = l-1, j = r+1; while(i < j) { do i++; while(q[i] < mid); do j--; while(q[j] > mid); if(i < j) swap(q[i], q[j]); } quickSort(q, l, j); quickSort(q, j+1, r); }

最终版（加入插入排序优化）：

void quickSort(int q[], int l, int r) { if(r - l < 16) { // 小规模数据用插入排序 for(int i=l+1; i<=r; i++) { int temp = q[i], j; for(j=i; j>l && q[j-1]>temp; j--) q[j] = q[j-1]; q[j] = temp; } return; } int mid = q[l + rand()%(r-l+1)], i = l, j = r; // 后续相同... }

2.4 归并排序的稳定优势

归并排序虽然也是O(NlogN)，但它是稳定排序，特别适合需要保持原始顺序的场景。核心思想是分治法：

int tmp[100005]; // 临时数组 void mergeSort(int q[], int l, int r) { if(l >= r) return; int mid = (l + r) >> 1; mergeSort(q, l, mid); mergeSort(q, mid+1, r); int k = 0, i = l, j = mid+1; while(i <= mid && j <= r) tmp[k++] = q[i] <= q[j] ? q[i++] : q[j++]; while(i <= mid) tmp[k++] = q[i++]; while(j <= r) tmp[k++] = q[j++]; for(i=l, j=0; i<=r; i++, j++) q[i] = tmp[j]; }

2.5 堆排序的进阶应用

虽然题目没要求，但作为完整的学习，堆排序也值得掌握：

void heapify(int n, int i) { int largest = i, l = 2*i+1, r = 2*i+2; if(l<n && a[l]>a[largest]) largest = l; if(r<n && a[r]>a[largest]) largest = r; if(largest != i) { swap(a[i], a[largest]); heapify(n, largest); } } void heapSort() { for(int i=n/2-1; i>=0; i--) heapify(n, i); for(int i=n-1; i>0; i--) { swap(a[0], a[i]); heapify(i, 0); } }