排序

[AILINGANGEL]

冒泡排序

核心思想: nums[j]和nums[j+1]进行比较，如果nums[j]大于nums[j+1]就交换位置

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

• 时间复杂度: 两轮for循环, O(n^2)
• 空间复杂度: O(1)
• 稳定吗？只有前一个元素大于后一个元素才交换位置，因此会保证两个相等的值的先后顺序。稳定！

选择排序

核心思想:假设当前位置i前面的区间已经排好序，从剩余的区间中选择最小的元素放到当前位置i

function selectionSort(nums) {
    let len = nums.length;
    for (let i = 0; i < len - 1; i++) {
        let min = i; //记录从下标i开始到数组末尾最小元素的下标
        for (let j = i + 1; j < len; j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        [nums[i], nums[min]] = [nums[min], nums[i]]; //es6利用解构赋值交换数组中的两个元素
    }
    return nums;
}

• 时间复杂度: 对于每一个i都会遍历一次，所以时间复杂度为O(n^2)
• 空间复杂度:用局部变量min和len来存储最小值对应的下标以及数组的长度，不需要其他额外空间，所以空间复杂度为O(1)
• 稳定吗? 不稳定。比如[1,2,3,1,3,2]第一个3会和最后一个2进行交换而置于第二个3后面

插入排序

核心思想：假设当前位置j之前的区间已经排好序，从位置j-1开始和位置j对应的数字开始比较，找到nums[j]在[0, ..., j-1]中的正确位置

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

• 时间复杂度: 对于每一个元素nums[j]都要遍历之前的区间，因此时间复杂度是O(n^2)
• 空间复杂度: O(1)
• 稳定吗? 只有nums[j]小于前面的数字才会交换，不小于不交换，因此稳定

归并排序

核心思想: 将一个数组对半分成两个区间，然后对这两个区间分别排序，然后将这两个区间进行合并

function mergeSort(nums) {
    if (nums.length > 1) {
        let mid = Math.floor(nums.length / 2);
        let left = mergeSort(nums.slice(0, mid));
        let right = mergeSort(nums.slice(mid));
        return merge(left, right);
    }
    return nums;
}

function merge(nums1, nums2) {
    let i = 0;
    let j = 0;
    let ans = [];
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] <= nums2[j]) {
            ans.push(nums1[i]);
            i++;
        } else if (nums1[i] > nums2[j]) {
            ans.push(nums2[j]);
            j++;
        }
    }
    if (i < nums1.length) {
        ans.push(...nums1.slice(i));
    }
    if (j < nums2.length) {
        ans.push(...nums2.slice(j));
    }
    return ans;
}

• 时间复杂度: 每次将区间拆分成两部分，然后再合并，复杂度为O(nlogn);
• 空间复杂度：每次归并返回新数组因此空间复杂度是o(n);
• 稳定吗: 合并的时候判断条件是如果前一个数组中的元素小于等于后一个区间中对应的元素就加入到最后的结果中，这样可以保证两个相同的值在数组中本身的顺序，因此是稳定的.

快排

核心思想：找到一个标杆值,通常情况下选取数组的最后一个值作为这个pivot;然后把小于它的数放在它的左边，大于它的数放在右边，并返回这个值在数组中的正确位置。然后递归的对pivot左边的区间和右边的区间分别进行排序

function quickSort(nums, start, end) {
    if (start < end) {
        let pivotIndex = findPivotIndex(nums, start, end);
       // pivotIndex对应的值已经在正确的位置了，不需要再处理这个位置的值，注意边界条件
        quickSort(nums, start, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, end);
    }
    return nums;
}

function findPivotIndex(nums, start, end) {
    let i = start - 1; // i来维护小于pivot的值的下标
    let j = start; //j来维护大于pivot值的下标
    let pivot = nums[end];// 选取最后一个值作为pivot
    while (j < end) {
        //如果nums[j]小于等于Pivot那么就把j对应的值放到下标i的位置，否则前进
        if (nums[j] <= pivot) {  
            i++;
            [nums[i], nums[j]] = [nums[j], nums[i]];
        }
        j++;
    }
    // i+1就是pivot的正确下标,把pivot放到正确的位置上，并返回这个下标
    [nums[i + 1], nums[end]] = [nums[end], nums[i + 1]];
    return i + 1;
}

• 时间复杂度: 每次将数组分成两个区间然后分别排序，平均时间复杂度为O(nlogn)
• 空间复杂度: 在原地修改，不需要额外的空间，因此是O(1);
• 稳定吗？ 按照上述算法,nums[j]只要小于pivot就放到前面，因此稳定！

[AILINGANGEL]

合并有序数组

和归并排序中不同的地方在于合并有序数组需要在本地修改数组，而不是重新分配一个数组
本地修改nums1, 注意不当nums1没有遍历完不需要特殊处理了，因此就是在nums1上进行本地修改

var merge = function(nums1, m, nums2, n) {
    let i = m - 1;
    let j = n - 1;
    let k = m + n - 1;
    while(i > - 1 && j > -1) {
        if(nums1[i] > nums2[j]) {
            nums1[k] = nums1[i];
            i--;
        } else {
            nums1[k] = nums2[j];
            j--;
        }
        k--;
    }
    while(j > -1) {
        nums1[k] = nums2[j];
        k--;
        j--;
    }
};