likes
comments
collection

算法学习笔记 【day2】

作者站长头像
站长
· 阅读数 1
原视频链接

归并排序

思路:简单递归,先让左边变有序,再让右边变有序。最后合并两个有序数组。

相关问题:

  1. 小和问题在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。求一个给定数组的小和。
  2. 逆序对问题设有一个数组 [a1, a2, a3,... an],对于数组中任意两个元素ai,aj,若i<j,ai>aj,则说明ai和aj是一对逆序对。求一个给定数组的逆序对个数。
以上实现: https://segmentfault.com/a/11...

荷兰国旗问题

给一个数组,一个值N 将数组重新排序,将大于N的放在左边,小于N的放在右边

快速排序

思路:

  1. 从数列中挑出一个元素,称为 "基准"(pivot);
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

function jiaohuan(arr, index1, index2) {
    let temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

function quickSort(arr) {
    if(arr.length < 2) {
        return arr;
    }
    const middle = Math.floor(((0 + arr.length) / 2));
    const value = arr[middle];
    let leftflag = 0;
    let rightflag = arr.length - 1;
    let index = 0;
    while(index < rightflag + 1) {
        if(arr[index] > value) {
            jiaohuan(arr, index, rightflag)
            rightflag -= 1;
            continue;
        }
        if(arr[index] < value) {
            jiaohuan(arr, index, leftflag)
            leftflag += 1;
        }
        index += 1;
    }

    return [
        ...quickSort(arr.slice(0, leftflag)), // 小于middle的
        ...arr.slice(leftflag, rightflag + 1), // 等于middle的
        ...quickSort(arr.slice(rightflag + 1, arr.length)), // 大于middle的
    ]
}

ps 上面快排虽然写了 但不好,因为arr.slice 我估计本质上也是遍历了一遍 实际上好的实现应该类似于这种https://www.runoob.com/w3cnot...