题解 | #明明的随机数-快排#

参考：https://www.bilibili.com/video/BV1at411T75o/?spm_id_from=333.337.search-card.all.click&vd_source=e0d139ef9278fd07bd20752f3c433bb0

pivot可以随机选择，比如可以选择第一个数字，设定两个下标。

import sys
c = 0
data = []
for line in sys.stdin:
    if c == 0:
        c = 1
        continue
    a = int(line[:-1])
    # 过滤重复值
    if a not in data:
        data.append(a)

# 快速排序：双边扫描，取哨兵pivot,分成两部分，前一部分数据都小于它，后一部分数据都大于它，再递归调用函数
def part(data, l, r):
    # l,r都是索引
    pivot = data[l]
    while l < r:
        # 右指针操作
        while l < r and data[r] >= pivot:
            r -= 1
        if data[r] < pivot:
            data[l] = data[r]
        # 左指针操作
        while l < r and data[l] <= pivot:
            l += 1
        if data[l] > pivot:
            data[r] = data[l]
    if l == r:
        data[l] = pivot
    mid = l # or r
    return mid # 返回重合的中间索引

def quick_sort(data, l, r):
    if l >= r:
        return
    mid = part(data, l, r)
    quick_sort(data, l=l, r=mid-1) # 左边
    quick_sort(data, l=mid+1, r=r) # 右边

# data = [29, 105, 52, 108, 73, 58, 38, 64, 14, 55, 98, 94, 102, 35, 60, 68, 15, 27, 103, 33, 47, 16, 31, 46, 65, 89, 13, 51, 99, 113, 66, 111, 54, 117, 20, 106, 9, 11, 25, 100, 79, 69, 84, 59, 92, 42]
quick_sort(data, l=0, r = len(data)-1)
# print(data)
print('\n'.join([str(i) for i in data]))