Day20:[排序演算法]Selection Sort - 选择排序法

在了解快速排序法的概念之前要先理解partition演算法，不过单用文字叙述还是蛮抽象的，所以搭配示意图来做说明，假如现在有个阵列[2, 6, 3, 9, 1, 5]

取阵列的最後一个值5作为pivot基准值
接下来从index 0开始， 2小於5所以标记为绿色
再来是6，6大於5所以标记为橘色
轮到3，发现比5小所以把3标记为绿色，因为要把比5小的值都集中到左边，所以跟6交换位置
接下来是9，比5大标记成橘色
轮到1，比5小所以把1标记为绿色，因为比5小的值都要集中到左边，所以要跟6交换位置
最後再让支点5与最大值群组(橘色的便条纸)中的第一个值做交换，5这个数字就完成了排序
不过这时你会发现绿色的阵列并没有由小到大排序好，这边假设我们也不知道橘色阵列是否有排序好，所以接下来也对左右两个阵列，利用递回的方式持续做一样的动作。

函式内部实作为:

先将阵列里的最後一个元素定义为基准值
接下来传入起始点和终点来指定回圈跑的范围
每个遍历的值跟基准值做比较，假如比基准值小的话就跟基准值较大的群组中最左边的那个值交换位置，这个动作是要将比基准值小的数字都集中在左边

进行完一轮之後，若左群体[比基准值小的阵列]或右群体［比基准值大的阵列］的长度大於1的话，则再次呼叫quickSort函式(递回)，最後将[比基准小的阵列] 、基准值、［比基准大的阵列］依序组合起来就是排序好的阵列。

用js实作快速排序法

const partition = (arr, left, right) => {
    let pivot = arr[right];
    //用来计算有几个数字小於pivot
    let i = left - 1;
    //从最左边找到pivot的前一个停止
    for (let j = left; j <= right - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
    return i + 1;
};

const quickSort = (arr, left, right) => {
    if (left < right) {
        let sortedIndex = partition(arr, left, right);
        quickSort(arr, left, sortedIndex - 1);
        quickSort(arr, sortedIndex + 1, right);
    }
    return arr;
};

const arr = [2, 6, 3, 9, 1, 5];
quickSort(arr, 0, arr.length - 1);

//输出 [1, 2, 3, 5, 6, 9]

第二种解法比较容易理解

函式内部实作为:

先将阵列里的最後一个元素定义为基准值 5
接下来准备两个阵列(比基准值大的阵列[A] 、比基准值小的阵列[B])
跟基准值做比较，比基准值大的值就放入A阵列，反之放入B阵列

若A or B阵列长度大於1，则再次呼叫quickSort函式(递回)，最後将[比基准小的阵列] 、基准值、［比基准大的阵列］依序组合起来就是排序过後的阵列。

用js实作第二种快速排序法

const quickSort2 = (arr) => {
    if (arr.length <= 1) return arr;
    const small = [];
    const big = [];
    const pivot = arr[arr.length - 1];
    for (let i = 0; i < arr.length - 1; i++) {
        if (pivot > arr[i]) {
            small.push(arr[i]);
        } else {
            big.push(arr[i]);
        }
    }

    return [...quickSort2(small), pivot, ...quickSort2(big)];
};

const arr1 = [2, 6, 3, 9, 1, 5];
quickSort2(arr1);
//输出 [1, 2, 3, 5, 6, 9]