>[success] # js -- 快速排序 [很不错的文章](https://juejin.im/post/6844904174014955527#heading-0) ~~~ 1.快速排序基本思想是：通过一趟排序将要排序的数据分割成独立的'两部分'，其中一部分的所有数据都比另外一部分的所有数据都要 '小'，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列 2.根据上面的概念最重要的一点是要让一组数据比另一组数据都'小'，为了做到这个，可以采用的思想方式是，找到这一组数据 中的任意一个值作为'基准'在快速排序中我们叫做'主元'，这个'主元'就会将数据分割成左右两个部分，这两个部分数据依次和'主元' 比较，最后比主元大的都在一侧，小的在一侧 ~~~  * 快排的模拟图  >[info] ## 代码实现方法 * 通用方法 ~~~ // 生成随机数数组 function randomArray(max, min, len) { let randomNum = 0 const array = [] for (let i = 0; i < len; i++) { randomNum = Math.floor((Math.random() * (max - min + 1)) + min) array.push(randomNum) } return array } // const array = randomArray(1, 10, 5) const Compare = { LESS_THAN: -1, BIGGER_THAN: 1, EQUALS: 0 }; function defaultCompare(a, b) { if (a === b) { return Compare.EQUALS; } return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN; } ~~~ >[danger] ##### 代码分析 * 这里引用的是《学习JavaScript数据结构与算法第3版》分析过程 ~~~ (1) 首先，从数组中选择一个值作为'主元（pivot）'，也就是数组中间的那个值(也可以是随机任意值)。 (2) 创建'两个指针'（引用），左边一个指向数组第一个值，右边一个指向数组最后一个值。移 动左指针直到我们找到一个比主元大的值，接着，移动右指针直到找到一个比主元小的值，然后 交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元 之前，而比主元大的值都排在主元之后。这一步叫作'划分（partition）'操作。 (3) 接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的 子数组）重复之前的两个步骤，直至数组已完全排序。 ~~~ 到这了还懵逼的话一定要读开篇分享的文章 * 先实现分化的过程 ~~~ 1.首先会创建两个指针'left','rihgt',选出'主元 piovt' 这里的主元使用数组中间元素 1.1.{1} -- 首先整个寻找过程只要两个指针只要不出现交替越位结束，也就是'直到左指针超过了右指针' 1.2.先移动左侧指针，移动的位置值和'主元'依次比较，当发现有比'主元'小的时候，开始移动右侧指针依次和'主元' 比较，当发现有比'主元'大的时候停止查找，因为我们要形成'比主元小的值都排在主元之前，而比主元大的值都排在主元之后' ,这时候正好得到两个位置处于相反地方两个角标 1.3. {4} 这时候就要相互替换位置 ~~~ ~~~ function partition(array, left, right, compareFn = defaultCompare) { const pivot = array[Math.floor((right + left)) / 2] let i = left let j = right while (i <= j) { // {1} while (compareFn(array[i], pivot) === Compare.LESS_THAN) { // {2} i++ } while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) { // {3} j-- } if (i <= j) { swap(array, i, j) //{4} i++; j-- } } return i } const array = [3, 5, 1, 6, 4, 7, 2] const partitionP = partition(array, 0, 4) console.log(partitionP) console.log(array) ~~~ * 如图  * 快排代码（还是暂时不懂） ~~~ function quickSort(array, compareFn = defaultCompare) { return quick(array, 0, array.length - 1, compareFn); }; function quick(array, left, right, compareFn) { let index; // {1} if (array.length > 1) { // {2} index = partition(array, left, right, compareFn); // {3} console.log(index, left, right, array) if (left < index - 1) { // {4} console.log(888) quick(array, left, index - 1, compareFn); // {5} } if (index < right) { // {6} quick(array, index, right, compareFn); // {7} } } return array; }; ~~~