JavaScript 来尝试实现一遍

排序很重要，基本很多地方都需要有它的存在，找什么第几个大的啦，将数据升序降序等等事情。

排序算法的分类

  1. 内部排序算法，是应用于少量数据的排序算法。一般仅使用于主存储器，包括冒泡排序、插入排序和快速排序。

  2. 外部排序算法，是可以应用于海量数据的排序算法。因此，可以使用于诸如硬盘驱动器和闪存盘之类的外部存储设备。归并排序是外部排序算法。

排序常用到的思路

  1. 递归/迭代

  2. 分治法

冒泡排序 --- Bubble sort

一言简之：冒泡排序的任务就是每次大循环都能实现将最小（大）的数提到最前面来，每个大循环内的小循环就是不断的比较和交换；

const bubbleSort = (arr) => {
    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);
    }
};

最坏和平均的时间复杂度都是 O(n^2) ，最佳时间复杂度是 O(n) ，空间复杂度因为冒泡排序是内部排序的关系，不需要额外的空间，其复杂度为 O(1) 。

插入排序 --- Insertion sort

插入排序，将要排序的数组分为两部分，已经排好序的，还没排序的；不断将未排序数组元素插入到已经排序数组中。

说人话，今天体育老师要排班级的队列，他将学生分成了两部分，一部分是排好的队伍，一个是散乱的一堆调皮学生；他预选在排好的队伍放进了一个最乖的学生，之后，他次次都去那堆无序散乱的人群中拉出一个调皮捣蛋的学生，将这个学生拉去和排好的队伍做身高比较，给他选个好位置，嘱咐他别随便乱动，不断重复这个行为直至把所有的学生都排进队里，就可以愉快地下课摸鱼了！

const insertionSort = (arr) => {
    for (let i = 1; i < arr.length; i++) {
        for (let j = i - 1; j > -1; j--) {
            if (arr[j + 1] < arr[j]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
}

我的理解中，插入排序和冒泡排序有很多相似的地方，都有相邻位的比较以及元素的值交换，因此插入排序的时间复杂度和空间复杂度和冒泡排序的一样。其空间复杂度为 O(1) ，最坏和平均时间复杂度为 O(n^2) ，最佳时间复杂度为 O(n) 。

选择排序 --- Selection sort

罢了罢了，直接说胡话吧；体育老师今天又有个任务要帮个班级排队伍，毕竟出了名的排队能手；体育老师今天换种方式排队列，直接说了会靠目测一次次把人群中最矮（高）的人群拉出来，不断重复直至无人可拉，之后他就下班打游戏去了！

const selectionSort = (arr) => {
    let minIndex;

    for (let i = 0; i < arr.length; i++) {
        minIndex = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[minIndex] > arr[j])
                minIndex = j;
        }

        if (minIndex !== i) {
            [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
        }
    }
}

呀，不得不说，重新认识排序，更感觉冒泡排序，插入排序，选择排序基本需要两个操作（比较，交换）；而选择排序的时间复杂度和空间复杂度也和上面两个一样的；其空间复杂度为 O(1) ，最坏和平均时间复杂度为 O(n^2) ，最佳时间复杂度为 O(n) 。

合并排序 --- Merge sort

合并排序开始就采用一种新的思路解决，就是分治法，将问题分成小块部分逐一解决；归并排序的主要概念就是对长度为 1 的数组进行排序。 因此，任务在于将数组拆分为大小为 1 的子数组，然后适当地合并它们，以便得出已排序的数组。

思路：

  1. 将数组元素拆分为单个元素。

  2. 比较各个元素并按顺序排列它们。 这会产生长度为 1 或 2 的子数组。

  3. 创建一个空数组。

  4. 比较子数组的元素并将较小的值推送到空数组。

  5. 如果您已从其中一个数组中提取了所有值，请将剩余的数组推送到新数组。

  6. 继续直到所有子数组都被覆盖并且您有一个已排序的数组。

const merge = (arr1, arr2) => {
    let mergeArr = [];

    if (arr1.length > 1) {
        let minIndex;

        for (let i = 0; i < arr1.length; i++) {
            minIndex = i;
            for (let j = i + 1; j < arr1.length; j++) {
                if (arr1[minIndex] > arr1[j])
                    minIndex = j;
            }

            if (minIndex !== i) {
                [arr1[minIndex], arr1[i]] = [arr1[i], arr1[minIndex]];
            }
        }
    }

    if (arr2.length > 1) {
        let minIndex;

        for (let i = 0; i < arr2.length; i++) {
            minIndex = i;
            for (let j = i + 1; j < arr2.length; j++) {
                if (arr2[minIndex] > arr2[j])
                    minIndex = j;
            }

            if (minIndex !== i) {
                [arr2[minIndex], arr2[i]] = [arr2[i], arr2[minIndex]];
            }
        }
    }

    let i = 0,
        j = 0;

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            mergeArr.push(arr1[i++]);
        } else
            mergeArr.push(arr2[j++]);
    }

    while (i < arr1.length)
        mergeArr.push(arr1[i++]);

    while (j < arr2.length)
        mergeArr.push(arr2[j++]);

    return mergeArr;
}

const mergeSort = (arr) => {
    if (arr.length <= 1)
        return arr;

    let mid = Math.ceil(arr.length / 2);

    let arr1 = arr.slice(0, mid);

    let arr2 = arr.slice(mid);

    let arr1_subarrays = [],
        sorted_arr1_subarrays = [];

    let arr2_subarrays = [],
        sorted_arr2_subarrays = [];

    for (let i = 0; i < arr1.length; i += 2) {
        arr1_subarrays.push(arr1.slice(i, i + 2));
    }

    for (let i = 0; i < arr2.length; i += 2) {
        arr2_subarrays.push(arr2.slice(i, i + 2));
    }

    for (let i = 0; i < arr1_subarrays.length; i += 2) {
        let result = merge(arr1_subarrays[i], arr1_subarrays[i + 1]);
        result.forEach((value) => sorted_arr1_subarrays.push(value));
    }

    for (let i = 0; i < arr2_subarrays.length; i += 2) {
        let result = merge(arr2_subarrays[i], arr2_subarrays[i + 1]);
        result.forEach((value) => sorted_arr2_subarrays.push(value));
    }

    let result = merge(sorted_arr1_subarrays, sorted_arr2_subarrays);

    return result;
}

此处的分治法，将数组先分为每两个为一组，之后将相邻数组合并起来，最终合并为一个大数组。有用到二分的思想，该算法的空间复杂度因为需要额外申请一个新数组存储中间数据，所以为 O(n) ；其最坏，最好和平均时间复杂度都为 O(n*logn) 。

快速排序 --- QuickSort

快速排序也应用了分治的思想；它的工作原理是有一个枢轴元素，它左边的元素小于它，右边的元素大于它；枢轴元素可以是数组中的任何元素。

分治思路：

  1. 选择一个枢轴元素。

  2. 将数组拆分为两个数组，左侧小于枢轴元素，右侧大于枢轴元素。

  3. 递归地执行上述步骤，直到我们有长度为 1 的子数组。组合子数组以产生一个已排序的数组。

const partition = (arr, left, right) => {
    let pivot = arr[Math.floor(left + (right - left) / 2)],
        i = left,
        j = right;

    while (i <= j) {
        while (arr[i] < pivot)
            i++;

        while (arr[j] > pivot)
            j--;

        if (i <= j) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
            j--;
        }
    }

    return i;
}

const quickSort = (arr, left, right) => {
    let index;

    if (arr.length > 1) {
        index = partition(arr, left, right);

        if (left < index - 1)
            quickSort(arr, left, index - 1);

        if (right > index)
            quickSort(arr, index, right);
    }
    return arr;
}

其最坏时间复杂度是 O(n^2) , 而其平均和最好时间复杂度以及空间复杂度都是 O(n*long) ，因为这里主要运用到了二分的套路，不断将问题拆半进行解决。

总结

JavaScript 的 sort() 方法默认使用插入排序。 这意味着在对大型数据集进行排序时不合适。 在处理大数据集时，应该考虑其他排序算法，例如归并排序，且通常，基于分而治之的排序算法会相较快些。

开发运用到排序时可以根据数据集、所需时间和可用空间找出要使用的合适排序算法。

Last modification：October 6, 2023
© Allow specification reprint
兴趣使然