快速排序的优化：荷兰国旗问题

测试

PTA：校内链接7-1 排序 - Search & Sort（信安24）

题目

图解

因为嗯，我觉得文字描述太干了，而且很难看也是画了个图解好理解一点ovo

首先是一个乱序的数组我们给他排序，我们先设置两个界限，和三个指针，下面会给出每个东西的含意，和基本的逻辑

然后我们来模拟逻辑

代码

#include<iostream> using namespace std; const int N = 1e5 + 2; int arr[N]; int first, last;//全局变量作为partition的返回值 void swap(int x, int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } void partition(int l, int r, int x) { first = l, last = r; int i = l; while (i <= last) { if (arr[i] == x) i++; else if (arr[i] < x) { swap(i++, first++); } else { swap(last--, i); } } } void sort(int l,int r) { if (l >= r) return; partition(l, r, arr[(l + r) / 2]); int fir = first; int las = last; sort(l, fir - 1); sort(las + 1, r); } int main() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> arr[i]; sort(0, n - 1); for (int i = 0; i < n; i++) cout << arr[i] <<" "[i==n-1]; }

结果