算法通过村第十关-快排|白银笔记|快排实战

一个程序员一生中可能会邂逅各种各样的算法，但总有那么几种，是作为一个程序员一定会遇见且大概率需要掌握的算法。今天就来聊聊这些十分重要的“必抓！”算法吧~

文章目录

前言
数组第K大
总结

前言

这是快排中的经典算法题，但是很多人从没有对过，涉及到核心问题没搞清楚，不理解想不明白与快速排序的关系是啥？？还有好多是直到原理，但是代码写不出来，这节我们就那他练手😎

数组第K大

参考题目介绍：215. 数组中的第K个最大元素 - 力扣（LeetCode）

在这里插入图片描述

这个问题用堆解决也是不错的选择，这个我们稍后分析，我们先看看这个如何基于快速排序来处理的，这个题目出现的频率也是很高的，甚至在很多时候，面试官会直接要求你基于快速排序来解决问题。而我们要直接改造一下上面的快速排序，而不是另起炉灶，只有这样平时练习才有效果，想想怎么能用快速排序解决问题呢？我哦们还是看看这个排序序列：

我们以关键序列{26，53，48，15，13，48，32，15}看一下一次划分的过程：
在这里插入图片描述

上面圈起来的位置便是当前已经被赋值给了pivot或者其他位置，可以空出来放移动来的新元素。我们可以看到26最终被放在了属于它的位置上面，不会再变化了，而26的左右两侧可以分别再次进行排序。

这里还有一个关键的信息，我们直到26的索引值为3，也就是说递增排序之后一定是第4大的元素。这就是问题关键。既然我们直到26是第四大，那么我们找第2大，一定实在右边找。找第6大一定是再左边找（当然，如果降序的话就会翻过来），而不需要的那部分就不用关心了，这就是为什么采用快速排序可以解决。

 	 /*** 快排倒叙注意* @param nums* @param left* @param right*/public static void quicksort(int[] nums, int left, int right) {int start = left;int end = right;int pivot = nums[(start + end) >> 1];// 采用类似前序 [注意倒叙相反]while(start < end){// 大于放左边while (nums[start] > pivot){start++;}// 小于放右边while (nums[end] < pivot){end--;}// 提前退出循环  即pivot左边大于等于哨兵值，右边小于等于哨兵值if (start >= end){break;}//交换int temp = nums[start];nums[start] = nums[end];nums[end] = temp;// 如果左边值和哨兵相同  则右边移动一位if (nums[start] == pivot){end--;}if (nums[end] == pivot){start++;}}// 防止栈溢出if (start == end){start++;end--;}// 向左或者向右递归if (left < end){quicksort(nums,left,end);}if (right > start){quicksort(nums,start,right);}}