阅读 16

排序算法之快速排序

###快速排序

  • 快速排序的执行流程

    1. 从序列中选择一个轴点元素
    2. 将有序序列与轴点元素比较,分割成两个子序列
      • 小于轴点元素的放在左侧
      • 大于轴点元素的放在右侧
      • 等与轴点元素的随意放
    3. 重复执行1,2两步,直到子序列只剩下一个元素
  • 快速排序的本质: 将每一个元素都转换成轴点元素进行比较

  • 快速排序图解:

快.png

构造出 [begin, end) 范围的轴点元素:

/// 构造出 [begin, end) 范围的轴点元素
    /// - Parameters:
    ///   - begin: <#begin description#>
    ///   - end: <#end description#>
    /// - Returns: 轴点元素的最终位置
    func pivotIndex(begin b:Int,end e:Int) -> Int {
        var begin = b
        var end = e
        // 定义0位置为轴点元素,随机选择序列中一个位置与第0元素交换位置,避免数组分布极度不均匀
        let randomBegin = Int(arc4random() % UInt32(end - begin))
        swap(begin: begin, target: begin + randomBegin)
        // pivot: 轴点元素
        let pivot = array[begin]
        end -= 1
        /**
         右侧索引从末尾开始以此向左移动,当end索引元素大于轴点元素,无需移动元素,end向左移动一位,否则覆盖begin位置
         左侧索引从头部开始以此向右移动,当begin索引元素小于轴点元素,无需移动元素,begin向右移动一位,否则覆盖endend位置
         当begin和end重合是结束本轮循环
         */
        while begin < end {
            while begin < end {
                if pivot < array[end] {
                    end -= 1
                }else{
                    array[begin] = array[end]
                    begin += 1
                    break
                }
            }
            while begin < end {
                if pivot > array[begin] {
                    begin += 1
                }else{
                    array[end] = array[begin]
                    end -= 1
                    break
                }
            }
        }
        array[begin] = pivot
        return begin
    }
复制代码
  • 归并排序的稳定性
    • 属于不稳定排序
  • 归并排序的时间复杂度和空间复杂度
    • 时间复杂度
      • O(nlogn)
      • O(nlogn)是左右元素分布比较均匀的情况下的时间复杂度,若极度不均匀,可能变成O(n^2),例如:[7,1,2,3,4,5,6]
    • 空间复杂度
      • O(logn)

      • logn因为递归调用

源码及单元测试:https://github.com/yukifeng/suanfaStudy