介绍快速排序的原理和时间复杂度，实现快速排序

本文转载请联系三分钟学习前端公众号。快速排序使用了分而治之策略的思想。所谓分而治之，顾名思义就是将一个复杂的问题分治为两个或多个相似的子问题，然后将子问题分解为更小的子问题，直到更小的子问题的可以简单求解，原问题的解就是子问题解的组合。快速排序的过程很简单，就是三步：首先从序列中选择一个数作为参考数，将所有大于这个数的数放在它的右边，所有小于或等于它的数放在它的左边（一次Quicksortpartition）然后在benchmark的左右两边重复上述操作，直到数组完全排序完毕。具体步骤如下：1.创建两个指针，分别指向数组的最左端和最右端。2.从数组中随机取出一个元素作为基准3，左指针开始向右移动，遇到比基准大的元素停止4，右指针开始向左移动，遇到大于基准的元素停止一个比基准小的元素，交换左右指针指向的元素5，重复3、4，直到左指针超过右指针，此时，比基准小的值会放在benchmark的左边，大于benchmark的值会出现在benchmark的右边6，然后在benchmark的左右两边重复上面的操作，直到数组完成排序注意如何选择这里的基准？最简单的方法是每次都选择最左边的元素作为基准：但这对于几乎已排序的序列来说并不是最好的选择，它会导致算法的性能最差。另一种方法是选择一个中间数或使用Math.random()随机选择一个数作为基准。以下代码实现使用随机数作为基准。代码实现letquickSort=(arr)=>{quick(arr,0,arr.length-1)}letquick=(arr,left,right)=>{letindexif(left{//以中间项为基准vardatum=arr[Math.floor(Math.random()*(right-left+1))+left],i=left,j=right//开始调整while(i<=j){//左指针向右移动while(arr[i]datum){j--}//交换if(i<=j){swap(arr,i,j)i+=1j-=1}}returni}//交换letswap=(arr,i,j)=>{lettemp=arr[i]arr[i]=arr[j]arr[j]=temp}//testletarr=[1,3,2,5,4]quickSort(arr)console.log(arr)//[1,2,3,4,5]//第二个最大值console.log(arr[arr.length-2])//4快速排序是从小到大排序，所以复杂度分析n-k位置的第k个最大值时间复杂度：O(nlogn)空间复杂度：O(nlogn)