快速排序作为前端排序算法面试的最常考算法之一,是必须要掌握的。现场面试的时候,会要求直接在A4纸上书写出来,不能有犹豫,所以还在等什么呢?
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>快速排序</title>
<!-- 1、快速排序思想:先找到一个基准点(一般指数组的中部),然后数组被该基准点分为两部分,依次与该基准点数据比较,如果比它小,放左边;反之,放右边。
左右分别用一个空数组去存储比较后的数据,最后递归执行上述操作,直到数组长度小于等于1。
2、特点:快速、常用。缺点是需要另外声明两个数组,浪费了内存空间资源。
3、依赖基准的选取,属于不稳定排序算法。
-->
</head>
<body>
<script type="text/javascript">
var time=0;
function sort(arr) {
// body...
if(arr.length<=1){
return arr;
}
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];//splice()返回的是含有被删除的元素的数组,删除基准数
//console.log(pivot);
var left=[];
var right=[];
for(var i=0;i<arr.length;i++){
if(arr[i]<pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return sort(left).concat(pivot,sort(right));
}
var arr=[3,1,5,7,2,4,9,6,10,8];
console.log("beforeSort:"+arr);//beforeSort:3,1,5,7,2,4,9,6,10,8
console.log("afterSort:"+sort(arr));//afterSort:1,2,3,4,5,6,7,8,9,10
</script>
</body>
</html>