include<bits/stdc++.h>
using namespace std;
template
int Partition(T a[],int low,int height){
T pivot=a[low];//这个要用T，因为你不知道这个是什么类型的数据
while(low<height){
while(low<height&&a[height]>=pivot)height--;
a[low]=a[height];
while(low<height&&a[low]<=pivot)low++;
a[height]=a[low];
}
a[low]=pivot;
return low;
}
template
void QuickSort(T a[],int low,int height){
if(low<height){
int pivot=Partition(a,low,height);
QuickSort(a,low,pivot-1);
QuickSort(a,pivot+1,height);
}
}
template
void QuickSort(T a[],int len){
QuickSort(a,0,len-1);
}
int main(){
int a[5]={3,5,7,8,9};
QuickSort(a,5);
int b[5]={1,1,10,9,8};
QuickSort(b,5);
for(auto i:a)cout<<i<<" ";
cout<<endl;
for(auto j:b)cout<<j<<" ";
}
/*
这个有什么缺点呢：
1：如果输入的数据是降序的或者升序的话，那么就会退化为n*n
因为如果正常的递归深度是logn
2：致命伤二：处理“大量重复元素”时的无力感
OI Wiki 逻辑：
while (low < high && pivot <= A[high]) --high;
while (low < high && A[low] <= pivot) ++low;
模拟情景： 假设数组里全是相等的数，如 [5, 5, 5, 5, 5]。
high 指针会一直减，直到撞上 low。
low 指针完全不动。
Partition 返回的索引依然是边界。
后果： 面对全相等的数据，这个模板依然会退化成 O(n ^2)
为什么双指针实战版可以？
实战版的 while(a[i] < pivot)（注意没有等号）会让指针在遇到相等元素时停止并发生交换。
虽然交换看似多余，但它强制让两个指针在中间相遇，从而保证了左右子区间的绝对平衡。
3:OI Wiki 逻辑： 这种“挖坑填数”法在每一轮 while 循环里都有两次赋值操作：
A[low] = A[high] 和 A[high] = A[low]。
实战双指针逻辑： 只有在两个指针都停下时才执行一次 std::swap。
后果： 在处理海量数据时，频繁的内存赋值会导致常数开销变大。
虽然不至于超时，但运行速度会明显慢于双指针版。
4:容易错
OI Wiki 写法： 非常依赖 low < high 的判断和指针的细微移动。
如果你漏写了一个等号，或者顺序反了，极其容易死循环。
双指针写法： do i++; while(a[i] < pivot); 这种写法逻辑更加自恰，且由于它不依赖于 low 和 high 的交替覆盖，代码出错的概率更低。
*/