用JavaScript实现常见的排序算法

2018-02-10

##前戏

  • 复习了一些比较常见的排序算法，用JS实现，带一些实现思路。
  • 无图，无脑贴代码。。

比较排序

冒泡排序

  1. 比较相邻的元素，若第二个比第一个大，则交换位置。
  2. 对每一对相邻元素作比较，一轮交换完成后，最大的元素应该排在最后，即排序完成。
  3. 对剩余待排序元素重复步骤1~2，直到所有元素都已排序完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(paramArr) {
    const arr = paramArr.slice()
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}

选择排序

  1. 从未排序序列中选择最小的元素放在已排序序列的末尾。
  2. 重复步骤1，直到所有元素都已被放入已排序序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function selectionSort(paramArr) {
    const arr = paramArr.slice()
    for (let i = 0; i < arr.length; i++) {
        let minIndex = 0
        for (let j = 1; j < arr.length - i; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        arr.push(arr[minIndex])
        arr.splice(minIndex, 1)
    }
    return arr
}

插入排序

  1. 取出第一个元素，这个元素可以认为已经被排序。
  2. 取出下一个元素，从后向前依次对比，如果已排序元素大于新元素，则将该元素后移一位。
  3. 重复步骤2，直到找到已排序元素小于等于新元素的位置，将新元素插入。
  4. 重复步骤2~3，直到所有元素都插入完毕。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insertionSort(paramArr) {
    const arr = paramArr.slice()
    for (let i = 1; i < arr.length; i++) {
        for (let j = i; j > 0; j--) {
            if (arr[j - 1] > arr[j]) {
                const temp = arr[j]
                arr[j] = arr[j - 1]
                arr[j - 1] = temp
            } else {
                break
            }
        }
    }
    return arr
}

快速排序

  1. 在待排序元素中选择一个元素作为基准。
  2. 将所有小于基准的元素都移到基准的左边，所有大于基准的元素都移到基准的右边。操作结束后，基准就已经处在最终排序后它的位置。
  3. 对左右两个子集重复步骤1~2，直到所有的子集只剩下一个元素。

这里说一下代码细节：

  1. 将序列中最后一个数作为基准数。
  2. 用storeIndex表示移动元素放置的位置，最开始指向序列起点。
  3. 从前向后遍历，移动小于等于基准元素的元素到数组的开头，每次移动 storeIndex 自增 1。
  4. 循环结束后将storeIndex位置上的元素与基准数交换，此时一轮排序完成。
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
28
29
30
31
32
function quickSort(paramArr) {
    const swap = (arr, index1, index2) => {
        const temp = arr[index1]
        arr[index1] = arr[index2]
        arr[index2] = temp
    }

    const partition = (arr, start, end) => {
        let storeIndex = start
        const standardIndex = end
        for (let i = start; i < end; i++) {
            if (arr[i] <= arr[standardIndex]) {
                swap(arr, storeIndex, i)
                storeIndex += 1
            }
        }
        swap(arr, storeIndex, end)
        return storeIndex
    }

    const sort = (arr, start, end) => {
        if (start > end) return []
        const storeIndex = partition(arr, start, end)
        return [
            ...sort(arr, start, storeIndex - 1),
            arr[storeIndex],
            ...sort(arr, storeIndex + 1, end)
        ]
    }

    return sort(paramArr.slice(), 0, paramArr.length - 1)
}

非比较排序

计数排序

懒。。介绍就抄维基的啦。

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第i项
  3. 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
  4. 反向填充目标数组：将每个元素i放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function countingSort(arr) {
    const bucketArr = []
    const sortedArr = []

    for (let i = 0; i < arr.length - 1; i++) {
        if (!bucketArr[arr[i]]) {
            bucketArr[arr[i]] = 1
        } else {
            bucketArr[arr[i]] += 1
        }
    }

    for (let i = 0; i < bucketArr.length - 1; i++) {
        if (bucketArr[i]) {
            for (let j = 0; j < bucketArr[i]; j++) {
                sortedArr.push(i)
            }
        }
    }

    return sortedArr
}

桶排序

  1. 设置一个定量的数组当作空桶子。
  2. 寻访序列，并且把项目一个一个放到对应的桶子去。
  3. 对每个不是空的桶子进行排序。
  4. 从不是空的桶子里把项目再放回原来的序列中。

这里对每个桶中的元素使用插入排序

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
28
29
30
31
32
33
function bucketSort(arr, step) {
    const bucket = []
    const sortedArr = []

    for (let i = 0; i < arr.length; i++) {
        const index = Math.floor(arr[i] / step)
        if (!bucket[index]) {
            bucket[index] = []
            bucket[index].push(arr[i])
        } else {
            bucket[index].push(arr[i])
            for (let j = bucket[index].length - 1; j > 0; j--) {
                if (bucket[index][j - 1] > bucket[index][j]) {
                    const temp = bucket[index][j]
                    bucket[index][j] = bucket[index][j - 1]
                    bucket[index][j - 1] = temp
                } else {
                    break
                }
            }
        }
    }

    for (let i = 0; i < bucket.length; i++) {
        if (bucket[i]) {
            for (let j = 0; j < bucket[i].length; j++) {
                sortedArr.push(bucket[i][j])
            }
        }
    }

    return sortedArr
}

结语

还有一些比较常见的如基数排序、堆排序这里没有写（其实是已经忘干净了。。可能以后会再开一篇吧）

惯例贴链接：