算法练习：排序

[ShannonChenCHN]

题目列表

实现几种常见的排序算法，并计算相应的时间复杂度和空间复杂度

• 时间复杂度为 O(n²) 的排序
  • 冒泡排序
  • 插入排序
  • 选择排序
• 时间复杂度为 O(nlog(n)) 的排序
  • 归并排序
  • 快速排序
• 时间复杂度为 O(n) 的排序(线性排序)
  • 桶排序
  • 计数排序
  • 基数排序
• 其他
  • 希尔排序
  • 堆排序O(nlogn)

    LeetCode

• 912. 排序数组⭐️
• 148. 排序链表（难度中等）
• 147. 对链表进行插入排序（难度中等）
• 215. 数组中的第K个最大元素（难度中等）
• 剑指 Offer 40. 最小的k个数
• 剑指 Offer 39. 数组中出现次数超过一半的数字
• 剑指 Offer 45. 把数组排成最小的数（难度中等）
• 179. 最大数（难度中等）⭐️

其他

• 合并日志文件

总结

1. 关键要掌握以下几点：
   • 几种常见的排序算法的原理和适应场景
   • 时间复杂度和空间复杂度分析
   • 重点掌握前五种排序算法的实现，尤其是快排的实现，一定要熟记，很多题目的解法都是基于 partition 函数的实现
2. 跟排序相关的常考题型主要有 Top K 问题、求第 K 大元素。
3. 各排序算法的比较

[ShannonChenCHN]

冒泡排序算法的实现和复杂度分析

2021.01.25

解法

基本思路：核心思想是通过多轮比较把大数往后移，也就是所谓的“冒泡操作”。具体步骤是每次从第一个数开始，对相邻的两个数依次进行比较，如果发现前面的数字比后面的数字大，就交换两者的位置，然后再往后继续比较，直至当前轮全部比较完，以此类推。

代码实现：

func bubbleSort<T: Comparable>(_ list: inout [T]) {
    // 最外层的 i 表示第 i 轮，也意味着当前剩余前 list.count-i-1 个未排序的元素
    for i in 0..<list.count {
        for j in 0..<list.count-i-1 {
            if list[j] > list[j+1] {
                list.swapAt(j, j+1)
            }
        }
    }
}

优化方案

当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。

优化过的代码：

func bubbleSort<T: Comparable>(_ list: inout [T]) {
    // 最外层的 i 表示第 i 轮，也意味着当前剩余前 list.count-i-1 个未排序的元素
    for i in 0..<list.count {

        var isSwapNeeded = false
        for j in 0..<list.count-i-1 {

            if list[j] > list[j+1] {
                list.swapAt(j, j+1)

                // 说明还有需要交换顺序的数据
                isSwapNeeded = true
            }
        }

        // 说明不再需要交换顺序了，剩余的部分已经完全排好序了
        if isSwapNeeded == false {
            break
        }
    }
}

测试case

var list1 = [6, 5, 4, 3, 2, 1]
bubbleSort(&list1)
print(list1)  // [1, 2, 3, 4, 5, 6]

var list2 = [3, 5, 4, 1, 2, 6]
bubbleSort(&list2)
print(list2)  // [1, 2, 3, 4, 5, 6]

var list3 = [4, 5, 6, 3, 2, 1]
bubbleSort(&list3)
print(list3)  // [1, 2, 3, 4, 5, 6]

var list4 = [3, 2]
bubbleSort(&list4)
print(list4)  // [2, 3]

var list5 = [2]
bubbleSort(&list5)
print(list5)  // [2]

var list6 = [Int]()
bubbleSort(&list6)
print(list6)  // []

复杂度分析

[ShannonChenCHN]

插入排序算法的实现和复杂度分析

2021.01.28

核心思路

首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。

对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。

解法一

思路：将数组分成已排序和未排序两个部分，依次遍历未排序的部分，每次将未排序部分的第一个元素插入到已排序中合适的位置。插入时，在已排序部分从后往前遍历，如果前面的元素比要插入的元素大就往后移，最终直到找到插入的位置。

func insertionSort<T: Comparable>(_ list: inout [T]) {
    guard list.count > 1 else {
        return
    }

    for i in 1..<list.count {
        // 从后往前遍历，如果前面的元素比要插入的元素大就往后移，最终直到找到插入的位置
        var j = i
        let itemToInsert = list[j]
        while j > 0 && list[j-1] > itemToInsert {
            list[j] = list[j-1]
            j -= 1
        }
        list[j] = itemToInsert
    }
}

解法二

思路：将数组分成已排序和未排序两个部分，依次遍历未排序的部分，每次将未排序部分的第一个元素插入到已排序中合适的位置。插入时，在已排序部分从后往前遍历，相邻的两个元素进行比较互换。

func insertionSort<T: Comparable>(_ list: inout [T]) {
    guard list.count > 1 else {
        return
    }

    for i in 1..<list.count {
        // 从后往前遍历，相邻的两个元素进行比较互换
        var j = i
        while j > 0 && list[j-1] > list[j] {
            list.swapAt(j-1, j)
            j -= 1
        }
    }
}

解法三

思路：将数组分成已排序和未排序两个部分，依次遍历未排序的部分，每次将未排序部分的第一个元素插入到已排序中合适的位置。插入时，在已排序部分从前往后遍历，如果当前元素比要插入的元素大就进行互换。

func insertionSort<T: Comparable>(_ list: inout [T]) {
    guard list.count > 1 else {
        return
    }

    for i in 1..<list.count {
        // 从前往后遍历，如果当前元素比要插入的元素大就进行互换
        for j in 0..<i {
            if list[j] > list[i] {
                list.swapAt(i, j)
            }
        }
    }
}

测试 case

var list1 = [6, 5, 4, 3, 2, 1]
insertionSort(&list1)
print(list1)  // [1, 2, 3, 4, 5, 6]

var list2 = [3, 5, 4, 1, 2, 6]
insertionSort(&list2)
print(list2)  // [1, 2, 3, 4, 5, 6]

var list3 = [ "b", "a", "d", "c", "e" ]
insertionSort(&list3)
print(list3)  // ["a", "b", "c", "d", "e"]

var list4 = [3, 2]
insertionSort(&list4)
print(list4)  // [2, 3]

var list5 = [2]
insertionSort(&list5)
print(list5)  // [2]

var list6 = [Int]()
insertionSort(&list6)
print(list6)  // []

复杂度分析

[ShannonChenCHN]

选择排序算法的实现和复杂度分析

2021.01.30

核心思路

将数组分为已排序部分和未排序部分，在未排序的元素中，找出最小的数与第一个位置的数交换，交换后未排序部分中的最小数就变成了排序部分中的最后一个元素。然后重复这个步骤，如此循环到最后一个数比较为止。

代码实现

func selectionSort<T: Comparable>(_ list: inout [T]) {
    guard list.count >= 2 else {
        return
    }

    for i in 0..<(list.count-1) { // 最后只剩一个时，不需要再“选择”出最小的了
        var lowestIndex = i
        for j in (i+1)..<list.count { // 第一个默认当做最小的了，所以不需要和自己比较
            if list[j] < list[lowestIndex] {
                lowestIndex = j
            }
        }

        if i != lowestIndex {
            list.swapAt(lowestIndex, i)
        }
    }
}

测试 case

var list1 = [6, 5, 4, 3, 2, 1]
insertionSort(&list1)
print(list1)  // [1, 2, 3, 4, 5, 6]

var list2 = [3, 5, 4, 1, 2, 6]
insertionSort(&list2)
print(list2)  // [1, 2, 3, 4, 5, 6]

var list3 = [ "b", "a", "d", "c", "e" ]
insertionSort(&list3)
print(list3)  // ["a", "b", "c", "d", "e"]

var list4 = [3, 2]
insertionSort(&list4)
print(list4)  // [2, 3]

var list5 = [2]
insertionSort(&list5)
print(list5)  // [2]

var list6 = [Int]()
insertionSort(&list6)
print(list6)  // []

复杂度分析

时间复杂度：最坏和最好的情况下都是 O(n²)，平均复杂度？？？TODO 空间复杂度：O(1)，选择排序算法是一种原地排序算法 是否是一种稳定的排序算法：不是

[ShannonChenCHN]

归并排序算法的实现和复杂度分析

2021.01.31 01:30 pm

核心思路

归并排序法应用了分而治之的思想，把待排序数组分为若干个子列表，然后对每个子列表进行排序，再把排好序的子列表合并为整体有序列表。

归并排序用的是分治思想，所以可以用递归来实现。写递归代码的技巧就是，分析得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。

归并排序的递推公式和终止条件如下：

递推公式：
let middle = (end-start)/2 + start
mergeSort(array, start, end) = merge(mergeSort(array, start, middle), mergeSort(array, middle+1, end))

终止条件：start >= end

归并排序的主流程可以用递归来实现，但是我们从上面的递推公式中可以看到，在递归执行 mergeSort 操作时，还有一个 merge 的操作，这个合并的操作是怎么实现的呢？ 其实就是合并两个相邻的有序序列，核心步骤分为三步：

• 第一步创建临时数组 tmpArray，按从小到大的顺序依次将两个有序序列中的元素拷贝到 tmpArray 中。
• 第二步将两个有序序列中其中一个序列的剩余元素拷贝到 tmpArray 中。
• 第三步将 tmpArray 中合并好的元素拷贝到原数组中对应的位置。

代码实现

func mergeSort<T: Comparable>(_ list: inout [T]) {
    guard list.count >= 2 else {
        return
    }

    // 合并两个已经排好序的子数组
    func _merge<T: Comparable>(_ list: inout [T], left: ClosedRange<Int>, right: ClosedRange<Int>) {

        var i = left.lowerBound
        var j = right.lowerBound
        var tmpList = [T]()
        while i <= left.upperBound, j <= right.upperBound {

            if list[i] <= list[j] {
                tmpList.append(list[i])
                i += 1
            } else {
                tmpList.append(list[j])
                j += 1
            }
        }

        // 将剩余的数据拷贝到临时数组tmp
        while i <= left.upperBound {
            tmpList.append(list[i])
            i += 1
        }
        while j <= right.upperBound {
            tmpList.append(list[j])
            j += 1
        }

        // 将tmp中的合并后的数据拷贝回到原数组
        for k in 0..<tmpList.count {
            list[k+left.lowerBound] = tmpList[k]
        }
    }

    func _mergeSort<T: Comparable>(_ list: inout [T], start: Int, end: Int) {
        guard start < end else {
            return
        }
        let middle = (end-start)/2 + start
        _mergeSort(&list, start: start, end: middle)
        _mergeSort(&list, start: middle+1, end: end)

        _merge(&list, left: start...middle, right: (middle+1)...end)
    }

    _mergeSort(&list, start: 0, end: list.count-1)
}

测试 case 同上面的选择排序部分。

复杂度分析

时间复杂度：最好、最坏和平均复杂度都是 O(nlog(n))，具体分析见这里。

空间复杂度：如果我们按照分析递归时间复杂度的方法，通过递推公式来求解，那整个归并过程需要的空间复杂度就是 O(nlogn)。不过，递归代码的空间复杂度并不能像时间复杂度那样累加。 因为尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

是否是一种稳定的排序算法：归并排序稳不稳定关键要看 merge() 函数，也就是两个有序子数组合并成一个有序数组的那部分代码。在合并的过程中，如果左半部分和右半部分之间有值相同的元素，那我们可以先把左半部分中的元素放入 tmp 数组，然后再把右半部分中的元素放入 tmp 数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。

[ShannonChenCHN]

快速排序算法的实现和复杂度分析

2021.01.31 03:40 pm~05:30pm

一、核心思路

跟归并排序类似，快速排序采用的也是分而治之的思想。先选择一个基准元素(pivot)，通常选择第一个元素(或者最后一个元素或者中间元素，具体取决于所选的分割策略)，通过一趟扫描，将待排序列分成三部分，比基准元素小的，比基准元素大的，基准元素本身(或者是跟基准元素一样大的子序列)，然后再用同样的方法对划分好的子序列递归地进行划分排序，直到不能再分为止，最终得到的就是一个排好序的数组。

跟归并排序一样，我们也可以用递推公式来将上面的过程写出来：

 递推公式：
 quickSort(array, first, last) = quickSort(array, first, pivotIndex-1) + quickSort(array, pivotIndex+1, last)

 终止条件：
first >= last

Lomuto 分割策略：

1. 取最后一个元素作为枢纽元
2. 从第一个元素开始，依次比较，把比 pivot 小的或者相等的元素依次放到前面

3. 然后再把 pivot 放到“中间”来，保证后面的都是比它大的元素

   
   图中的 low 代表下面代码中的 first，high 代表 last，p 代表 pivotIndex
   
   [| 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]   pivot = 8
    low                                      high
    p
    i
   
   [| 10 | 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]       将 0 和 10 互换
   low                                        high
   p
       i
   
   [ 0 | 10 | 3, 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]       将 3 和 10 互换
   low                                         high
      p
           i
   
   [ 0, 3 | 10 | 9, 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]       9 比 8 大，不需要和 10 互换
   low                                         high
         p
             i
   
   [ 0, 3 | 10, 9 | 2, 14, 26, 27, 1, 5, 8, -1 | 8 ]       将 2 和 10 互换
   low                                         high
         p
                 i
   
   以此类推，直到把比枢纽元小的都放到最前面来
   
   [ 0, 3, 2, 1, 5, 8, -1 | 27, 9, 10, 14, 26 | 8 ]
   low                                        high
                         p                   i
   
   最后再将枢纽元与中间的元素交换位置
   
   [ 0, 3, 2, 1, 5, 8, -1 | 8 | 9, 10, 14, 26, 27 ]    pivotIndex = 7
   low                                       high
                         p                  i
   
   然后再接着下一回合的分割，直到最小单元为 1

二、代码实现(Lomuto 分割策略)

func quickSort<T: Comparable>(_ list: inout [T]) {
    guard list.count >= 2 else {
        return
    }

    func _partition<T: Comparable>(_ list: inout [T], first: Int, last: Int) -> Int {

        let pivot = list[last] // pivot 取最后一个元素
        var pivotIndex = first // 比 pivot 小的还没有找到，所以从 first 开始
        for i in first...last {
            if list[i] < pivot {
                list.swapAt(pivotIndex, i)
                pivotIndex += 1
            }
        }
        list.swapAt(pivotIndex, last)

        return pivotIndex
    }

    func _quickSort<T: Comparable>(_ list: inout [T], first: Int, last: Int) {
        guard first < last else {
            return
        }

        let pivotIndex = _partition(&list, first: first, last: last)
        _quickSort(&list, first: first, last: pivotIndex-1)
        _quickSort(&list, first: pivotIndex+1, last: last)
    }
    return _quickSort(&list, first: 0, last: list.count-1);
}

其他几种实现方式见：https://github.com/ShannonChenCHN/algorithm-and-data-structure/blob/master/Algorithm/Sorting/QuickSort.playground/Contents.swift

三、测试 case

var list1 = [6, 5, 4, 3, 2, 1]
quickSort(&list1)
print(list1)  // [1, 2, 3, 4, 5, 6]

var list2 = [8, 5, 10, 2, 3, 6, 1, 5]
quickSort(&list2)
print(list2)  // [1, 2, 3, 5, 5, 6, 8, 10]

var list3 = [ "b", "a", "d", "c", "e" ]
quickSort(&list3)
print(list3)  // ["a", "b", "c", "d", "e"]

var list4 = [3, 2]
quickSort(&list4)
print(list4)  // [2, 3]

var list5 = [2]
quickSort(&list5)
print(list5)  // [2]

var list6 = [Int]()
quickSort(&list6)
print(list6)  // []

var list7 = [1, 2, 3, 4, 5, 6]
quickSort(&list7)
print(list7)  // [1, 2, 3, 4, 5, 6]

四、复杂度分析

时间复杂度：如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式跟归并是相同的。所以，快排最好情况的时间复杂度也是 O(nlogn)。

最坏的情况是，数组中的数据原来已经是有序的了，比如 [1，3，5，6，8]。如果我们每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。我们需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素，这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n²)。

平均时间复杂度 TODO

空间复杂度：O(1)

是否是一种稳定的排序算法：因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 [6，8，7，6，3，5，9，4]，在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。

五、快速排序和归并排序的比较

快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢？

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。

归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

六、快排算法优化

如果数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数据，那快速排序算法就会变得非常糟糕，时间复杂度就会退化为 O(n²)。实际上，这种 O(n²) 时间复杂度出现的主要原因还是因为我们分区点选得不够合理。

最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。

两个比较常用、比较简单的分区算法：

• 三数取中法
• 随机法

[ShannonChenCHN]

215. 数组中的第K个最大元素（难度中等）

注：极客时间的专栏文章中也讲到了这个题目

2021.01.31 07:00pm~09:00pm

参考题解： https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/60294/Solution-explained

解法一：基于快速排序的选择方法

思路：借助选择排序中选取 pivot 分割数组的方式，将数组分为两部分，大于 pivot 的和小于 pivot 的：

• 如果 pivot 对应的 index 正好是第 k 大元素的 index，说明找到了第 k 大元素
• 如果 pivot 对应的 index 比第 k 大元素的 index 要大，说明第 k 大元素在左半部分，再继续重复上面的过程
• 如果 pivot 对应的 index 比第 k 大元素的 index 要小，说明第 k 大元素在右半部分，再继续重复上面的过程

粗糙版实现：

• 时间复杂度：最好 O(n)，最坏 O(n^2)
• 空间复杂度：O(1)

class Solution {
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        guard nums.count > 1 else {
            return nums.first!
        }

        let kthIdx = nums.count - k
        var nums = nums

        var left = 0
        var right = nums.count - 1
        while left < right {
            let pivotIdx = partition(&nums, left, right)
            if pivotIdx > kthIdx {
                right = pivotIdx - 1
            } else if pivotIdx < kthIdx {
                left = pivotIdx + 1
            } else {
                break
            }
        }
        return nums[kthIdx]
    }

    func partition(_ nums: inout [Int], _ left: Int, _ right: Int) -> Int {
        let pivot = nums[right]
        var pivotIdx = left  // 起始时还没有比 pivot 小的元素，所以赋值为 left
        for i in left...right {
            if pivot > nums[i] {
                nums.swapAt(pivotIdx, i)
                pivotIdx += 1
            }
        }

        nums.swapAt(pivotIdx, right)
        return pivotIdx
    }
}

优化版（随机选取一个元素作为 pivot）：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

• func partition(_ nums: inout [Int], _ left: Int, _ right: Int) -> Int {
      // 随机选取一个元素作为 pivot
      let randomIdx = Int.random(in: left...right)
      nums.swapAt(randomIdx, right)
  
      let pivot = nums[right]
      var pivotIdx = left  // 起始时还没有比 pivot 小的元素，所以赋值为 left
      for i in left...right {
          if pivot > nums[i] {
              nums.swapAt(pivotIdx, i)
              pivotIdx += 1
          }
      }
  
      nums.swapAt(pivotIdx, right)
      return pivotIdx
  }

解法二：基于堆排序的选择方法

TODO

[ShannonChenCHN]

148. 排序链表（难度中等）

解法一部分 2021.02.01, 2021.02.06 04:00 pm ~ 05:30pm 解法二部分 2021.02.06 05:30 pm ~ 09:00pm

考察点：链表、归并排序、递归

测试 case

let list1 = ListNode(3, ListNode(7, ListNode(1, ListNode(4, ListNode(8, ListNode(6, ListNode(5, ListNode(2))))))))
print(Solution().sortList(list1)!) // [1, 2, 3, 4, 5, 6, 7, 8]

let list2 = ListNode(3, ListNode(7, ListNode(1)))
print(Solution().sortList(list2)!) // [1, 3, 7]

let list3 = ListNode(7, ListNode(1))
print(Solution().sortList(list3)!) // [1, 7]

分析

题目的进阶问题要求达到 O(nlog n) 的时间复杂度和 O(1) 的空间复杂度，时间复杂度是 O(nlogn) 的排序算法包括归并排序、堆排序和快速排序，而最适合链表的排序算法是归并排序。

虽然快速排序也很高效，但是快速排序的最差时间复杂度是 O(n²)。而且，快速排序的一些改良版本（比如 randomized quicksort）也不适合链表的排序，因为链表不能像数组那样支持随机访问，随机访问链表中的一个元素需要从头结点开始查找，这样随机访问的时间复杂度也就不是 O(1) 了。 综上，如果在链表中使用快速排序，则只能选取头结点作为 pivot，这样的话最差情况下时间复杂度就变成了 O(n²)。

解法一： 自顶向下归并排序(递归)

思路：基于归并排序的思路，首先将链表分成左右两半，然后再对将排好序的子链表进行合并，就得到了排好序的链表。

• 如何将链表分成两部分：参考 876. 求链表的中间结点 的做法，用快慢指针找到中点
• 子链表怎么排序：重复上面的过程，分成两半->排序->再分成两半...，一直重复这个过程，直到不能不能再分，然后再合并
• 子链表怎么合并：可以参考 21. 合并两个有序链表 的做法 时间复杂度：O(nlogn) 空间复杂度：因为使用了递归实现，考虑到递归调用的栈空间，所以自顶向下归并排序的空间复杂度是 O(logn)

参考题解：

• https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/
• https://leetcode.com/problems/sort-list/solution/

class Solution {
    func sortList(_ head: ListNode?) -> ListNode? {
        // 至少要有两个节点
        guard head?.next != nil else {
            return head
        }

        // 分成两部分：用快慢指针找到中点
        var slow: ListNode? = ListNode(0, head)
        var fast: ListNode? = ListNode(0, head)
        while fast?.next?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        let right = slow?.next
        slow?.next = nil
        let left = head

        // 排序子序列并合并
        let sortedLeft = sortList(left)
        let sortedRight = sortList(right)
        return merge(sortedLeft, sortedRight)
    }

    func merge(_ left: ListNode?, _ right: ListNode?) -> ListNode? {

        var left: ListNode? = left
        var right: ListNode? = right
        let dummy: ListNode? = ListNode(0, nil)
        var newList: ListNode? = dummy

        while left != nil, right != nil {
            if left!.val <= right!.val {
                newList?.next = left
                left = left?.next
            } else {
                newList?.next = right
                right = right?.next
            }
            newList = newList?.next
        }

        if left != nil {
            newList?.next = left
        }

        if right != nil {
            newList?.next = right
        }

        return dummy?.next
    }
}

解法二：自底向上归并排序(迭代法)

难度偏高，没做出来。。。

思路：从前到后，先将左右相邻的 2 个元素进行归并排序，然后再将相邻的 4 个元素进行归并排序，以此类推，直到整个链表都已经排序好了。 时间复杂度：O(nlogn) 空间复杂度：O(1)

参考题解：

• https://leetcode.com/problems/sort-list/discuss/46712/Bottom-to-up(not-recurring)-with-o(1)-space-complextity-and-o(nlgn)-time-complextity
• 图解见 https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/

class Solution {
    func sortList(_ head: ListNode?) -> ListNode? {
        // 至少要有两个节点
        guard head?.next != nil else {
            return head
        }

        // 计算长度
        var length = 0
        var temp = head
        while temp != nil {
            length += 1
            temp = temp?.next
        }

        // 1. 最外层的循环表示每一轮对应的子链表的跨度：1，2，4，8，16..<length
        // 2. 按照当次的跨度拆分子链表，得到 left 和 right
        // 3. 再将 left，right 和 prve 合并
        // 4. 再重复步骤2和步骤3
        let dummy = ListNode(0, head)
        var step = 1
        while step < length {
            // 每一轮从头开始
            var prev: ListNode = dummy
            var cur: ListNode? = dummy.next
            while cur != nil {
                let left = cur
                let right = getHeadOfNextSublist(from: left, step) // 获取 right 部分的头结点，并切断 left 和 right
                cur = getHeadOfNextSublist(from: right, step) // 切断 right 和后面剩下的部分
                prev = merge(left, right, prev)
            }

            step <<= 1
        }

        return dummy.next
    }

    /// 获取下一段子链表的头结点，并切断该头节点与前驱结点的连接
    func getHeadOfNextSublist(from head: ListNode?, _ step: Int) -> ListNode? {
        var cur = head
        for _ in 1..<step {
            if cur?.next != nil {
                cur = cur?.next
            }
        }
        let right = cur?.next
        cur?.next = nil // 切断子链表之间的连接
        return right
    }

    /// 将 prev，left 和 right 合并并返回尾结点作为下一次的 prev 节点
    func merge(_ left: ListNode?, _ right: ListNode?, _ prev: ListNode) -> ListNode {

        var left: ListNode? = left
        var right: ListNode? = right
        var cur: ListNode = prev

        while left != nil, right != nil {
            if left!.val <= right!.val {
                cur.next = left
                left = left?.next
            } else {
                cur.next = right
                right = right?.next
            }
            cur = cur.next!
        }

        if left != nil {
            cur.next = left
        }

        if right != nil {
            cur.next = right
        }

        while cur.next != nil {
            cur = cur.next!
        }

        return cur
    }
}

[ShannonChenCHN]

147. 对链表进行插入排序

2021.02.13 06:45 pm~09:00pm

测试 case

let list1 = ListNode(3, ListNode(7, ListNode(1, ListNode(4, ListNode(8, ListNode(6, ListNode(5, ListNode(2))))))))
print(Solution().insertionSortList(list1)!)

let list2 = ListNode(3, ListNode(7, ListNode(1)))
print(Solution().insertionSortList(list2)!)

let list3 = ListNode(7, ListNode(1))
print(Solution().insertionSortList(list3)!)

解法

思路：链表不同于数组，链表的插入节点和删除节点操作不需要移动其他元素，但是查找的时间复杂度为 O(n)。 所以链表的插入排序也可以分为“找出插入的位置”和“插入节点”两步。但是其中需要注意的地方是，因为我们在查找“插入位置”时其实是在找第一个比插入节点大的节点，所以考虑到插入节点比已排序部分所有节点都要大的情况，需要借助一个 tailOfSorted 变量来记录。 时间复杂度：O(n²)，n 为链表的长度。因为首先我们需要遍历整个链表，而插入操作最坏的情况是，每次都要插入到已排序部分最后一个节点前，所以最坏情况下累加的耗时就变成了 n(n+1)/2，因此，总的时间复杂度就是O(n²)。

空间复杂度：O(1)

参考题解：https://leetcode-cn.com/problems/insertion-sort-list/solution/dui-lian-biao-jin-xing-cha-ru-pai-xu-by-leetcode-s/

func insertionSortList(_ head: ListNode?) -> ListNode? {
        guard head != nil else {
            return head;
        }

        let dummy = ListNode(0, head)
        var curr = head!.next // 待插入的节点
        var tailOfSorted = head // 已排序部分的尾节点
        while curr != nil {
            // 如果当前节点比已排序部分尾节点还要大，那就不需要排序了，相当于不需要插入操作了
            if tailOfSorted!.val <= curr!.val {
                tailOfSorted = curr
            } else {
                // 找出插入的位置
                var prev = dummy
                while prev.next != nil, prev.next!.val <= curr!.val {
                    prev = prev.next!
                }

                // 插入操作
                tailOfSorted?.next = curr?.next
                curr?.next = prev.next
                prev.next = curr
            }
            curr = tailOfSorted?.next
        }
        return dummy.next
    }

[ShannonChenCHN]

剑指 Offer 40. 最小的k个数

解法二：2021.02.14 07:00 pm~08:05 pm

参考题解：

• https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/
• https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/tu-jie-top-k-wen-ti-de-liang-chong-jie-fa-you-lie-/
• https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/wei-ruan-mian-shi-jiao-xun-x-by-jerry_nju/

测试 case

输入：[2,1,7,5], k=2
输出：[1,2]

输入：[2,1,1,5], k=2
输出：[1,1]

输入：[2,1,1,5], k=0
输出：[]

输入：[2,1,1,5], k=4
输出：[1,1,2,5]

解法一：排序

解法二：基于快排算法中的 partition 函数的算法

思路：这个解法跟 215. 数组中的第K个最大元素 很相似，求解第 K 大/小或者前 K 大/小的元素都可以用快排思想来解决。不过我们在求解 Top K 类问题时，只需要将枢纽元素的索引和 k 的大小比较，然后再对枢纽元素的一侧来递归分组，而不需要将枢纽两边都进行递归排序。 时间复杂度：最坏情况下是 O(n²)，最好的情况下是 O(n) 空间复杂度：O(1)

快排的模板代码一定要牢记！

    func getLeastNumbers(_ arr: [Int], _ k: Int) -> [Int] {
        guard k > 0 else {
            return []
        }

        guard arr.count > 1 else {
            return arr
        }

        var arr = arr
        var left = 0
        var right = arr.count - 1
        while left < right {
            let pivotIdx = partition(&arr, left, right)
            if pivotIdx > k {
                right = pivotIdx - 1
            } else if pivotIdx < k {
                left = pivotIdx + 1
            } else {
                break
            }
        }
        return Array(arr[0...k-1])
    }

    // 这个函数要背下来
    func partition(_ arr: inout [Int], _ left: Int, _ right: Int) -> Int {
        let randomIdx = Int.random(in: left...right)
        arr.swapAt(randomIdx, right)

        let pivot = arr[right]
        var pivotIdx = left
        for i in left...right {
            if arr[i] < pivot {
                arr.swapAt(i, pivotIdx)
                pivotIdx += 1
            }
        }
        arr.swapAt(pivotIdx, right)
        return pivotIdx
    }

解法三：基于堆或者红黑树

TODO

[ShannonChenCHN]

剑指 Offer 39. 数组中出现次数超过一半的数字

注：本题同主站 169. 多数元素

解法三：2021.02.14 08:30 pm~09:10 pm

参考题解：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/pai-xu-map-fen-zhi-boyer-moore-mo-er-tou-piao-wei-/

测试 case

输入：[1, 2, 3, 2, 2, 2, 5, 4, 2]
输出：2

解法一：HashMap

思路：遍历整个数组，同时用 HashMap 记录每个元素出现的次数，并检查其是否超过数组大小的一半。

解法二：排序

思路：如果一个数组中存在出现次数超过数组大小一半的数字，那么当我们将数组排好序之后，位于数组中间的数字就是我们要找的数字。各种常规的排序算法中，最快的时间复杂度是 O(nlogn)。

解法三：基于快排 partition 函数的算法

思路：核心思想跟解法二一样，如果一个数组中存在出现次数超过数组大小一半的数字，那么当我们将数组排好序之后，位于数组中间的数字就是我们要找的数字。 不过我们不需要排序也能找到目标元素，跟 215. 数组中的第K个最大元素 和 40. 最小的k个数 一样，这里我们可以借助快排的思想，找出理想的枢纽元素，直到枢纽元素正好是数组中间的元素。 时间复杂度：最坏情况下是 O(n²)，最好的情况下是 O(n) 空间复杂度：O(1)

func majorityElement(_ nums: [Int]) -> Int {
        var arr = nums
        var pivotIndex = -1
        var low = 0
        var high = arr.count - 1
        let middleIndex = arr.count / 2 
        while pivotIndex != middleIndex {
            pivotIndex = partition(&arr, low, high)
            if pivotIndex < middleIndex {
                low = pivotIndex + 1
            } else if pivotIndex > middleIndex {
                high = pivotIndex - 1
            }
        }

        return arr[pivotIndex]
    }

    func partition(_ nums: inout [Int], _ low: Int, _ high: Int) -> Int {
        let randomIndex = Int.random(in: low...high)
        nums.swapAt(randomIndex, high)

        let pivot = nums[high]
        var pivotIndex = low 
        for i in low...high {
            if nums[i] < pivot {
                nums.swapAt(i, pivotIndex)
                pivotIndex += 1
            }
        }
        nums.swapAt(pivotIndex, high)

        return pivotIndex
    }

解法四：分治法

见169. 多数元素

解法五：Boyer-Moore 摩尔投票算法

见169. 多数元素