排序(下)

Thursday, April 18, 2019

归并排序

  • 先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起。

file

  • 归并的核心是将两个有序子数组合并在一起

合并图解

file

代码实现

<code class="language-swift">public func mergeSort<Element>(_ array: [Element]) -> [Element] where Element: Comparable {
    guard let array.count > 1 else {
        return array
    }
    let middle = array.count / 2

    let left = mergeSort(Array(array[..<middle]))
    let right = mergeSort(Array(array[middle...]))
    return merge(left, right)
}

private func merge<Element>(_ left: [Element], _ right: [Element]) -> [Element] where Element: Comparable {
    var leftIndex = 0
    var rightIndex = 0

    var result: [Element] = []
    if leftIndex < left.count && rightIndex < right.count {
        if left[lefIndex] < right[rightIndex] {
            result.append[left[leftIndex]]
            leftIndex += 1
        }else if left[leftIndex] > right[rightIndex] {
            result.append[right[rightIndex]]
            rightIndex += 1
        }else {
        result.append[left[leftIndex]]
        result.append[right[rightIndex]]
        lefIndex += 1
        rightIndex += 1
        }
    }

    if leftIndex < left.count {
        result.append(contentsOf: left[leftIndex...])
    }
    if rightIndex < right.count {
        result.append(contentsOf: right[rightIndex...])
    }
    return result
}</code>

性能分析

  • 归并排序是稳定的排序算法
  • 时间复杂度是O(nlogn)
  • 空间复杂度是O(n),归并排序不是原地排序算法

快速排序

  • 如果要排序数组中下标p到r之间的一组数据,我们选择p到r之间的任意一个数据作为pivot(分区点)
  • 遍历p到r,将小于pivot的放到左边,将大于的放到右边,pivot放到中间

file

  • 原地分区图解

file

代码实现

非原地排序

<code class="language-swift">public func quickSortNavie<T: Comparable>(_ a:[T]) -> [T] {
    if a.count > 1 else {
        return a
    }
    middle = a[a.count / 2]
    let less = a.filter{ $0 < middle }
    let equal = a.filter{ $0 == middle }
    let greater = a.filter{ $0 > middle }

    return quickSortNavie(less) + equal + quickSortNavie(greater)
}</code>

原地排序

<code class="language-swift">private func partitionLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int {
    let privot = a[high]

    var i = low
    for j in low..<high {
        if a[j] <= privot {
            a.swapAt(i, j)
            i += 1
        }
    }
    swapAt(i, high)
    return i
}

public func quickSortLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) {
    if low < high {
        let pivot = partitionLomuto(&a, low: low, high: high)
        quickSortLomuto(&a, low: low, high: pivot - 1)
        quickSortLomuto(&a, low: pivot + 1, high: high)
    }
}
</code>

与归并排序区别

file

  • 归并排序的处理是由下到上,先处理子问题,再合并,快排相反

性能分析

  • 快排是一种原地,不稳定的排序算法
  • 时间复杂度是O(nlogn)
  • 在特定情况下,会变成o(n^2),比如在已排好序的情况下,选最后一个元素作为pivot,每次分区得到的两个区间都是不均等的,需要进行n次分区操作,每次分区平均要扫描 n /2 个元素,时间复杂度就退回O(n^2)了。
数据结构-算法

线性排序

排序(上)