千锋教育web前端高频面试题视频教程，kerwin大话前端面试秘籍（附答案）

快速排序

一、排序是什

排序说白了其实就是对一个无序的列表中的所有元素按顺序排列。

二、快速排序

快速排序其实是交换排序的一种，而交换排序也就是根据那个待排序列中两个关键字的比较结果，来对换他们两个在序列中的位置。

三、快速排序思想

假如从小到大排序...

1. 在待排序的列表中选定一个元素，将这个元素作为此次排序的枢纽。正常来讲这个枢纽选首元素就好。
2. 然后通过遍历，对待排序的所有元素与此次遍历的枢纽做比较，将比这个枢纽小的元素放在左侧，比这个枢纽大的元素放在它的右侧。
3. 经过一次排序，此次排序的枢纽就已经确定了它的最终位置，此后不用在改变了。
4. 同时在一次排序后，将此次执行的待排序列分成了两个新的待排序列，通过递归，分别对这两个待排序列作为新的执行待排序列进行前几步。
5. 当递归完成时，每一个元素都在它的最终位置了，快速排序结束。

四、算法性能

• 当初始序列越接近有序，导致算法的递归层数越高，也就是执行次数越多，性能越差，
• 完全有序时最差，时间复杂度为为O(n*n)，空间复杂度为O(n)
• 反之性能最好，时间复杂度为O(n*log2(n))，空间复杂度为O(log2(n))

五、代码实现

 function quickSort(arr) {
   if (arr.length <= 1) return arr;
   const pivot = arr[0];
   const low = [],high = []; 
   for (let i = 1; i < arr.length; i++) {
     if (arr[i] < pivot) {
       low.push(arr[i]);
    } else {
       high.push(arr[i]);
    }
  }
   return quickSort(low).concat(pivot, quickSort(high));
 }