排序

排序

冒泡排序

  1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
  2. 对每一对相邻元素做比较。一轮结束后，最后的元素会是最大的数。
  3. 执行n-1轮，就可以完成排序

代码实现

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

选择排序

1.找到数组0-n中的最小值，将它放在第一位

2.找到数组1-n中的最小值，将它放在第二位

3.依次类推

代码

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

插入排序

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素小于已经排序元素，将已经排序元素移到下一位置，继续向前扫描，否则插入当前位置

代码实现

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

快速排序

快速排序使用分治法策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。

  1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）
  2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
  3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列进行快速排序。

代码实现

function quickSort(arr, left = 0, right = arr.length) {
    let partitionIndex;
    
    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
}

function partition(arr, left, right) {
    //设定基准值位置,可以选择任意一个，此处选择最左边的位置
    let pivot = left,
        index = pivot + 1;//比基准值小的值放入的位置
    for (let i = index; i <= right; i++) {
        // 如果比基准值小，交换。
        if (arr[i] < arr[pivot]) {
            [arr[i], arr[index]] = [arr[index], arr[i]]
            index++;
        }
    }
    // 最后交换基准值和最后一位比基准值小的数
    // 这样新的数组，以基准值为界分成小数和大数
    [arr[pivot], arr[index - 1]] = [arr[index - 1], arr[pivot]]
    return index - 1;
}

归并排序

1.分：把数组分成两半，递归子数组,进行分割操作，直到分成一个数

2.合：把两个有序子数组合并成一个有序数组

代码实现

function mergeSort(nums) {
    let len = nums.length;
    if (len <= 1) {
        return nums
    }

    let middle = len >> 1
    let left = nums.slice(0, middle);
    let right = nums.slice(middle);

    return mergeAry(mergeSort(left), mergeSort(right))
};

// 合并两个有序数组
function mergeAry(left, right) {
    let ary = []
    while (left.length && right.length) {
        if (left[0] < right[0]) {
            ary.push(left.shift())
        } else {
            ary.push(right.shift())
        }
    }
    ary.push(...left, ...right)
    return ary
}

计数排序

适合少量、数值集中的非负数排序。可实现优化以支持负数。非比较排序。

由于用来计数的数组count的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。

  1. 遍历数组nums，获取最大值max

  2. 定义数组count，长度为max+1，初始值均为0

    因为js初始化数组时可以不设置长度，可以省略上面两步。

  3. 遍历数组nums，令count[nums[i] ] ++ 。

  4. 遍历count数组，把count[i]不是0的下标值逐个放入res数组中。

代码实现

function sortArray(nums) {
    let len = nums.length
    if (len <= 1) {
        return nums
    }
    const count = []
    for (let i = 0; i < len; i++) {
        const j = nums[i]
        if (count[j]) {
            count[j]++
        } else {
            count[j] = 1
        }
    }
    const res = []
    for (let j = 0; j < count.length; j++) {
        if (count[j]) {
            while (count[j] > 0) {
                res.push(j)
                count[j]--
            }
        }
    }
    return res
};

基数排序

1.将所有待比较数值（非负整数）统一为同样的数位长度，数位较短的数前面补零。

2.从个位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数组就变成一个有序序列。

非比较排序因为不涉及比较，其基本操作的代价较小，所以在一定情况下，基数排序一般要快过基于比较的排序。

流程：

初始数组：[0, 50 , 5, 2 , 131]
补零：000 050 005 002 131

比较个位数
count = []
count[0] = [0, 50]
count[1] = [131]
count[2] = [2]
count[5] = [5]
合并：nums = [0, 50, 131, 2 , 5]

比较十位数
count=[]
count[0] = [0, 2, 5]
count[3] = [131]
count[5] = [50]
合并：nums = [0, 2, 5, 131, 50]

比较百位数
count= []
count[0] = [0, 2, 5, 50]
count[1] = [131]
合并：nums = [0, 2 ,5, 50, 131]

代码实现

function sortArray(nums) {
    let len = nums.length
    if (len <= 1) {
        return nums
    }
    // nums的最大值
    let max = Math.max.apply(null, nums)
    // max的位数，如131就是3位
    let maxDigit = 1
    while (max = Math.floor(max / 10)) {
        maxDigit++
    }
    let count = []
    let mod = 10
    let dev = 1
    for (let i = 0; i < maxDigit; i++) {
        count = []
        for (let j = 0; j < len; j++) {
            let bucket = Math.floor((nums[j] % mod) / dev)
            if (count[bucket]) {
                count[bucket].push(nums[j])
            } else {
                count[bucket] = [nums[j]]
            }
        }
        let pos = 0
        for (let j = 0; j < count.length; j++) {
            let value = null
            if (count[j]) {
                while ((value = count[j].shift()) != null) {
                    nums[pos++] = value
                }
            }
        }
        dev *= 10
        mod *= 10
    }
    return nums
};

TimSort

Array.prototype.sort

v8文档关于排序的原文链接：https://v8.dev/features/stable-sort。

以前V8的排序算法是，对于数组长度小于或者等于10的时候，采用插入排序，否则采用快速排序。

但是从 V8 v7.0 / Chrome 70 之后采用稳定的TimSort。

TimSort

时间复杂度：O(n log n)。

稳定性：稳定。

TimSort主体是归并排序，但小片段的合并中用了插入排序。用上了二分搜索等算法

利用待排序数据可能部分有序的事实，

依据待排序数据内容，动态改变排序策略——选择性进行归并以及galloping（倍增搜寻法）。

1. 分区（run）

在实际场景中，大部分的数组都是部分有序的，而TimSort就很好地利用了这一点：分区，分到的每个区都是有序的。如果分到的区是严格降序，那么就翻转(reverse)这个分区。最终得到若干个升序的分区。

如，对[1, 3, 5, 2, 4, 8, 7, 6]分区：

1, 3, 5

2, 4, 8

7, 6 --翻转--> 6, 7

2. 合并分区的顺序

两两合并分区，也就意味着要比较两个分区中的元素大小。

如果长度为1000的分区和长度为1的分区合并，把长度为1001的分区和长度为2的分区合并，最后还需要把前面合并得到的长度为1001和长度为1003的分区合并。

这显然不如先给分区长度排序，然后run1和run2合并，run1000和run1001合并。

TimSort维护了一个stack，在这个栈里，分区是按照分区长度升序存储的。

3. 合并分区

既然我们得到的每个分区都是升序的，那合并两个分区的时候可以去逐个去比较这两个分区中的元素，以此得到一个有序的分区。

这个时候，可以了解下Galloping（倍增搜寻法），即以2^n的递增，最终得到

run1[2^n-1] < run0[i] < run1[2^(n +1) - 1]。那么这样我们就知道了，run0[i]在run1中的顺序我们就锁定了run1[2n-1]与run1[2(n +1) - 1]之间，这个时候我们可以再使用二分查找高效定位run0[i]在run1中的位置。

4. 二分排序

当分区的长度较短时，相对来说二分插入排序会较快。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 排序算法（4）
    姗姗来迟的排序算法的第四篇，本介绍归并排序算法，是不是有人会问这样的问题，现在书本上学习到的排序算法都太经典了，在...
    漂流小王子阅读 240评论 0赞 1
  • 排序优化
    一、如何选择最优化的排序算法 为什选择快速排序？ 线性排序时间复杂度很低但使用场景特殊，如果要写一个通用排序函数，...
    二毛_220d阅读 451评论 0赞 7
  • 排序算法之Timesort: 最好的排序算法之一
    Timsort 是一个实际的算法，通过将组合插入和归并算法，结合现实世界中数据的特征对合并策略进行修改，最终形成一...
    keith666阅读 2,406评论 0赞 5
  • 常见排序算法
    1 前言 2 排序基础2.1 选择排序2.2 插入排序 3 高级排序算法3.1 归并排序3.1.1 插入排序与归并...
    憩在河岸上的鱼丶阅读 474评论 0赞 2
  • 第十四节-排序优化
    优化快速排序 三数取中法，九数取中法 随机法 限制递归深度 自己实现函数调用栈，手动模拟入栈出栈 举例分析排序函数...
    wean_a23e阅读 287评论 0赞 0