选择，冒泡，插入，快速排序

/**
 * 选择排序
 *  [3, 1, 4, 1, 5, 9]
 *  [1, 3, 4, 1, 5, 9]
 *  原理：一个min指针，一次循环找到最小值，和min互换位置，保证最左边是最小值
 */
function selectSort(nums) {
    for (let i = 0; i < nums.length - 1; i++) {
        let min = i
        for (let j = i + 1; j< nums.length; j++) {
            if (nums[j] < nums[min]) {
                min = j   1
            }
        }
        [nums[i], nums[min]] = [nums[min], nums[i]]
    }
    return nums
}

/**
 * 冒泡算法
 * 比较两两值，一次冒泡之后最右边的值肯定是为最大的
 * 第二次冒泡，就只要针对除去最后一个值的数值进行冒泡
 * [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]
 */
function bubble_one_time(arr, j) {
    for (let i = 0; i < arr.length-j; i++) {
        const element = arr[i];
        if (arr[i] > arr[i+1]) {
            let temp
            temp = arr[i+1]
            arr[i+1] = arr[i]
            arr[i] = temp 
        }
    }
    return arr
}
function bubble_sort (arr) {
    for (let i = 0; i < arr.length; i++) {
        arr = bubble_one_time(arr, i)
    }
    return arr
}

/**
 * 插入排序
 * 从原数组一个一个遍历，将其放到新数组，但要
 * 维持新数组的序列
 */
function insertSort (arr, l, r) {
    for (let i = l + 1; i <= r; i++) {
        if (arr[i] < arr[i-1]) {
            let temp = arr[i]
            let j = i
            while (j > l && arr[j-1] > temp ) {
                arr[j] = arr[j-1]
                j--
            }
            arr[j] = temp
        }
    }
}

/**
 * 快速排序
 * 是对冒泡排序的一种改进
 * 通过一趟排序将数据分为两部分，再对这两部分
 * 分别递归排序，以此类推
 * 双向的扫描比单项扫描快
 */
function quick_sort(arr, l, r) {
    if (l < r) {
        let e = quick_one_time(arr, l, r) // e 是一次快排的分界线，以此对左右两边再进行快排
        quick_sort(arr, l, e-1)
        quick_sort(arr, e+1, r)
    }
    return arr
}   
function quick_one_time (arr,i,j) {
    // i 和 j是两个指针，初始的时候分别指向首尾
    // 设定一个基准值 初始为 arr[0]
    let pivot = arr[i]
    // 现在指针移动，
    while (i < j) {
        while(arr[j] > pivot && i < j){
            j--
        }
        arr[i] = arr[j]
        while (arr[i]< pivot && i < j) {
            i++
        }
        arr[j] = arr[i]
    }
    // 指针重叠，说明遍历完一次了
    arr[i] = pivot
    return i
}

/**
 * BFPRT算法，它和快速排序的区别仅仅是改变了pivot的取值
 * 快排中我们默认取首个为基准值
 * 在BFPRT算法中我们取五分中位数的中位数
 * 1. 将 n个元素划为 n/5 组，每组5个，至多只有一组由 n mod 5个元素组成。 
 * 2. 寻找这 n/5 个组中每一个组的中位数，这个过程可以用插入排序。 
 * 3. 对步骤2中的 n/5 个中位数，重复步骤1和步骤2，递归下去，直到剩下一个数字。
 * 4. 最终剩下的数字即为pivot，把大于它的数全放左边，小于等于它的数全放右边。 
 * 5. 判断pivot的位置与k的大小，有选择的对左边或右边递归。
 */