SOURCE

const array = [1,3,2,6,5,8,2,9,7,4];
//冒泡排序
function mpSort(array) {
    for(let i = 1; i < array.length; i++) {
        for(let j = 0; j < i; j++) {
            if(array[i] < array[j]) 
            [array[i], array[j]] = [array[j], array[i]]
        }
    }
    return array
}
//选择排序
function selectSort(array) {
    let index = 0;
    for(let i = 0; i < array.length - 1; i++) {
        index = i;
        for(let j = i+1; j < array.length; j++) {
            if(array[j] < array[i]) {
                index = j
            }
        }
        if(index !== i) {
            [array[index], array[i]] = [array[i], array[index]]
        }
    }
    return array
}
//插入排序
function insertSort(arr) {
    let node = null;
    for(let i = 1; i < arr.length; i++) {
        for(let j = 0; j < i; j++) {
            if(arr[i] <= arr[j]) {
                const node = arr[i];
                arr.splice(i, 1);
                arr.splice(j, 0, node);
                break
            }
        }
    }
   
    return arr
}
console.log(insertSort(array))
//快速排序
// function quickSort(array) {
//     if(array.length <= 1) return array;
//     const middle = Math.floor( array.length / 2 ), base = array.splice(middle, 1)[0];
//     const left = [], right = [];
//     array.forEach( item => {
//         if(item < base) {
//             left.push(item)
//         } else {
//             right.push(item)
//         }
//     })
//     return quickSort(left).concat(base, quickSort(right))
// }
//https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/solution/jian-zhi-offer-40-zui-xiao-de-k-ge-shu-j-9yze/
function quickSort(left, riht, arr) {
    if(left >= riht) return;
    let i = left, j = riht;
    while(i < j) {
        while(i < j && arr[j] >= arr[left]) j--;
        while(i < j && arr[i] <= arr[left]) i++;
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }
    [arr[left], arr[i]] = [arr[i], arr[left]]
   
    quickSort(left, i-1, arr);
    
    quickSort(i+1, riht, arr);
    return arr
}
//归并排序
// function MergeSort(array) {
//   let len = array.length;

//   // 当每个子序列中仅有1个元素时返回
//   if (len <= 1) {
//     return array;
//   }
//   // 将给定的列表分为两半
//   let num = Math.floor(len / 2);
//   let left = MergeSort(array.slice(0, num));
//   let right = MergeSort(array.slice(num, array.length));
//   return merge(left, right);

//   function merge(left, right) {
//     let [l, r] = [0, 0];
//     let result = [];
//     // 从 left 和 right 区域中各个取出第一个元素，比较它们的大小
//     while (l < left.length && r < right.length) {
//       // 将较小的元素添加到result中，然后从较小元素所在的区域内取出下一个元素，继续进行比较；
//       if (left[l] < right[r]) {
//         result.push(left[l]);
//         l++;
//       } else {
//         result.push(right[r]);
//         r++;
//       }
//     }
//     // 如果 left 或者 right 有一方为空，则直接将另一方的所有元素依次添加到result中
//     result = result.concat(left.slice(l, left.length));
//     result = result.concat(right.slice(r, right.length));
//     return result;
//   }
// }


// console.log(MergeSort(array))
// console.log(mpSort(array))
// console.log(selectSort(array))
// console.log(insertSort(array))
// console.log(quickSort(array))
//console.log(quickSort(0, array.length - 1, array))