1 代码
一定非常简单的递归思想: TODO
//quick_sort 思想的最简单的实现
//Author by [Rainboy](https://github.com/rainboylvx)
//date: 2024-07-02 21:39:06
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int n,m;
int a[maxn];
//队列的简单实现,
//其实就是数组
struct Que {
int head;
int arr[maxn];
void clear(){ head = 0;}
void push(int t) { arr[++head] = t; }
//把数据转到数组a里
void to_array_a(int start) {
for(int i = 1 ;i <= head ;++i)
a[start++] = arr[i];
}
};
Que q1,q2;
//对数组a,[l,r]区间内数组进行排序
void quick_sort(int l,int r) {
if( l >= r ) return;
int key = a[l];
//<= key的值放到 q1里
//> key的值放到 q2里
q1.clear();
q2.clear();
//注意这里是从l+1 开始的
// 如果是从l开始对不对?
for(int i =l+1;i<=r ;++i) {
if( a[i] <= key)
q1.push(a[i]);
else
q2.push(a[i]);
}
q1.to_array_a(l);
int key_pos = l + q1.head;
a[key_pos] = key; //放置key
q2.to_array_a(key_pos+1);
quick_sort(l,key_pos-1);
quick_sort(key_pos+1,r);
}
int main (int argc, char *argv[]) {
std::cin >> n;
for(int i = 1;i <= n ;++i ) // i: 1->n
{
cin >> a[i];
}
quick_sort(1,n);
for(int i = 1;i <= n ;++i ) // i: 1->n
{
cout << a[i] << " ";
}
std::cout << "\n";
return 0;
}
2 标准代码
怎么不要两个辅助的数组q1,q2?
也就是怎么原地修改?
想看划分过程一步步怎么交换的,试试这个动画:
快速排序anima1取出数组的第一个元素, 机器人互相扔箱子里的值.
证明这个算法是对的:
- one操作可以分成两个部分.
- 递归一定会缩小范围
3 更好的代码
- 一定要取第一个元素作为key? 这样可能会被针对啊,例如数据TODO,的时间就会退化成
优点: 码量更少,且可以进行随机化
证明, 经过one操作后,L,R 其中任意一个区间不可能为空集
可以想到: [l,r] 至少有两个元素
- 证明R不可能为空集,R区间是由[j+1,r]得到的
等价证明j至少++两次
可以想到,j最右的情况下停止在r,那么i一定会遇到一个>=key的值(因为存在key的值),那么i的值一定会交换到j,
第二次j一定还会j++,那保证[j+1,r]不为空
- 证明L不可能为空集,L区间是由[l,j]得到的,也就是证明j不可能变成l-1,最多变成l
j到多变成l!!!
考虑到j先走,那么j第一趟行走,最多走到L(L就key,且>L,>key),(因为>=key)
如果走到L,那么i变化一次后,与j重合,算法停止
如果没有走到L, 看i再走, 可能走过了L,TODO ,后面就简单了
//Author by [Rainboy](https://github.com/rainboylvx)
//date: 2024-06-24 21:32:12
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int n,m;
int a[maxn];
void print_all() {
for(int i = 1;i <= n ;++i ) // i: 1->n
{
cout << a[i] << " ";
}
std::cout << "\n";
}
void debug(int i,int j) {
print_all();
cout <<i << " ";
cout <<j << "\n";
}
//i到j都是有序的
bool check_seq(int s ,int t) {
for(int i = s+1;i <= t ;++i ) // i: s->t
{
if( a[i] > a[i-1] )
return 0;
}
return 1;
}
template<typename F>
bool check_func(int s,int t,F && f) {
for(int i = s;i <= t ;++i ) // i: s->t
{
if( !f(a[i]))
return 0;
}
return 1;
}
// 核心
int one(int l,int r) {
int key = a[(l+r) / 2];
// cout << " key = " << key << endl;
int i = l-1;
int j = r+1;
while(i < j) {
while( a[--j] > key );
while( a[++i] < key );
// debug(i,j);
// assert(a[i] > a[j]);
// assert(i < j);
// i == j 不需要交换,因为指向同一步位置
// i = j+1 时,交换可能会出错; 数据 1 -1 1 1
// 只有i<j时一定,需要交换
if( i < j) std::swap(a[i],a[j]);
// 证明:
// 0. 证明: 停止时, i == j or i-1 == j 只有这两种情况 : 核心
// 1. j所在的位置的左边一定是 pos<=j 一定是 <= key的
// j 所在的位置的右边一定是 pos > j 一定是>=key
// 2. i所在的位置的左边不一定是 pos<=j 一定是 <= key的
// j 所在的位置的右边一定是 pos > j 一定是>=key
// !!! 还有一个重要的性质:
// 证明一定不会无限递归
// 2个元素一定拆成一边一个,也就是说不会一边两个,一边0个,否则会
// 任意n个元素一定会,拆成的新区间L,R
// L < n and R < n
// 那么就可以证明 一定可以到达边界
// 等价证明 L,R 其中任意一个元素不可能为空集
}
assert( check_func(l,j,[key](int v){ return v <= key;}) );
assert( check_func(j+1,r,[key](int v){ return v >= key;}) );
return j;
}
void quick_sort(int l,int r) {
if( l >= r ) return; //边界
int p = one(l,r);
// cout << "p = " << p << endl;
// assert(check(l,p));
// assert(check(p+1,r));
quick_sort(l,p);
quick_sort(p+1,r);
}
int main (int argc, char *argv[]) {
std::cin >> n;
for(int i = 1;i <= n ;++i ) // i: 1->n
{
cin >> a[i];
}
// print_all();
// cout << "===" << endl;
quick_sort(1 , n);
for(int i = 1;i <= n ;++i ) // i: 1->n
{
cout << a[i] << " ";
}
std::cout << "\n";
return 0;
}