JavaScript排序算法

发表于 | 分类于

参考：《数据结构与算法 JavaScript 描述》
visualgo 数据可视化

JavaScript 排序算法

排序算法的核心思想是对一组数据按照一定的顺序重新排列。重新排序时用到一组嵌套的 for 循环，其中外循环会遍历数组的每一项，内循环则用于比较元素。

冒泡排序

之所以叫冒泡排序，是因为排序时，数据会像起跑一样从数组的一端漂浮到另一端。算法在数组中移动，比较相邻的数据，当左侧大于右侧数据时将他们进行交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 1、第一轮排序之后就能将最大数放到最后，那么经过 n-1 轮，就能完成所有的排序，所以需要遍历的次数是 n-1
 * 2、内层循环中，max - i 而不是 max？ 因为没经过一轮都会讲最大数放到后面，不再需要对这些已经排序的值进行再次遍历
 * 3、为什么需要标志位，当一次遍历之后发现没有进行任何交换，说明次数数组已经完成排序，跳出循环，返回结果即可
 */

function bubbleSort(data) {
    var max = data.length - 1

    for (var i = 0; i < max; i++) {
        var done = true
        for (var j = 0; j < max - i; j++) {
            if (data[j] > data[j + 1]) {
                var temp = data[j]
                data[j] = data[j + 1]
                data[j + 1] = data[j]
                done = false
            }
        }
        if (done) break
    }
    return data
}

var testArr = [12, 34, 34, 5, 6, 7, 6579, 7569, 23.32, 234, 234]

console.log(bubbleSort(testArr))

选择排序

选择排序从数组的开头开始，将第一个元素和其他每一个元素进行比较，检查所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据便完成了排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 外层循环遍历 n-1 次
 * 内层循环，没经过一次，找出最小值的坐标，循环结束后交互外循环坐标和最小坐标元素
 * 内层循环是依次减少的
 *
 */
var example = [8, 94, 15, 88, 55, 76, 21, 39]
function selectSort(arr) {
    var len = arr.length
    var minIndex, temp

    for (var i = 0; i < len - 1; i++) {
        var minIndex = i
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }

        temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    }

    return arr
}
console.log(selectSort(example))

插入排序

插入排序有两个循环，外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及后面的那个元素进行比较。如果外循环中选中的元素比内循环中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function insertSort(arr) {
    var len = arr.length

    //数组长度为1时，不需要排序，直接返回
    if (len <= 1) return arr

    for (var i = 1; i < len; i++) {
        // tmp 是需要被插入的元素
        var tmp = arr[i]
        var j = i

        // 遍历已经排序的元素
        while (arr[j - 1] > tmp) {
            arr[j] = arr[j - 1]
            --j
        }
        arr[j] = tmp
    }
    return arr
}
console.log(insertSort([1, 45, 43, 4, 56, 7, 20, 1]))

希尔排序

希尔排序的工作原理是，通过定义一个间隔序列来小时排序过程中进行比较的元素之间有多远的间隔。我们可以动态定义间隔序列，不过对于大部分实际应用常见，算法要用到间隔序列可以提前定义好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1
    while (gap < len / 3) {
        // 动态定义间隔序列 1 4 13
        gap = gap * 3 + 1
    }
    for (gap; gap > 0; gap = Math.floor(gap / 3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i]
            for (var j = i - gap; j > 0 && arr[j] > temp; j -= gap) {
                arr[j + gap] = arr[j]
            }
            arr[j + gap] = temp
        }
    }
    return arr
}

var example = [8, 94, 15, 88, 55, 76, 21, 39]

console.log(shellSort(example))

外循环控制间隔序列的移动，也就是说，算法在第一次处理数据集时，会检查所有间隔为 4 的元素，下一次检查间隔为 1 的元素。在开始最后一次处理是时，大部分元素都将在正确的位置，算法就不必对很多元素进行交换，这也是希尔排序高效的地方。

快速排序

快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据一次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直到所有数据都是序列的。

首先要在列表中选择一个元素作为基准值 (pivot)。数据排序围绕基准值进行，将列表中小于基准值的元素移到数组的底部，将大于基准值的元素移到数组的顶部。

快速排序的算法和伪代码：

  • 选择一个基准元素，将列表分隔成两个子序列
  • 对列表重新排序，将所有小于基准值的元素放在基准值前面，所有大于基准值的元素放在基准值后面
  • 分别对较小元素的子序列和较大元素的子序列重复步骤 1 和步骤 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function qSort(arr) {
    if (arr.length == 0) return []

    var left = [] //小于基准存放数组
    var right = [] // 大于基准存放数组
    var pivot = arr[0] //基准值
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }
    return qSort(left).concat(pivot, qSort(right))
}
var a = []
for (var i = 0; i < 10; ++i) {
    a[i] = Math.floor(Math.random() * 100 + 1)
}

console.log(a)
console.log(qSort(a))