快速排序原理及实现

快速排序是冒牌排序的进阶版，效率更快，实现原理比冒泡排序稍微难理解一点，耐心多多看几遍，画图可以帮助更快的理解

开始代码

function quick (arr) { const sort = (arr, left = 0, right = arr.length - 1) => { if (left >= right) return; //当左边的指针位置大于或等于右边指针的位置时，说明比较结束 let [i, j] = [left, right]; //保存左边和右边指针的起始位置，此处采用的是es6的结构赋值，不了解的请参考es6解构赋值 const middle = arr[j]; //保存数组最后一位作为基准值 while (i < j) { while (i < j && arr[i] < middle) i++; //当左边的指针小于基准值时，指针位置向右移动一位 arr[j] = arr[i]; //当左边的指针不小于基准值时，将当前指针地址的值保存至数组最后一位的地址去 while (i < j && arr[j] >= middle) j--; //当右边的指针大于或等于基准值时，指针位置向左移动一位 arr[i] = arr[j]; //当右边的指针小于基准值时，将当前指针地址的值保存至数组的第i位地址去 } arr[j] = middle; //将基准值重新保存值数组的第j位,注意当前的j已经在数组的中央位置了 sort(arr, left, j - 1); //将基准值左边的一段(0到j-1的位置)进行递归 sort(arr, j + 1, right); //将基准值右边的一段(j+1到数组最后一位的位置)进行递归 } const newArr = [...arr]; //避免函数改变外面的状态，我们采用纯函数(无副作用)的方式，直接拷贝数组 sort(newArr); //将新数组开始排序 return newArr; //返回新数组 }