- Notifications
You must be signed in to change notification settings - Fork24
Open
Description
快速排序也是分治法的应用，处理过程是由上到下的，先分区，然后再处理子问题。
快速排序通过遍历数组，将待排序元素分隔成独立的两部分，一部分记录的元素均比另一部分的元素小，则可以分别对这两部分记录的元素继续进行排序，直到排序完成。
这就需要从数组中挑选出一个元素作为基准(pivot)，然后重新排序数列，将元素比基准值小的放到基准前面，比基准值大的放到基准后面。
然后将小于基准值的子数组(left)和大于基准值的子数组(right)递归地调用 quick 方法，直到排序完成。
constquickSort=function(arr){constquick=function(arr){if(arr.length<=1)returnarrconstlen=arr.lengthconstindex=Math.floor(len>>1)constpivot=arr.splice(index,1)[0]constleft=[]constright=[]for(leti=0;i<len;i++){if(arr[i]>pivot){right.push(arr[i])}elseif(arr[i]<=pivot){left.push(arr[i])}}returnquick(left).concat([pivot],quick(right))}constresult=quick(arr)returnresult}
- 时间复杂度: O(nlogn)
- 空间复杂度: O(nlogn)
- 不稳定
Metadata
Metadata
Assignees
Labels
No labels