Javascript和O(n^2)时间复杂度的排序

Javascript和O(n^2)时间复杂度的排序

O(n^2)时间复杂度的排序方法往往是入门算法的经典，在实际应用中使用的比较少，但是对于锻炼编程思维是有很大帮助的，而此类排序方法又以冒泡、选择和插入排序为典型代表，以下所有代码参考自慕课网刘波波老师的C++版本实现。

冒泡排序

这是实现起来最简单的排序算法，也是效率比较低的一类排序算法，但是很多编程语言都把它当做是否掌握了其基本语法的一个考验。它的实现就是使用两个循环遍历数组，然后在内层循环将大的数字和小的数字彼此交换位置，最终得到结果。

function bubbleSort(nums) {
    var i, j, temp;
    for (i = 0; i < nums.length - 1; i++)
        for (j = 0; j < nums.length - 1 - i; j++)
            //需要交换
            if (nums[j] > nums[j + 1]) {
                //交换
                temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
    return nums;
}

选择排序

选择排序的思想很容易理解：我假设排在最前面的就是最小的数字，第二位的次之，以此类推，然后我遍历数组找到最小的、次小的...逐个填进去就行了。

function selectSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[i]) {
                // 解构赋值交换
                [arr[i], arr[j]] = [arr[j], arr[i]];
            }
        }
    }
    return arr;
}

插入排序

插入排序的思想比较难理解些，不过算法导论类比了玩扑克时插入一张新牌的过程：即数组刚开始是有序的，每次新增一个新元素又变成一个更大的有序数组，最后得到最终的排序好的数组。

var insertSort = function(arr) {
    let len = arr.length;
    for (let i = 1; i < len; i++) {
        //把执行体的条件移到循环体里去，精简代码体积
        for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
        }
    }
    return arr;
}

//优化版本
let insertSort2 = function(arr) {
    let len = arr.length;
    for (let i = 1; i < len; i++) {
        let e = arr[i];//用e保存arr[i],减少交换次数
        let j; // j保存元素e应该插入的位置,要排序就会变，不排就是i
        for (j = i; j > 0 && arr[j - 1] > e; j--)
            arr[j] = arr[j - 1];
        arr[j] = e;
    }
    return arr;
}

后面有人提出了插入排序的改进版：希尔排序。

希尔排序

我们先把插入排序改造一下：

function insertSort(nums, step = 1) {
    for (let i = step; i < nums.length; i++) {
        let e = nums[i],
            j
        for (j = i; j >= step && e < nums[j - step]; j -= step) {
            [nums[j], nums[j - step]] = [nums[j - step], nums[j]]
        }
        nums[j] = e
    }

    return nums
}

然后创建希尔排序函数：

function shellSort(nums) {
    // 初始化最大步长：1/4/13/40...len的三分之一
    let h = 1
    while (h < parseInt(nums.length / 3)) h = 3 * h + 1

    while (h >= 1) {
        nums = insertSort(nums, h)
        //逐步缩小步长
        h = parseInt(h / 3)
    }

    return nums
}

结语

这四个排序算法里，大多数情况插入排序（希尔排序）的效率是最高的，因为它可以提前终止内层循环，而另外两个算法是需要执行完完整的两层循环过程。