快速排序（升序+降序）

对于大部分的书上的快速排序，都是升序。对于降序，大部分人应该和我一样，并没有什么概念。当然，没有概念的主要原因就是你对快排机制还是不够透彻。

下面是笔者花费很久时间才搞明白的点。如有帮助请点赞+关注+转发 。

首先，明确一下快排的概念:在一个闭区间，每次确定一个数（我们取最左边得数，a[l]）的位置，并且使其余数变得相对有序。

那么看的懂上面的概念应该算是入门了，看不懂得话，先去看看书再回来把。

这里得相对有序，就是升序还是降序得关键了。

• 升序
  • 从右边开始，小于a[l]的数，全部放到a[l]的左边
  • 从左边开始，大于a[l]的数，全部放到a[l]的右边
• 降序
  • 从右边开始，大于a[l]的数，全部放到a[l]的左边
  • 从左边开始，小于a[l]的数，全部放到a[l]的右边

接下来看代码：

#include<bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int mod = 1e9 + 7;
const int maxl = 1e5 + 7;int n = -1, temp;//n从下标-1开始， 为了，使范围是[0,n]， 而不是[0, n) 
int a[maxl];void quickGreater(int l ,int r){if (l < r){//判断是否越界 int lnow = l, rnow = r, temp = a[l];while (lnow < rnow){//为了找出temp的正确位置，出口lnow == rnow while (lnow < rnow && a[rnow] >= temp)	rnow--;//从最左边，找一个比temp小的数放到temp的位置 if (lnow < rnow)	a[lnow++] = a[rnow];while (lnow < rnow && a[lnow] < temp)	lnow++;//从最右边，一个比temp大的数放到temp的位置 if (lnow < rnow)	a[rnow--] = a[lnow];}a[lnow] = temp;//把出口，赋上开始的temp quickGreater(l, lnow - 1);//出口左边 quickGreater(lnow + 1, r);//出口右边 }
}void quickLess(int l ,int r){if (l < r){int lnow = l, rnow = r, temp = a[l];while (lnow < rnow){while (lnow < rnow && a[rnow] < temp)	rnow--;//从最左边，找一个比temp大的数放到temp的位置 if (lnow < rnow)	a[lnow++] = a[rnow];while (lnow < rnow && a[lnow] >= temp)	lnow++;//从最左边，找一个比temp大的数放到temp的位置 if (lnow < rnow)	a[rnow--] = a[lnow];}a[lnow] = temp;quickLess(l, lnow - 1);quickLess(lnow + 1, r);}
}void slove(){while (cin >> temp) a[++n] = temp;//输入 cout << "快速排序（升序）:";quickGreater(0, n);for (int i = 0; i <= n; i++)	cout << a[i] << '\\t';cout << endl;cout << "快速排序（降序）:";quickLess(0, n);for (int i = 0; i <= n; i++)	cout << a[i] << '\\t';cout << endl;
}int main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;
//	cin >> t;while (t--){slove();}return 0;
}/*输入; 
6 3 5
键盘：ctrl + z
*/