快速排序
创建用于交换数组两个值的函数swap
创建quick快速排序函数，入参i为起始下标，j为末尾下标
我们将起始下标i对应的arr[i]值作为基准，声明两个哨兵，l与r分别代表左侧哨兵和右侧哨兵，初始位于起始下标和末尾下标。
r向左侧移动，寻找到第一个小于（若降序则相反）基准的值；l向右侧移动，寻找到第一个大于（若降序则相反）基准的值，找到后交换，并继续找下一对值交换，寻找条件要确保左侧哨兵和右侧哨兵没有相遇：l<r。
当哨兵相遇时，将相遇点的值与基准值交换，得到的相遇点的值为基准中心，左侧的值一定小于它，右侧的一定大于它。
将相遇点左侧与右侧继续递归，递归条件为基准中心左侧l-1下标值大于起始下标i，也就是相遇点左侧至少存在两个数，右侧同理，递归完毕，值从小到大进行排序。
//对应解释1 const swap=(arr,a,b)=>{ [arr[a],arr[b]]=[arr[b],arr[a]] } //对应解释2 const quick=(arr,i,j)=>{ //对应解释3 let l=i,r=j //对应解释4 while(l<r){ while(l<r&&arr[r]>=arr[i]) r-- while(l<r&&arr[l]<=arr[i]) l++ swap(arr,l,r) } //对应解释5 swap(arr,i,l) //对应解释6 if(l-1>i){ quick(arr,i,l-1) } if(l+1<j){ quick(arr,l+1,j) } } quick(arr,0,arr.length-1)
快速选择
- 例如寻找前k个最小的数，快速排序时左侧值会小于基准中心，因此每次找到基准中心如果基准中心：
若等于k则已经找到前k个最小值了，返回前k个即可；
若大于k，则右侧数排除，继续排序左侧即可；
若小于k，则左侧数已经在前k个最小值的范围内了，顺序无所谓，继续排序右
const swap=(arr,a,b)=>{ [arr[a],arr[b]]=[arr[b],arr[a]] } const quick=(arr,i,j)=>{ let l=i,r=j while(l<r){ while(l<r&&arr[r]>=arr[i]) r-- while(l<r&&arr[l]<=arr[i]) l++ swap(arr,l,r) } swap(arr,i,l) //对应解释 if(l===k){ return arr.slice(0,k) }else if(l>k){ return quick(arr,i,l-1) }else { return quick(arr,l+1,j) } } const res= quick(arr,0,arr.length-1)
例如寻找第k个大的数，降序排序的话快速排序时左侧值会大于基准中心，因此每次找到基准中心如果基准中心：
若等于k-1则已经找到那个第k个(arr[k-1])大的数了，返回即可；
若大于k-1，则第k大的数必定在左侧，右侧数全排除，继续排序左侧即可；
若小于k-1，则左侧数(不超过k个)是都大于第k大的数，顺序无所谓直接排除，继续排序右侧。
const swap=(arr,a,b)=>{ [arr[a],arr[b]]=[arr[b],arr[a]] } const quick=(arr,i,j)=>{ let l=i,r=j while(l<r){ while(l<r&&arr[r]>=arr[i]) r-- while(l<r&&arr[l]<=arr[i]) l++ swap(arr,l,r) } swap(arr,i,l) //对应解释 if(l===k-1){ return arr[k-1] }else if(l>k-1){ return quick(arr,i,l-1) }else { return quick(arr,l+1,j) } } const res= quick(arr,0,arr.length-1)
