排序算法

Leetcode番外篇之排序算法，为什么单独拿出来呢？是因为可以水一篇文章😁。

题目对应Leetcode912排序数组，以下给出的都是js版本的。

1、调库

虽然考的是算法，但是调库这种方法也是需要去学会的，别搞了半天连调库都不会啊。

sort() 方法用原地算法对数组的元素进行排序，并返回数组。默认排序顺序是在将元素转换为字符串，然后比较它们的UTF-16代码单元值序列时构建的。

返回排序后的数组。请注意，数组已原地排序，并且不进行复制。

要比较数字而非字符串，比较函数可以简单的以 a 减 b，如下的函数将会将数组升序排列

numbers.sort((a, b) => a - b);

所以对应的解法就是，这是升序排序，如果是降序排序，就b-a

var sortArray = function (nums) {
    nums.sort((a, b) => a - b);
    return nums;
};

2、冒泡

冒泡是最简单的排序，时间复杂度是O(n^2)，空间是O(1)，在Leetcode里面也能提交通过，也不知道为什么其他人说不能通过，可能Leetcode放开了限制吧。

冒泡的思想就是一边比较一边向后两两交换，将最大值冒泡到最后一位。这里内外循环的次数需要注意，外循环只需要执行n-1次就行了，内循环的长度是从1开始，循环到n-i

var sortArray = function (nums) {
    const n = nums.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 1; j < n - i; j++) {
            if (nums[j - 1] > nums[j]) {
                const tmp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = tmp;
            }
        }
    }
    return nums;
};

3、选择

1.找到数组未排序部分的最小值交换至数组未排序部分首位。
2.与冒泡排序相同，循环该过程n-1次(n为数组长度)，数组此时为升序排列。

这个选择排序比冒泡快的多了，因为没有重复的交换次数，虽然也是O(n2)，最差情况应该是一样的，但是平均下来是比冒泡牛逼一点。

var sortArray = function (nums) {
    const n = nums.length;
    for (let i = 0; i < n-1; i++) {
        let min = i;
        for (let j = i + 1; j < n; j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        if (min != i) {
            [nums[i], nums[min]] = [nums[min], nums[i]];
        }
    }
    return nums;
};

4、插入

假设一个数组，在其内部，数已经按照升序排列，此时有一个新的数a要加入数组，那么数组内大于a的数字需不断地向后腾出位置，直到a找到自己的位置，就可以将a插入该位置，此时原数组仍保持升序排列。
同理，插入排序就是将已排序部分当成一个小数组，未排序部分将一个一个插入到小数组当中，循环插入，直至排序完成。

时间复杂度也是O(n2)，空间复杂度是O(1)，别说，插入排序写法还是有点困难的，但是速度很快啊。O(n2)的骄傲啊。

var sortArray = function (nums) {
    const n = nums.length;
    for (let i = 1; i < n; i++) {
        let flag = nums[i];
        let j = i - 1;
        while (j >= 0 && flag < nums[j]) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = flag;
    }
    return nums;
};

希尔排序，时间复杂度介于O(n2)到O(nlogn)的排序算法，时间一下子快了很多，比快排还快好多，离谱就，时间直接击败了百分之百的，但是好复杂，了解一下吧。

希尔排序，即高级插入排序，是对插入排序的优化，思路如下：
1.将一个长数组按照相同的间隔h分为多个小数组，每个小数组分别进行插入排序。
2.将间隔h缩小，并继续排序，直至间隔为1。
可以证明出当间隔h=3*h+1时，希尔排序平均时间复杂度最优，推理过程此处省略。

var sortArray = function (nums) {
    const n = nums.length;
    // 直接用证明
    let h = 1;
    while (h < n / 3) {
        h = 3 * h + 1;
    }
    while (h > 0) {
        for (let i = h; i < n; i++) {
            let flag = nums[i];
            let j = i - h;
            while (j >= 0 && flag < nums[j]) {
                nums[j + h] = nums[j];
                j-=h;
            }
            nums[j + h] = flag;
        }
        h = Math.floor(h / 3);
    }
    return nums;
};

5、快速

快排的重要性应该是NO1吧，非常需要重点了解。

快速排序的主要思想是通过划分将待排序的序列分成前后两部分，其中前一部分的数据都比后一部分的数据要小，然后再递归调用函数对两部分的序列分别进行快速排序，以此使整个序列达到有序。

直接从网上抄了一个基本的，这个版本把两个合成一个了，也就是递归和分支的两个部分挪到一块了。这个里面的基准是没有排序的最后一个数，分支的顺序是先找到左边比基准大的，赋值给右边，然后再找到右边比基准的小的，赋值给左边，最后当i>=j的时候，就重新把最后的基准赋值给j。

const sortArray = (nums) => {
    const sort = (arr, left = 0, right = arr.length - 1) => {
        if (left >= right) {
            //如果左边的索引大于等于右边的索引说明整理完毕
            return;
        }
        let i = left;
        let j = right;
        const baseVal = arr[j]; // 取无序数组最后一个数为基准值
        while (i < j) {
            //把所有比基准值小的数放在左边，大的数放在右边
            while (i < j && arr[i] <= baseVal) {
                //找到一个比基准值大的数交换
                i++;
            }
            arr[j] = arr[i]; // 将较大的值放在右边，如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
            while (j > i && arr[j] >= baseVal) {
                //找到一个比基准值小的数交换
                j--;
            }
            arr[i] = arr[j]; // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
        }
        arr[j] = baseVal; // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）

        sort(arr, left, j - 1); // 将左边的无序数组重复上面的操作
        sort(arr, j + 1, right); // 将右边的无序数组重复上面的操作
    };
    sort(nums);
    return nums;
};

再找个优化一点的版本，基准不是找第一个或者最后一个，而是随机选取，为了避免最差的O(n2)情况出现，baseVal本来是index，随机在left和right中找一个，然后跟right交换，最后baseval变成交换后的最后一个值（而不是下标，为了复用变量），果然时间变快了很多，很牛逼。

const sortArray = (nums) => {
    const sort = (arr, left = 0, right = arr.length - 1) => {
        if (left >= right) {
            //如果左边的索引大于等于右边的索引说明整理完毕
            return;
        }
        let i = left;
        let j = right;
        let baseVal = Math.floor(Math.random() * (right - left + 1)) + left;
        [arr[j], arr[baseVal]] = [arr[baseVal], arr[j]];
        baseVal = arr[j];
        // const baseVal = arr[j]; // 取无序数组最后一个数为基准值
        while (i < j) {
            //把所有比基准值小的数放在左边，大的数放在右边
            while (i < j && arr[i] <= baseVal) {
                //找到一个比基准值大的数交换
                i++;
            }
            arr[j] = arr[i]; // 将较大的值放在右边，如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
            while (j > i && arr[j] >= baseVal) {
                //找到一个比基准值小的数交换
                j--;
            }
            arr[i] = arr[j]; // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
        }
        arr[j] = baseVal; // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
        sort(arr, left, j - 1); // 将左边的无序数组重复上面的操作
        sort(arr, j + 1, right); // 将右边的无序数组重复上面的操作
    };

    sort(nums);
    return nums;
};

究极快排模版，这个可是典中典了，还是采用上面的随机数方法，就是分治里面的循环换一个写法，换一个写法，有点双指针的味道，只不过同时从左边出发。

const sortArray = (nums) => {
    const sort = (arr, left = 0, right = arr.length - 1) => {
        if (left >= right) {
            //如果左边的索引大于等于右边的索引说明整理完毕
            return;
        }

        let baseIndex = Math.floor(Math.random() * (right - left + 1)) + left;
        // 随机选取left到right中的一个数字，然后和right进行交换
        swap(arr, baseIndex, right);

        // 基准就选取最后一个，也就是之前随机得到的数字
        const pivot = arr[right];
        let i = left; // i是在左边的，j是在右边的
        // 循环从left到right-1，整个过程有点像冒泡（选择？），就是把基准小的都冒泡到左边去
        for (let j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                // 因为j是大于等于i，也就是在i的右边，所以找到比基准小的arr[j]，那么就交换
                swap(arr, i, j);
                i = i + 1;
            }
        }
        // 最后交换i和right位置的数字，此时arr[i]是大于等于基准的值
        swap(arr, i, right);

        sort(arr, left, i - 1); // 将左边的无序数组重复 上面的操作
        sort(arr, i + 1, right); // 将右边的无序数组重复上面的操作
    };
    const swap = (nums, i, j) => {
        const temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    };

    sort(nums);
    return nums;
};

6、归并

归并排序利用了分治的思想来对序列进行排序。对一个长为 nn 的待排序的序列，我们将其分解成两个长度为 n/2 的子序列。每次先递归调用函数使两个子序列有序，然后我们再线性合并两个有序的子序列使整个序列有序。

分开写就是下面这样子，比较清楚，mergeSort就是递归调用了，merge就是合并两个排序完的数组了

const mergeSort = (nums, left = 0, right = nums.length - 1, res) => {
    if (left >= right) return;
    const mid = Math.floor((left + right) / 2);
    mergeSort(nums, left, mid, res);
    mergeSort(nums, mid + 1, right, res);
    merge(nums, left, right, res);
};
// merge就是整合两个已经排序完的数组，分别是[left,mid]和[mid+1,right]
const merge = (nums, left, right, res) => {
    const mid = Math.floor((left + right) / 2);
    let i = left,
        j = mid + 1,
        k = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) res[k++] = nums[i++];
        else res[k++] = nums[j++];
    }
    while (i <= mid) res[k++] = nums[i++];
    while (j <= right) res[k++] = nums[j++];
    for (let i = left; i <= right; i++) nums[i] = res[i - left];
};

var sortArray = function (nums) {
    const n = nums.length;
    const res = new Array(n).fill(0);
    mergeSort(nums, 0, n - 1, res);
    return nums;
};

合并写省事点

var sortArray = function (nums) {
    const n = nums.length;
    const res = new Array(n).fill(0);
    const mergeSort = (nums, left = 0, right = nums.length - 1) => {
        if (left >= right) return;
        const mid = Math.floor((left + right) / 2);
        mergeSort(nums, left, mid, res);
        mergeSort(nums, mid + 1, right, res);
        let i = left,
            j = mid + 1,
            k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) res[k++] = nums[i++];
            else res[k++] = nums[j++];
        }
        while (i <= mid) res[k++] = nums[i++];
        while (j <= right) res[k++] = nums[j++];
        for (let i = left; i <= right; i++) nums[i] = res[i - left];
    };
    mergeSort(nums);
    return nums;
};

7、堆

堆排序的思想就是先将待排序的序列建成大根堆，使得每个父节点的元素大于等于它的子节点。此时整个序列最大值即为堆顶元素，我们将其与末尾元素交换，使末尾元素为最大值，然后再调整堆顶元素使得剩下的 n−1 个元素仍为大根堆，再重复执行以上操作我们即能得到一个有序的序列。

算法步骤需要先初始化一个大根堆，初始化完成后，把堆首和堆尾进行交换，把堆的尺寸减1，然后再调用heapify(0)，目的是重新调整堆，把最大值再重新推到堆顶，重复步骤，直到堆的尺寸为1。

function heapify(arr, i, len) {
    // 堆调整
    // 2i+1是左节点，2i+2是右节点，最大值的下标为当前节点
    const left = 2 * i + 1,
        right = 2 * i + 2;
    let largest = i;

    // 判断子节点是否存在，并找出最大的那个
    if (left < len && arr[left] > arr[largest]) largest = left;
    if (right < len && arr[right] > arr[largest]) largest = right;

    // 如果最大值不等于父节点（就是子节点比父节点大），那么就进行交换，并进行
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest, len);
    }
}

function sortArray(nums) {
    // 先初始化，建立大顶堆
    let len = nums.length;
    for (let i = Math.floor(len / 2); i >= 0; i--) {
        heapify(nums, i, len);
    }
    for (let i = nums.length - 1; i > 0; i--) {
        // 交换根节点和末尾节点
        swap(nums, 0, i);
        len--;
        heapify(nums, 0, len);
    }
    return nums;
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

其他排序就不写了，不怎么用到，而且懒