算法介绍

次序选择问题通常是指从一个包含不同元素的数组或序列中选择第𝑘小（或第𝑘大）的元素。这个问题的一个典型应用是在统计学和算法设计中，以找到中位数或某一百分位数的值。

形式化定义

算法步骤

• 分（Divide）：
  • 选择基准值（也称“主元”） (Pivot): 在待选择的数组或子数组中选择一个元素作为基准值（也称“主元”）。可以选择第一个元素、最后一个元素、中间元素或使用其他选择策略，如随机选择或“三数中值”法。
  • 划分 (Partition): 通过与基准值（也称“主元”）的比较，重新排列数组使得：基准值左边的所有元素都不大于它；基准值（也称“主元”）右边的所有元素都不小于它。
• 治（Conquer）：确定主元在划分后所属的子数组。
  • 如果 𝑘 恰好等于等于左子数组的长度+1，那么主元就是第 𝑘 小的元素，问题得到解决。
  • 如果 𝑘 小于左子数组的长度+1，就在左子数组中查找第 𝑘 小的元素。
  • 如果 𝑘 大于左子数组的长度+1，就在右于子数组中查找第 𝑘 小的元素。
  • 不断递归以上过程，直至找到第 𝑘 小的元素。
• 合（Merge）：无此过程

算法图示

分

• 基本思想

  • 选择基准值：任选元素𝒙作为分界线，称为主元(pivot)
    

  • 划分：交换重排，满足𝒙左侧元素小于右侧
    

• 实现方法一：选取固定位置为主元

  • 选择基准值：选取固定位置主元𝒙（如尾元素）
    

  • 划分与治的策略：

    • 选取固定位置主元，小于主元的元素个数 q-p
      
      
    • 情况𝟏：𝒌 = 𝒒 − 𝒑 + 𝟏，𝑨[𝒒]为数组第𝒌小元素
      
    • 情况2：𝒌 < 𝒒 − 𝒑 + 𝟏，数组第𝒌小元素在𝑨[𝒑. . 𝒒 − 𝟏]中
      
      
    • 情况3：𝒌 > 𝒒 − 𝒑 + 𝟏，在𝑨[𝒒 + 𝟏. . 𝒓]中寻找第𝒌 − (𝒒 − 𝒑 + 𝟏)小元素
      

  • 递归实现分治
    

合

无此过程

实现方法一：选取固定位置为主元

算法实例

• 问题：在以下数组中查找第8小元素
  
• 算法实现
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

伪代码

function orderSelect(array, k)
    if array.length == 1
        return array[0]  # 基本情况：数组中只有一个元素，直接返回这个元素
    else
        # 选取最后一个元素作为主元
        pivot = array[array.length - 1]
        # 初始化子数组
        less = []  # 存放小于主元的元素
        equal = []  # 存放等于主元的元素
        greater = []  # 存放大于主元的元素
        
        for i from 0 to array.length - 2
            if array[i] < pivot
                append array[i] to less  # 如果元素小于主元，加入 less 子数组
            else if array[i] == pivot
                append array[i] to equal  # 如果元素等于主元，加入 equal 子数组
            else
                append array[i] to greater  # 如果元素大于主元，加入 greater 子数组
        
        if k < length(less)
            # 第 k 小元素在 less 子数组中
            return orderSelect(less, k)
        else if k < length(less) + length(equal)
            # 第 k 小元素等于主元
            return pivot
        else
            # 第 k 小元素在 greater 子数组中
            return orderSelect(greater, k - length(less) - length(equal))

算法时间复杂度分析

• 最好情况：第k小元素就是所求（现象类似于上一节的“快速排序”，需要对比的同学可以参考上一章。）

  • 时间复杂度：𝑻(𝒏) = 𝑶(𝒏)
  • 图示
    

• 最坏情况：所选主元划分出来的2个数组，其中1个永远是空数组。

  • 时间复杂度
    

  • 图示
    

• 总结：不同的输入导致此种实现方式不同的算法效率，我们如何摆脱输入导致最坏情况的困境？因为最差的情况是数组划分时选取固定位置主元，因此可以针对性构造最差情况。所以我们可以在数组划分时选取随机位置主元，这样无法针对性构造最差情况。这也是第二种实现方法：随机位置划分。

实现方法二：随机化选取主元

算法图示

伪代码

function randomOrderSelect(array, k)
    if array.length == 1
        return array[0]  # 基本情况：数组中只有一个元素，直接返回这个元素
    else
        # 随机选择主元
        randomly_select pivot from array
        # 初始化子数组
        less = []  # 存放小于主元的元素
        equal = []  # 存放等于主元的元素
        greater = []  # 存放大于主元的元素
        
        for each element in array
            if element < pivot
                append element to less
            else if element == pivot
                append element to equal
            else
                append element to greater
        
        if k < length(less)
            # 第 k 小元素在 less 子数组中
            return randomOrderSelect(less, k)
        else if k < length(less) + length(equal)
            # 第 k 小元素等于主元
            return pivot
        else
            # 第 k 小元素在 greater 子数组中
            return randomOrderSelect(greater, k - length(less) - length(equal))

算法时间复杂度分析

随机化选取主元之后的时间复杂度是 𝑶(𝒏)

算法总结

次序选择问题借用了快速排序的分治框架思想，只是二者“治合”有所不同，快速排序需要排序；而次序选择无需排序，因此其无“合”的阶段。既然思想相近，就会遇到相似的问题，如固定主元选择会出现最优、最坏两种情况，而二者的解决方案也是一致的，利用随机主元的选择，大大降低了这种风险。

快速排序与次序选择的比较