Ricky.L的随笔
0%

排序算法（冒泡、选择、插入、希尔、快速、归并、堆、计数）

发表于 更新于 分类于 Disqus：

冒泡排序

一句话描述

左侧无序区域中的最大数字交换到右侧已排序区域的最左侧。

冒泡排序代码

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
class BubbleSort {
    fun sort(nums: IntArray) {
        val n = nums.size
        for (i in 0 until n) {
            // nums[0, n - 1 - i]是无序区域，初始时整个数组无序
            // nums[n - i,n - 1]是有序区域，是数组中大的数

            // 记录一趟冒泡是否有交换发生
            var isNotSwapped = true

            // 因为要比较当前和下一个数大小，所以j只能取到n - 1 - i的前一个数
            for (j in 0 until n - 1 - i) {
                // 不是升序，就要交换一下
                if (nums[j] > nums[j + 1]) {
                    // 交换
                    val tmp = nums[j + 1]
                    nums[j + 1] = nums[j]
                    nums[j] = tmp
                    // 标记有交换
                    isNotSwapped = false
                }
            }

            // 没有交换，说明无序区域已经有序，那么整个数组也是有序的了
            if (isNotSwapped) break
        }
    }
}

稳定性

冒泡排序是稳定的。

因为交换是当前数大于下一个数才会交换。

如果有x1 == x2，x1在x2左边，x1始终不会被交换到x2右边。

选择排序

一句话描述

右侧未排序区域选取一个最小的数，交换到前面已排序区域的末尾。

选择排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class SelectionSort {  
    fun sort(nums: IntArray) {  
        val n = nums.size  
  for (i in 0 until n) {  
            // s[0,i-1]为已排序区域，s[i,n-1]为未排序区域  
  // 从未排序取一个最小的放入已排序区域的末尾  
  var minIndex = i  
            for (j in i + 1 until n) {  
                if (nums[j] < nums[minIndex]) {  
                    minIndex = j  
                }  
            }  
            // 将未排序区域中最小值与已排序区域末尾的下一个位置的数字交换  
  // 已排序区域末尾的下一个位置就是i了，最小值索引是minIndex  
  val tmp = nums[minIndex]  
            nums[minIndex] = nums[i]  
            nums[i] = tmp  
        }  
    }  
}

稳定性

选择排序不稳定，因为发生了位置交换。

由于每次会在后面的未排序区域选择最小的数字与前面的已排序区域末尾元素交换，如果未排序区域交换的位置的前面有与已排序区域末尾元素相等的元素，这两个元素的相对位置就变了。

例如[2, 3, 4, 2, 1]，第一趟选择会把最小的1放到最前面，第一个2交换到最后面，这样两个2的相对顺序就变了。

如何不发生位置交换呢？

有两种做法：

  • 一个是开辟一个新数组，把最小的放到第一个位置上，把第二小的放到第二个位置上等等。空间复杂度是O(n)。
  • 一个是使用链表，空间复杂度是O(1)。

特点

交换次数比冒泡排序少，交换次数是跟数组长度呈线性关系。

直接插入排序

一句话描述

扑克牌拿牌后插牌的排序：把数组右侧未排序区域的最左侧元素插入数组左侧已排序区域中。

直接插入排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class InsertSort {  
    fun sort(nums: IntArray) {  
        val n = nums.size  
  // 初始时未排序区域共有n个数，每次向左侧已排序区域插入一个数，总共需要插入n次  
  for (i in 0 until n) {  
            // nums[0,i-1]为已排序区域  
  // nums[i,n-1]为未排序区域  
  // 从未排序区域第一个元素开始，从后往前一个个跟已排序区域数字比较，相邻两个数字顺序不对就交换，直至顺序正确  
  // 由于要比较当前数字和前一个数字的大小，所以索引j最少只能取到第2个元素位置即索引1  
  for (j in i downTo 1) {  
                // 如果相邻两个数不是升序则需要交换  
  if (nums[j] < nums[j - 1]) {  
                    // 交换元素  
  val tmp = nums[j]  
                    nums[j] = nums[j - 1]  
                    nums[j - 1] = tmp  
                    break  
  }  
            }  
        }  
    }  
}

优化

已排序区域寻找插入位置可以使用二分查找。

适用场景

适合部分有序的数组，这样比较次数就会大大减少，从而提高效率。

对于大规模乱序的数组，插入排序很慢，因为只会交换相邻的元素，元素只能一步一步的从数组的一端移动到另一端。

例如，如果是升序排序，数组最小的元素在数组末尾，那么移动到开头就要交换N-1次。如果有一个完全降序的数组，用插入排序变为升序的话，要做的事情太多了。

给定一个10万个元素的数组，部分有序，部分无序，选择哪一种排序算法最好？

用插入排序，插入排序在已排序区域寻找插入位置可以用二分法加快寻找

希尔排序

一句话描述

先大步再小步的插入排序。

大步插入排序使得用很少的交换次数让数组变得部分有序，从而在小步排序时发挥插入排序的优势，达到总体的比较和交换次数变少。

希尔排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class ShellSort {
    fun sort(nums: IntArray) {
        val n = nums.size
        var d = 1
        while (d < n / 3) {
            d = 3 * d + 1
        }
        while (d >= 1) {
            for (i in d until n) {
                for (j in i downTo d step d) {
                    if (nums[j] < nums[j - d]) {
                        val tmp = nums[j]
                        nums[j] = nums[j - d]
                        nums[j - d] = tmp
                        break
                    }
                }
            }
            d /= 3
        }
    }
}

递增序列如何选择？不同的递增序列有什么影响？

《算法（第4版）》

如何选择递增序列呢？要回答这个问题并不简单。算法的性能不仅取决于h，还取决于h 之间的数学性质，比如它们的公因子等。

有很多论文研究了各种不同的递增序列，但都无法证明某个序列是 “ 最好的” 。

算法2.3中递增序列的计算和使用都很简单，和复杂递增序列的性能接近。但可以证明复杂的序列在最坏情况下的性能要好于我们所使用的递增序列。更加优秀的递增序列有待我们去发现。

一个简单的序列选择：
从1开始，一直 d * 3 + 1，直到小于 n / 3。

希尔排序更高效的原因？

希尔排序权衡了数组的规模和有序性。

排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。

子数组部分有序的程度取决于递增序列的选择。

适用场景

在大规模乱序的情况下，希尔排序可以减少元素交换的次数，数组越大优势越大。

快速排序

一句话

选取一个轴心元素，将数组划分成比这个数小的和比这个数字大的两个子数组，分别对两个子数组递归调用划分。

快速排序代码

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
34
35
fun sort(nums: IntArray) {
    if (nums.isEmpty()) {
        return
    }
    return quickSort(nums, 0, nums.size - 1)
}

fun quickSort(nums: IntArray, low: Int, high: Int) {
    if (nums.isEmpty()) {
        return
    }
    if (low < high) {
        val pivotIndex = partition(nums, low, high)
        quickSort(nums, low, pivotIndex - 1)
        quickSort(nums, pivotIndex + 1, high)
    }
}

fun partition(nums: IntArray, low: Int, high: Int): Int {
    var start = low
    var end = high
    val pivot = nums[start]
    while (start < end) {
        while (start < end && nums[end] >= pivot) {
            end--
        }
        nums[start] = nums[end]
        while (start < end && nums[start] <= pivot) {
            start++
        }
        nums[end] = nums[start]
    }
    nums[start] = pivot
    return start
}

为什么partition()里的while判断条件里low不能等于high？

因为一开始取pivot就已经挖空了一个位置。

特点

每次划分，轴心元素就在最终排序完成后的位置上。

快排为什么是O(n log n)复杂度？

根据主定理推导。

参考： 如何证明快速排序法的平均复杂度为 O(nlogn)？ - 知乎

什么会影响时间复杂度？

用于划分数组的中枢元素的选择会影响时间复杂度，划分的左右子数组数量越接近效果越好，否则会让整个快速排序退化到O(n^2)级别。

具体怎么划分要根据数组本身的数据分布特性来决定

以下情况会变得低效：

（1）近乎有序的数列

对于一个近乎有序的数列，当直接使用第一个元素作为基准点的时候，将会导致划分的子数组大小差距太大，进而无法发挥快排划分的优势

（2）含有大量重复数据的数列

選取的數字如果是重複較多的數字，划分出的两个子数组有一边的长度会很大，因为移动指针的时候，判断条件是大于等于和小于等于枢纽元素

如何优化时间复杂度？

针对近乎有序的数组：

三数取中法

选取基准点之前我们可以拿出数列中间位置元素的值，将它和首尾的元素进行比较，之后将这三个数中的中间大的数交换到数列首位的位置，之后将这个数作为基准点，尽量减小之后的分区后左右两边的区间长度之差。

LeetCode.75.颜色分类（中等）正好就是用到这种方法。

随机交换法

选取基准点之前设计随机种子，通过随机函数得到一个在数列长度内的数，将这个随机数作为索引所指的数和第一个元素进行交换，之后将首位元素作为基准点。即随机选一个数放到首位的地方。这样一来，第一次就将最小的数交换到首位的概率是非常小的，第二次将次小的数交换到首位的概率依然非常的小。

堆排序

一句话说明

堆就是一个完全二叉树，堆排序两步走：
建堆：从最后一个非叶子节点到根结点不停的向下调整堆。
排序调整：堆顶元素与数组末尾元素交换，再向下调整堆顶元素。

堆排序代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

class HeapSort {
    fun sort(nums: IntArray) {
        // 构建最大堆
        buildHeap(nums)
        // 堆顶最大的元素与数组末尾的数字进行交换
        // 堆大小减1
        // 新的堆顶元素可能破坏最大堆性质，需要向下调整，把缩小后的堆的最大的元素放到堆顶
        // 重复如此最后堆大小缩减为0，原数组从末尾开始向前填充大的数，最后得到升序数组
        for (length in nums.size downTo 1) {
            nums.swap(0, length - 1)
            sink(nums, 1, length - 1)
        }
    }

    private fun buildHeap(nums: IntArray) {
        val n = nums.size
        // 给数组元素从1到n编号，最后一个非叶节点的编号为n/2
        // 从最后一个非叶节点开始往前不停的向下调整堆
        // 如果一个结点的左右子树已经是堆，从该结点向下调整后该结点为根结点的二叉树依然保持着堆的性质
        // 所以可以从下往上不停的向下调整
        for (parent in n / 2 downTo 1) {
            sink(nums, parent, n)
        }
    }

    /**
     * 对[nums]的第[k]个元素为根结点的子堆进行向下调整，把大的元素放到堆顶
     *
     * 要从[k]向下调整是因为[k]与孩子结点可能不满足堆性质
     * 初始时已经建立了堆，交换前我们可以认定k的左右子树都已经满足最大堆的性质，即k的左右子结点一定比它下面的所有结点值都大
     * 如果k当前比左右孩子最大的一个要小，当把k的左右孩子结点与k交换，依然满足k大于所有其孩子结点
     */
    private fun sink(nums: IntArray, k: Int, length: Int) {
        var parent = k
        // 最后一个非叶节点编号是length/2
        // parent初始时是在上层的结点，一直会往下遍历，一直遍历到最后一个非叶节点
        while (parent <= length / 2) {
            // 找出较小的孩子结点child
            var child = parent * 2
            // 如果child不是最后一个元素，对比下其相邻的孩子谁更大，取更大的孩子结点，以便接下来跟其父结点parent比较，检查是否满足最大堆的性质
            if (child < length && nums[child - 1] < nums[child]) child++
            // 因为初始已经建了最大堆，我们可以认定parent的左右子树都已经满足堆的性质
            // 如果当前parent与child也满足堆性质，则不用继续调整了
            // 这里构建的是大顶堆，要求父结点比孩子结点要大
            if (nums[parent - 1] >= nums[child - 1]) break
            // 父结点比孩子结点小，不满足最大堆性质，交换父结点和孩子结点的值，以满足最大堆性质
            nums.swap(parent - 1, child - 1)
            // 交换后，以孩子结点child为根的子堆可能不满足最大堆性质，继续向下检查调整
            parent = child
        }
    }

    /**
     * 定义数组IntArray的扩展函数swap，用以交换数组内两个位置[i]和[j]的元素
     */
    private fun IntArray.swap(i: Int, j: Int) {
        val tmp = this[i]
        this[i] = this[j]
        this[j] = tmp
    }
}

堆排序的时间复杂度也是O(n * logn)，为什么一般排序用快速排序？

因为堆是一种完全二叉树，访问的数据不在内存中连续的区域，空间访问局部性效果不太好，缓存命中率低，进而降低了程序运行速度。

快速排序会访问数组相邻的元素，空间访问局部性比较好，程序运行速度快。

归并排序

一句话说明

归并两个子数组为一个有序数组。

可以自顶向下递归进行，也可以自底向上迭代进行。

归并排序代码

自顶向下：

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
34
35
36
37
38
39
40
41
42
43
44
45

class MergeSort {
    fun sort(nums: IntArray) {
        mergeSort(nums, 0, nums.size - 1)
    }

    /**
     * 自顶向下，分而治之
     * 类似于二叉树后序遍历的写法，理解二叉树后续遍历这个递归写法就好理解对应上了
     */
    private fun mergeSort(nums: IntArray, low: Int, high: Int) {
        // 只有一个元素的时候，low与high相等，只有一个数字的子数组认定是有序的，不需要再排序了
        if (low < high) {
            val mid = low + (high - low) / 2
            mergeSort(nums, low, mid)
            mergeSort(nums, mid + 1, high)
            merge(nums, low, mid, high)
        }
    }

    /**
     * 归并两个子数组为一个有序数组，用双指针法
     */
    private fun merge(nums: IntArray, low: Int, mid: Int, high: Int) {
        val copiedNums = nums.copyOf()
        // 最终将两个子数组归并的大数组的指针
        var p = low
        // 划分的第一个（左侧）子数组的指针
        var p1 = low
        // 划分的第二个（右侧）子数组的指针
        var p2 = mid + 1
        // 以上三个指针都会从各自数组的起始位置移动到末尾位置
        // 开始遍历整个数组
        for (i in low..high) {
            when {
                // 2.当其中一个子数组已经遍历完了，即代表该子数组的元素已经全部复制到大数组，把剩下一个未遍历完的数组的剩余元素在全部复制到大数组的末尾
                p1 > mid -> nums[p++] = copiedNums[p2++]
                p2 > high -> nums[p++] = copiedNums[p1++]
                // 1.一开始会比较个子数组最前端的元素大小，把小的放到最终数组的位置
                copiedNums[p1] < copiedNums[p2] -> nums[p++] = copiedNums[p1++]
                else -> nums[p++] = copiedNums[p2++]
            }
        }
    }
}

自底向上：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class MergeSort {
    fun sort(nums: IntArray) {
        mergeSort(nums)
    }

    /**
     * 自底向上
     */
    private fun mergeSort(nums: IntArray) {
        val n = nums.size
        // 从最小的子数组开始向上归并，最小的子数组长度是1，每次向上归并后子数组大小变为原来的两倍
        var size = 1
        while (size < n) {
            // 按照子数组的大小将长度为n的数组划分为n/size个子数组
            var low = 0
            // 依次归并 n/size 个子数组
            while (low < n - size) {
                // 第一个子数组的右边界索引（包含）
                val mid = low + size - 1
                // 第二个子数组的右边界索引（包含），最后一个子数组可能只包含的元素个数较少，需要防止数组越界
                val high = min(low + 2 * size - 1, n - 1)
                // 归并两个子数组
                merge(nums, low, mid, high)
                // 每次归并2个子数组，所以下一次归并发生在第三个子数组的位置
                low += size * 2
            }
            size *= 2
        }
    }

    /**
     * 归并两个子数组为一个有序数组，用双指针法
     */
    private fun merge(nums: IntArray, low: Int, mid: Int, high: Int) {
        val copiedNums = nums.copyOf()
        // 最终将两个子数组归并的大数组的指针
        var p = low
        // 划分的第一个（左侧）子数组的指针
        var p1 = low
        // 划分的第二个（右侧）子数组的指针
        var p2 = mid + 1
        // 以上三个指针都会从各自数组的起始位置移动到末尾位置
        // 开始遍历整个数组
        for (i in low..high) {
            when {
                // 2.当其中一个子数组已经遍历完了，即代表该子数组的元素已经全部复制到大数组，把剩下一个未遍历完的数组的剩余元素在全部复制到大数组的末尾
                p1 > mid -> nums[p++] = copiedNums[p2++]
                p2 > high -> nums[p++] = copiedNums[p1++]
                // 1.一开始会比较个子数组最前端的元素大小，把小的放到最终数组的位置
                copiedNums[p1] < copiedNums[p2] -> nums[p++] = copiedNums[p1++]
                else -> nums[p++] = copiedNums[p2++]
            }
        }
    }
}

计数排序

一句话说明

  1. 记录待排序数组每个取值的个数
  2. 用一个数组累加记录有多少数是小于等于当前索引I
  3. 逆序输出

计数排序代码

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

class CountSort {
    private val w = 10000

    /**
     * [nums]取值范围在1到w
     */
    fun sort(nums: IntArray) {
        val n = nums.size
        val copied = nums.copyOf()
        val count = IntArray(w + 1) { 0 }
        // 统计每个取值有多少个
        for (num in nums) {
            count[num]++
        }
        // 累加计数
        for (i in 1..w) {
            count[i] += count[i - 1]
        }
        // 逆序遍历原数组，保持元素相对顺序不变
        for (i in n - 1 downTo 0) {
            val index = count[copied[i]] - 1
            nums[index] = copied[i]
            count[copied[i]]--
        }
    }
}

为什么最后要逆序遍历原数组？

  1. 这里必须从后向前遍历，只有这样出现重复的元素，才会保持顺序的把最后面的重复元素，永远放在最右边，从而保证排序的稳定性
  2. 如果从前向后排序，重复元素的顺序，刚好相反，所以就不是稳定的算法，但如果不关注稳定性，那么结果还是正确的

保证相同的数字还是按照原数组中的顺序，保证稳定性

比如[1,2,3,4,5,5,5]

最后从后向前遍历原数组，3个5的输出顺序还是跟原数组的顺序是一致的

如果是从前向后输出，3个5的位置正好倒过来了，因为最终排序的索引是通过计数来得到的，计数是从大到小的，所以最后相同值的索引位置的计算是从大到小的，也就是说相同值的索引位置是从后往前的，如果顺序遍历原数组，遇到几个相同的数字，会先把前面的数字先放到后面了

特点

O(n)时间复杂度

适用场景

数组取值范围是常数范围。