SOURCE

// sort排序
// 如果 compare(a, b) 小于 0 ，那么 a 会被排列到 b 之前；
// 如果 compare(a, b) 等于 0 ， a 和 b 的相对位置不变。备注： ECMAScript 标准并不保证这一行为，而且也不是所有浏览器都会遵守（例如 Mozilla 在 2003 年之前的版本）；
// 如果 compare(a, b) 大于 0 ， b 会被排列到 a 之前。
// compare(a, b) 必须总是对相同的输入返回相同的比较结果，否则排序的结果将是不确定的。
// function compare(a, b) {
//     if (a < b) return -1
//     if (a > b) return 1
//     if (a === b) return 0
// }

let arr = [1, 3, 9, 7, 15, 11, 13]

// // console.log(arr.sort(compare))

// console.log(arr.sort((a, b) => a - b))

// // 冒泡排序 bubbleSort
// function bubbleSort(arr) {
//     const len = arr.length;
//     for (let i=0;i<len;i++) {
//         let flag = false;
//         for (let j=0;j<len-1-i;j++) {
//             if (arr[j] > arr[j+1]) {
//                 [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
//                 flag = true;
//             }
//         }
//         if (flag === false) return arr
//     }
//     return arr
// }
// // console.log(bubbleSort(arr))

// // 选择排序 selectSort
// function selectSort(arr) {
//     const len = arr.length;
//     let minIndex
//     for (let i=0;i<len-1;i++) {
//         minIndex = i;
//         for (let j=i;j<len;j++) {
//             if (arr[minIndex] > arr[j]) {
//                 minIndex = j;
//             }
//         }
//         if (minIndex !== i) {
//             [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
//         }
//     }
//     return arr
// }
// console.log(selectSort(arr))

// // 插入排序 insertSort
// function insertSort(arr) {
//     const len = arr.length;
//     let temp;
//     for (let i=1;i<len;i++) {
//         let j = i;
//         temp = arr[i];
//         while(j>0 && temp < arr[j-1]) {
//             arr[j-1] = arr[j]
//             j--
//         }
//         arr[j] = temp;
//     }
//     return arr
// }
// console.log(insertSort(arr))

// // 归并排序 mergeSort
// function mergeSort(arr) {
//     const len = arr.length;
//     if (len <= 1) return arr;
//     // 计算中点
//     const mid = Math.floor(len/2);
//     // 左数组
//     const leftArr = mergeSort(arr.slice(0, mid));
//     // 右数组
//     const rightArr = mergeSort(arr.slice(mid, len));
//     // 合并左右数组
//     arr = mergeArr(leftArr, rightArr);
//     return arr
// }
// // 归并排序的合并数组方式 mergeArr
// function mergeArr (leftArr, rightArr) {
//     // 左右数组的初始化标识
//     let i =0, j = 0;
//     // 初始化结果数组
//     let res = [];
//     // 左右数组的长度
//     let leftLen = leftArr.length;
//     let rightLen = rightArr.length;
//     // 合并两个数组
//     while (i<leftLen && j<rightLen) {
//         if (leftArr[i] < rightArr[j]) {
//             res.push(leftArr[i]);
//             i++
//         } else {
//             res.push(rightArr[j]);
//             j++
//         }
//     }
//     // 长度不一样的则合并剩余数组
//     if (i<leftLen) {
//         return res.concat(leftArr.slice(i))
//     } else {
//         return res.concat(rightArr.slice(j))
//     }
// }
// console.log(mergeSort(arr))

// // 快速排序
// function quickSort(arr, left=0, right=arr.length-1) {
//     if (arr.length > 1) {
//         // 划分左右索引位
//         let lineIndex = partition(arr, left, right)
//         if (left < lineIndex - 1) {
//             quickSort(arr, left, lineIndex - 1)
//         }
//         if (lineIndex < right) {
//             quickSort(arr, lineIndex, right)
//         }
//     }
//     return arr
// }
// // 以基准值为轴心，划分左右子数组的过程
// function partition(arr, left, right) {
//     // 取中点
//     let pivotValue = arr[Math.floor(left + (right-left)/2)]
//     let i = left;
//     let j = right;
//     // 左右指针不越界时
//     while (i<=j) {
//         while (arr[i]<pivotValue) {
//             i++
//         }
//         while (arr[j]>pivotValue) {
//             j--
//         }
//         if (i<=j) {
//             // 交换位置
//             [arr[i], arr[j]] = [arr[j], arr[i]]
//             i++
//             j--
//         }
//     }
//     return i
// }
// console.log(quickSort(arr))

function quickSort2(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let lineIndex = Math.floor(arr.length/2);
    let middleValue = arr.splice(lineIndex, 1)[0];
    let leftArr = []
    let rightArr = []
    for (let i=0;i<arr.length;i++) {
        if (arr[i] < middleValue) {
            leftArr.push(arr[i])
        } else {
            rightArr.push(arr[i])
        }
    }
    return quickSort2(leftArr).concat([middleValue], quickSort2(rightArr));
}
console.log(quickSort2(arr))