js 实现的快速排序

js 实现的快速排序
目前是升序排列,改成降序只需要将 arr[j] >= midarr[i] <= mid 中的 >= 和 <= 互换
算法优化:

  • 随机取基准数
  • 采用三数取中的方式取基准数
  • 多种排序算法配合 - 当数组元素比较少的时候采用插入排序
const quickSort = (arr, left, right) => {
    if (left < right) {
        // 取第一个数为基准数
        let mid = arr[left];
        let i = left;
        let j = right;
        let temp = 0;

        while (i < j) {
            // 先从 *右边* 开始找 *小于* 基准数的值
            while (i < j && arr[j] >= mid) {
                // 在 i < j 的前提下 直到找到小于基准数的值 本次循环结束
                j--;
            }
            // 再从 *左边* 开始找 *大于* 基准数的值
            while (i < j && arr[i] <= mid) {
                // 在 i < j 的前提下 直到找到大于基准数的值 本次循环结束
                i++;
            }
            // console.log(i, j);
            // 交换 - 这里 肯定是 i <= j 的,加上 i < j 的判断可以少一次无用的赋值
            if (i < j) {
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;            
            }
        }

        // 到这里的话 i = j
        arr[left] = arr[i];
        arr[i] = mid;
    
        // 再排左半边
        quickSort(arr, left, i - 1);
        // 再排右半边
        quickSort(arr, i + 1, right);
    }
}

var arr = [15, 4, 23, 32, 2, 7, 14, 24, 3, 1, 44, 51, 17];
// var arr = [153, 234, 4364, 565, 32423, 2, 5, 55, 35, 23, 24, 23, 32, 22, 27, 14, 4, 3, 1, 14];

quickSort(arr, 0, arr.length - 1);
console.log(arr);

评论