排序

1、冒泡排序：时间复杂度O（n）

function bubbleSort(nums) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums.length - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                let temp = nums[j + 1];
                nums[j + 1] = nums[j];
                nums[j] = temp;
            }
        }
    }
    return nums;
}

2、选择排序：时间复杂度O（n）

function selectionSort(nums) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i; j < nums.length; j++) {
            if (nums[j] < nums[i]) {
                let temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
            }
        }
    }
    return nums;
}

3、插入排序：时间复杂度O（nlogn）

function insertionSort(nums) {
    for (let i = 1; i < nums.length; i++) {
        let j = i;
        let temp = nums[i];
        while (j >= 0 && temp < nums[j - 1]) {
            nums[j] = nums[j-1];
            j--;
        }
        nums[j] = temp;
    }
    return nums;
}

4、归并排序：时间复杂度O（nlogn）
采取分治思想进行排序：
步骤1：拆分数组为小数组直至长度为1；
步骤2：排序小数组；
步骤3：归并所有小数组，归并的过程也进行排序（两个有序数组排序）。

function mergeSort(nums) {
    const len = nums.length;
    if (len === 1) return nums;
    const middle = Math.floor(nums.length / 2);
    const left = nums.slice(0, middle);
    const right = nums.slice(middle);
    return mergeSortImp(mergeSort(left), mergeSort(right));
}
function mergeSortImp(left, right) {
    let i = 0;
    let j = 0;
    let result = [];
    while (i < left.length && j < right.length) {
        const value = left[i] > right[j] ? right[j++] : left[i++];
        result.push(value);
    }
    return result.concat(i !== left.length ? left.slice(i) : right.slice(j));
}

5、快速排序：时间复杂度O（nlogn）
步骤1：选取主元（一般是中间位置）；
步骤2：划分操作，移动左指针找到比主元大的值，移动右指针找到比主元小的值，然后交换它们。重复这个过程，直到左指针超过了右指针；
步骤3：对划分好的小数组重复步骤1和步骤2，直至排序完成。

function quickSort(nums){
    return quick(nums, 0, nums.length - 1);
}
function quick(nums, left, right) {
    if (nums.length <= 1) return nums;
    let index = partition(nums, left, right);
    if (left < index - 1) {
        quick(nums, left, index - 1);
    }
    if (index < right) {
        quick(nums, index, right);
    }
    return nums;
}
//选取主元并进行划分操作
function partition(nums, left, right) {
    let i = left;
    let j = right;
    let middle = Math.floor((i + j) / 2);
    let main = nums[middle];
    while (i <= j) {
        while(nums[i] < main){
            i++;
        }
        while (nums[j] > main) {
            j--;
        }
        if (i <= j) {
            let temp = nums[i];
            nums[i]=nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
    return i;
}

6、图的拓扑排序
拓扑排序是用于解决有向无环图的排序

function Node(){
  this.parentQueue = [];
  this.childQueue = [];
}
function sortTop(nodes) {
    const incoming0Queue = [];
    const sortQueue = [];
    for(let node of nodes){
        const parentQueue = node.parentQueue || [];
        node.incoming = parentQueue.length;
        if (node.incoming === 0) {
            incoming0Queue.push(node);
        }
    }
    let node;
    while (node = incoming0Queue.shift()) {
        sortQueue.push(node);
        if (!node.childQueue || node.childQueue.length === 0) continue;
        let index = 0;
        let child;
        while (child = node.childQueue[index++]) {
            child.incoming = child.incoming - 1;
            if (child.incoming === 0){
                incoming0Queue.push(child);
            }
        }
    }
    return sortQueue;
}