快速排序
2021-06-23 15:03
标签：快排 传送门 选择 哨兵 value for 算法 bsp nbsp 快速排序 上述的快速排序实现很好理解，就是每次遍历当前的arr，将比中间值小的放到left，大的放到right。这是前端通常的版本，但是这样的版本是有问题的。正常的我们说快排的时间复杂度平均和最好都是O(nlogn)，最坏情况下是O(n^2)，空间复杂度为O(nlogn)。这个代码中，空间复杂度为O(nlogn)，因为使用了临时数组，应该就地服用数组，不要临时空间，使算法的空间复杂度变为O(1)。 注：网上看到说阮版本的快排会有问题，在其中使用了splice，splice的时间复杂度为n，导致算法的复杂度达到O(n^2)，具体见（v8引擎之splice实现） 真正的快排： 其实网上看到的大部分讲快速排序的实现原理，中间关于两头的哨兵，调换位置，就是使用的就地复用的思想。避免额外的空间。 引申问题 1.为什么快速排序是不稳定的 2.快速排序的空间复杂度 上面说了，空间复杂度O(nlogn)，但是使用就地复用 3.什么时候时间复杂度变为O(n^2) 动画版的传送门 快速排序 标签：快排 传送门 选择 哨兵 value for 算法 bsp nbsp 原文地址：https://www.cnblogs.com/wuleh/p/9674000.html//思路：每次确定一个数的左边和右边，然后依次递归，直到触发停止条件
//具体：每次选择一个基准，这个基准左边的用left数组保存，右边的用right数组保存，再对左边和右边分别进行递归，直到数组的长度小于等于1
function quickSort(arr){
if(arr.length return arr
}
var [left,right,mid] = [[],[],Math.floor(arr.length/2)],
value = arr[mid]
arr.forEach((item,index)=>{
if(item
}else if(item>value){
right.push(item)
}
})
return quickSort(left).concat([value],quickSort(right))
}function quickSort(){
}
function Patition(){
}