深入解析快速排序算法函数的实现与优化

该文章用来记录对快排的理解&＃xff0c;方便回忆

function quickSort(arr, left, right) {//left和right代表所要进行对比区间var len &＃61; arr.length,partitionIndex,left &＃61; typeof left !&＃61; &＃39;number&＃39; ? 0 : left,right &＃61; typeof right !&＃61; &＃39;number&＃39; ? len - 1 : right;//设置初始首尾下标if (left return arr;}function partition(arr, left, right) { //分区操作var pivot &＃61; left, //设定基准值&＃xff08;pivot&＃xff09;index &＃61; pivot &＃43; 1;for (var i &＃61; index; i <&＃61; right; i&＃43;&＃43;) {if (arr[i] return index - 1;//当前基准值的下标}function swap(arr, indexA, indexB) {[arr[indexA], arr[indexB]] &＃61; [arr[indexB], arr[indexA]];}// testconst arr &＃61; [9,91, 65, 10, 65, 6, 30, 8,7];console.log(quickSort(arr));


排序函数来自www.jianshu.com/p/1b4068ccd… &＃xff0c;对其中的快排做分析&＃xff0c;原作者的各种排序算法罗列值得一看&＃xff0c;并附有生动形象的图片&＃xff0c;方便理解

var quicksort &＃61; function (arr) {if (arr.length <&＃61; 1) {return arr;}var pivotIndex &＃61; Math.floor(arr.length / 2);//取一个基准值&＃xff0c;用于做参考点&＃xff08;不一定要用这个&＃xff0c;像上面&＃xff0c;以左侧做基准值&＃xff09;var pivot &＃61; arr.splice(pivotIndex, 1)[0];var left &＃61; []; var right &＃61; [];for (var i &＃61; 0; i if (arr[i] else { right.push(arr[i]); }}return quicksort(left).concat([pivot], quicksort(right));//但开了三个线处理&＃xff0c;性能上有缺陷}