算法---找出一组序列中的第k小(大)的元素

#第一种：分组比较
def partition(seq):
    pi = seq[0]
    lo = []
    hi = []
    for element in seq[1:]:
        if element <= pi:
            lo.append(element)
        else:
            hi.append(element)
    return lo, pi, hi


def select(seq, k):
    if not seq:  # 检查输入序列是否为空
        raise ValueError("输入的序列不能为空")
    if k < 0 or k >= len(seq):  # 检查k值是否合法
        raise ValueError("k值超出了序列长度范围")
    lo, pi, hi = partition(seq)
    m = len(lo)
    if m == k:
        return pi
    elif m < k:
        return select(hi, k - m - 1)
    else:
        return select(lo, k)


if __name__ == '__main__':
    seq = [3, 4, 1, 6, 3, 7, 9, 13, 93, 0, 100, 1, 2, 2, 3, 3, 2]
    try:
        print(select(seq, 3))
        print(select(seq, 1))
    except ValueError as e:
        print(e)

# 第二种：快速排序的分治算法
def quicksort(num, low, high):
    if low < high:
        location = partition(num, low, high)
        quicksort(num, low, location - 1)
        quicksort(num, location + 1, high)

def partition(num, low, high):
    pivot = num[high]  # 基准值选择最后一个元素
    while low < high:
        while low < high and num[low] <= pivot:  # 寻找比基准值大的元素
            low += 1
        while low < high and num[high] >= pivot:  # 寻找比基准值小的元素
            high -= 1
        if low < high:
            temp = num[low]
            num[low] = num[high]
            num[high] = temp
    num[high] = pivot  # 将基准值放到中间
    return high

def findkth(num, low, high, k):
    index = partition(num, low, high)
    if index == k:
        return num[index]
    elif index < k:
        return findkth(num, index + 1, high, k)
    else:
        return findkth(num, low, index - 1, k)

pai = [2, 3, 1, 5, 4, 6]
quicksort(pai, 0, len(pai) - 1)  # 先对数组进行排序
print(findkth(pai, 0, len(pai) - 1, 5))  # 打印第5小的元素

#第三种：分组和排序同时进行
def selectTopK(a, low, high, k):
    if low == high and k == 0:
        return a[0]
    pivotkey = a[high]
    i, j = low, high
    while i < j:
        while i < j and a[i] <= pivotkey:  # 比较操作符
            i += 1
        a[i], a[j] = a[j], a[i]  # 先交换元素
        while i < j and a[j] >= pivotkey:  # 比较操作符
            j -= 1
        a[i], a[j] = a[j], a[i]  # 再交换元素
    print('i:', i)
    if k < i:
        return selectTopK(a, low, i - 1, k)
    elif k > i:
        return selectTopK(a, i + 1, high, k)
    else:
        return a[i]

# 测试函数
print(selectTopK([1, 5, 3, 4, 2, 3], 0, 5, 3))

#第四种：生成随机校验码
import random
def selectTopK(a, low, high, k):
    if low == high and k == 1:
        return a[low]
    m = random.randint(low, high)
    pivotkey = a[m]
    a[m], a[high] = a[high], a[m]
    i = low - 1
    for j in range(low, high):
        if a[j] < pivotkey:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[high] = a[high], a[i + 1]
    print('i:', i + 1)
    t = i + 1
    if k < t:
        return selectTopK(a, low, i, k)
    elif k > t:
        return selectTopK(a, i + 2, high, k - t)
    else:
        return a[i + 1]

# 测试代码
print(sorted([1, 5, 3, 4, 2, 3, 9]))
print(selectTopK([1, 5, 3, 4, 2, 3, 9], 0, 6, 1))

输出结果：

第二种：

第三种：
 

第四种：