快速选择算法

python--快速选择算法

 

快速选择（Quicksort）是一种从无序列表找到第k小元素的选择算法。它从原理上来说与快速排序有关。与快速排序一样都由托尼·霍尔提出的，因而也被称为霍尔选择算法。同样地，它在实际应用是一种高效的算法，具有很好的平均时间复杂度，然而最坏时间复杂度则不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。

快速选择的总体思路与快速排序一致，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是，快速选择并不递归访问双边，而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度，从O(n log n)至O(n)，不过最坏情况仍然是O(n2)。

import random

"""
快速选择算法的python实现，它可以有效地计算如果要排序的列表索引中出现的值，即使它尚未排序也是如此。
https://en.wikipedia.org/wiki/Quickselect
"""
def _partition(data, pivot):
    """
三种方式将数据划分为更小、更平等和更大的列表，
与枢轴的关系
*Param数据：要排序的数据(列表)
Param枢轴：对数据进行分区的值
*返回：三个列表：较小、平等和更大
    """
less, equal, greater= [], [], []
    forelementindata:
        ifelement<pivot:
less.append(element)
        elifelement>pivot:
greater.append(element)
        else:
equal.append(element)
    returnless, equal, greater
    
def quickSelect(list, k):
    #K=len(List)/2当试图找到中位数时(当对List排序时，该值将是索引)
    
    #无效输入
    ifk>=len(list) ork<0:
        return None
    
smaller= []
larger= []
pivot=random.randint(0, len(list) - 1)
pivot=list[pivot]
count= 0
smaller, equal, larger=_partition(list, pivot)
count= len(equal)
m= len(smaller)

    #k is the pivot
    ifm<=k<m+count:
        returnpivot
    #must be in smaller
    elifm>k:
        returnquickSelect(smaller, k)
    #must be in larger
    else:
        returnquickSelect(larger, k-(m+count))