SOURCE

// js函数排序
let arr = [2, 3, 1, 6, 4, 0]
console.log(arr.toSorted())

// 选择排序
arr = [2, 3, 1, 6, 4, 0]
for(let i=0;i<arr.length;i++) {
    for(let j=i+1;j<arr.length;j++) {
        if(arr[i]>arr[j]){
            [arr[i], arr[j]] = [arr[j], arr[i]]
        }
    }
}
console.log(arr)

// 冒泡排序1
arr = [2, 3, 1, 6, 4, 0]
for(let i=0;i<arr.length;i++) {
    for(let j=0;j<arr.length-1-i;j++) {
        if(arr[j] > arr[j+1]) {
            [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
        }
    }
}
console.log(arr)

// 冒泡排序2
arr = [2, 3, 1, 6, 4, 0]
for(let i=0;i<arr.length;i++) {
    for(let j=arr.length-1;j>i;j--) {
        if(arr[j-1] > arr [j]) {
            [arr[j-1], arr[j]] = [arr[j], arr[j-1]]
        }
    }
}
console.log(arr)


// 插入排序
arr = [2, 3, 1, 6, 4, 0]
for(let i=0;i<arr.length;i++) {
    let pre = i-1;
    let current = arr[i];
    while(pre >= 0 && arr[pre] > current) {
        arr[pre+1] = arr[pre]
        pre--;
    }
    arr[pre+1] = current;
}
console.log(arr)

// 快排
arr = [2, 3, 1, 6, 4, 0]
function quickSort(arr) {
    if (arr.length <= 1) return arr;
    let index = Math.floor(arr.length / 2);
    let center = arr[index]
    let left = [];
    let right = [];

    for(let i=0;i<arr.length;i++) {
        if(arr[i] < center) {
            left.push(arr[i])
        }else if(arr[i] >center){
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([center], quickSort(right))
}
console.log(quickSort(arr))

// 归并排序
arr = [2, 3, 1, 6, 4, 0]
function mergeSort(arr) {
    if(arr.length <= 1) return arr;
    let index = Math.floor(arr.length / 2);
    let left  = mergeSort(arr.slice(0, index));
    let right = mergeSort(arr.slice(index, arr.length));
    return merge(left, right);
}

function merge(left, right) {
    let res = [];
    while(0 < left.length && 0 < right.length) {
        res.push(left[0] <= right[0] ? left.shift() : right.shift())
    }
    return res.concat(left, right);
}
console.log(mergeSort(arr));

// 希尔排序
arr = [2, 3, 1, 6, 4, 0]
function shellSort(arr) {
    for(let gap = parseInt(arr.length / 2);gap > 0;gap = parseInt(gap/2)) {
        for(let i=gap;i<arr.length;i++) {
            let j=i;
            let empty = arr[j];

            while(j - gap>=0 && empty < arr[j-gap]) {
                arr[j] = arr[j-gap]
                j -= gap;
            }
            arr[j] = empty;
        }
    }
    return arr;
}
console.log(shellSort(arr))

// 堆排序-非递归
arr = [2, 3, 1, 6, 4, 0]
function buildHeap(arr) {
    let len = arr.length;
    for(let i=Math.floor(len / 2); i >= 0;i--) {
        heapAjust(arr, i, len);
    }
}

function heapAjust(arr, i, len) {
    // 节点的左子节点
    let child = 2*i + 1;
    while(child < len) {
        if(child + 1 < len && arr[child] < arr[child+1]){
            child += 1;
        }

        if(arr[i] < arr[child]){
            [arr[i], arr[child]] = [arr[child], arr[i]]
            i = child;
            child = 2*i+1;
        }else{
            break
        }
    }
}

function heapSort(arr){
    buildHeap(arr);
    for(let i=arr.length-1;i>=0;i--){
        [arr[i], arr[0]] = [arr[0], arr[i]];
        heapAjust(arr, 0, i-1);
    }
    return arr;
}
console.log(heapSort(arr));

// 堆排序-递归
arr = [2, 3, 1, 6, 4, 0]
function heap(arr, i, len) {
    let left = i*2+1;
    let right = i*2+2;

    if(right >= len && left >= len) return;
    // 遍历左子树
    if(left < len) heap(arr, left, len);
    // 遍历右子树
    if(right < len) heap(arr, right, len);
    
    let max = i;

    if(left < len && arr[left] > arr[max]) max = left;
    if(right < len && arr[right] > arr[max]) max = right;
    
    if(max !== i) {
        [arr[i], arr[max]] = [arr[max], arr[i]]
    }
}

function heapSort(arr) {
    for(let i=arr.length;i>0;i--) {
        heap(arr, 0, i);
        [arr[0], arr[i-1]] = [arr[i-1], arr[0]]
    }
    return arr;
}

console.log(heapSort(arr));