快排复习#
0 冒泡排序好像TLE了 不如我们...
又要排序了 愉快的使用闭着眼睛就能敲出来的冒泡吧！
恭喜TLE+1(Time Limit Enough运行时间充裕) （雾
那我要调用sort()，当然可以 但是惊闻KaiKai说 现在的年轻人 连快排都不会写了
1.1 历史的进程
快速排序是由Tony Hoare于1959年发明的(前辈 要致敬的)
那么就会有人问了 上个世纪的东西为什么这么厉害呢 快速排序真的很快吗？
当然这样说说肯定不行 我们要看看复杂度
最好情况：O(nlgn)
最坏情况：O(n^2) (退化为大家最爱的冒泡排序 每次划分只能划分为一个元素 和 另一堆剩余元素 递归树是单侧的斜着的 但是出现的概率是多少呢 学了概统的大家可以算算)
平均表现：O(nlgn)
看起来也和归并之类的差不多啦 会不会只是叫快排 而实际上超逊的呢？
事实上，如果发挥正常，使用得当，快排会比归并排序和堆排序快2~3倍（超勇的
那么为什么呢？
1.2 归并排序与快排
明明大家都是O(nlgn)你却大多数时候时候比我快QAQ
归并排序T(n)=T(n/2)+T(n/2)+mergetime
void merge(int input[], int temp[], int left, int right) {
if (left >= right)
return;
int mid = (right - left)/2 + left;
int from1 = left, end1 = mid;
int from2 = mid + 1, end2 = right;
merge(input, temp, from1, end1);
merge(input, temp, from2, end2);
int k = left;
while (from1 <= end1 && from2 <= end2){//1
temp[k++] = input[from1] < input[from2] ? input[from1++] : input[from2++];
merge_count++;
}
while (from1 <= end1) temp[k++] = input[from1++];
while (from2 <= end2) temp[k++] = input[from2++];
for (k = left; k <= right; k++) input[k] = temp[k];//2
}
void merge_sort(int input[], int n) {
int temp[MAX];
merge(input, temp, 0, n - 1);
}
在mergetime中 我们需要n-1次的两两比较(//1) 和 n次的从temp数组移出来(//2) 因此是2n-1
快速排序T(n)=T(n/2)+T(n/2)+quicktime
void quicksort(int a[],int left,int right){
if(left < right){
int l = left,r = right;
int temp = a[left];
while(l < r){
while(l < r && a[r] >= a[l]) r--;
swap(a[l],a[r]);
while(l < r && a[l] < a[r]) l++;
swap(a[l],a[r]);
}
a[l] = temp;
quicksort(a, left, l-1);
quicksort(a, l+1, right);
}
}
quicktime主要就是while(l < r)部分中的比较了 最坏情况下对每次l和r我们都要执行一次比较和互换，因此quicktime是n+n=2n，但这仅仅是最坏的情况，出现的概率很小。大多数情况下仅会进行很少的几次比较和交换。
通过上述发现，快排比归并快主要体现在划分的过程中，减小了没必要的比较和空间上的转移而造成的时间浪费，从而比归并排序要快的。
2 Show Me The Code
void quicksort(int a[],int left,int right){
if(left < right){
int l = left,r = right;
int temp = a[left];
while(l < r){
while(l < r && a[r] >= temp) r--;
swap(a[l],a[r]);
while(l < r && a[l] <= temp) l++;
swap(a[l],a[r]);
}
a[l] = temp;
quicksort(a, left, l-1);
quicksort(a, l+1, right);
}
}
常见的快排写法就是这样啦 以从小到大排序为例。每次我们寻找一个一个基准记为temp，那么遍历一遍数组，比基准小的放在基准前面，比基准小的放在基准的后面。接着，我们递归地 对基准前的子数组和基准后的子数组进行划分操作，最终实现排序。这一过程是不稳定的，原地的，不需要额外的数组空间。
3 有没有那种 就是...
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
大家看到这道题很高兴的调用了sort(),也有手搓快排的那么时间复杂度都在O(nlgn)
TLE++;
勇一点的可能会上桶排序，但是MLE可能在会等着你。
那么有没有那种 就是...平均复杂度O(n)的呢？
有的啊
我们仔细想想快排的思想 本质上是在划分 那么我们先愉快的写一个划分吧
注意这里要从大到小了
int partition(vector<int>& nums, int l,int r){
int temp = nums[l];
while(l < r){
int temp = nums[l];
while(l < r){
while(l < r && nums[r] <= temp) r--;
swap(nums[l],nums[r]);
while(l < r && nums[l] >= temp) l++;
swap(nums[l],nums[r]);
}
}
nums[l] = temp;
return l;
}
这里我们执行了一次划分操作，即把基准temp放在了一个位置，基准前的都比基准大，基准后的都比基准小 l就是基准最后所在的位置
那么这是想一想 如果l刚好和k-1相等(假设数组下标从0开始) 那么基准不就是要找的数字吗(前面有k-1个比他大的 他就是第k大的) 我们就可以愉快的返回了；如果 l > k-1那么很不幸运，我们的基准选的有点小了 造成基准是第k+eps(eps=1、2...)个大的元素，那么我们就在[left,l-1]这个区间找找；反之，基准选大了，就在[l+1,right]里面找找
int search(vector<int>& nums,int l,int r,int k){
int m =partition(nums,l,r);
if(m == k-1) return nums[m];
else if(m > k-1) return search(nums,l,m-1,k);
else return search(nums,m+1,r,k);
}
这样就解决了问题。
我们并没有对数组进行排序，而是根据情况递归的寻找第k大的数，因此复杂度是比快排本身要低的。
但是如果数组本身就是有序的情况下，复杂度还是会飙升至O(n^2 )
关于这个问题的详细复杂度分析可以看看算导的第九章
完整函数代码 想尝试的可以移步leetcode
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/description/
int partition(vector<int>& nums, int l,int r){
int temp = nums[l];
while(l < r){
int temp = nums[l];
while(l < r){
while(l < r && nums[r] <= temp) r--;
swap(nums[l],nums[r]);
while(l < r && nums[l] >= temp) l++;
swap(nums[l],nums[r]);
}
}
nums[l] = temp;
return l;
}
int search(vector<int>& nums,int l,int r,int k){
int m =partition(nums,l,r);
if(m == k-1) return nums[m];
else if(m > k-1) return search(nums,l,m-1,k);
else return search(nums,m+1,r,k);
}
int findKthLargest(vector<int>& nums, int k) {
int length = nums.size();
if(k > length) return 0;
else return search(nums,0,length-1,k);
}
4 参考文献
https://algs4.cs.princeton.edu/23quicksort/
https://blog.csdn.net/linfeng24/article/details/38429055
《算法导论》 第四版