关于javascript:算法学习笔记-day2

原视频链接

归并排序

思路：简略递归，先让右边变有序，再让左边变有序。最初合并两个有序数组。

相干问题：

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…