前言

在开始之前, 我们先思考个问题，js中已经提供sort()方法排序，为什么我们需要快速排序算法？

1 2	let items = [3, 4, 1, 5, 2, 10, 7] console.log(items.sort((a, b) => a - b));

通过sort()方法，我们很轻松地得到想要的结果，但我们需要了解的是，原生的sort()方法在Chrome v8引擎使用的是插入排序，在Firefox以及Safari使用的合并排序，当你需要对大数据进行排序时，默认的sort()方法往往会遇到性能问题，因此我们可以考虑使用快速排序。

什么是快速排序？

快速排根据某些条件将元素划分成较小的部分，并且根据较小的部分进行排序操作。因此它比较适合与大型数据集合。简单来说，快速排序有如下几个步骤。

首先，选择数组中的一个元素作为基准数据pivot
然后，将数据其他元素与基准pivot进行比较，小于基准pivot的放在左边，大于基准pivot的放在右边。
最后，对基准pivot左右两边的元素进行同样的操作

先展示一波代码:

function swap(items, leftIndex, rightIndex) {
    let temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}


function partition(items, left, right) {
    let pivot = items[Math.floor((right + left) / 2)],
        i = left,
        j = right;
    
    while(i <= j) {
        while(items[i] < pivot) {
            i++;
        }
        while(items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }    
    }
    
   return i;
}

function quickSort(items, left, right) {
    let index;
    if (items.length < 2) return;
    
    index = partition(items, left, right);
    
    if (left < index - 1) {
       quickSort(items, left, index - 1)
    }
    if (index < right) {
        quickSort(items, index, right)
    }        
    
    return items;    
}

const result = quickSort(items, 0, items.length - 1)