题目描述
将读入的 NN 个数从小到大排序后输出。
输入格式
第一行为一个正整数 NN。
第二行包含 NN 个空格隔开的正整数 aiai,为你需要进行排序的数。
输出格式
将给定的 NN 个数从小到大输出,数之间空格隔开,行末换行且无空格。
输入输出样例
输入 #1复制
5 4 2 4 5 1
输出 #1复制
1 2 4 4 5
说明/提示
对于 20%20% 的数据,有 1≤N≤1031≤N≤103;
对于 100%100% 的数据,有 1≤N≤1051≤N≤105,1≤ai≤1091≤ai≤109。
快速排序模板:
def qsort(num):if len(num) <= 1:return numelse:temp = num[len(num)//2]left = [i for i in num if i < temp]middle = [i for i in num if i == temp]right = [i for i in num if i > temp]return qsort(left) + middle + qsort(right)if __name__ == "__main__":N = int(input())num = list(map(int, input().split()))num = qsort(num)print(' '.join(str(i) for i in num))
题目描述
输入 nn(1≤n<50000001≤n<5000000 且 nn 为奇数)个数字 aiai(1≤ai<1091≤ai<109),输出这些数字的第 kk 小的数。最小的数是第 00 小。
请尽量不要使用 nth_element
来写本题,因为本题的重点在于练习分治算法。
输入格式
无
输出格式
无
输入输出样例
输入 #1复制
5 1 4 3 2 1 5
输出 #1复制
2
# 排序
def qsort(num, l, r, k):if l == r:return num[l]p = (l+r)//2 # 以中间的数为基准temp = qsort_num(num, l, r, p) # 得到基准数的位置if k == temp: # 如果位置等于我们要找的kreturn num[k] # 输出elif k < temp:return qsort(num, l, temp-1, k) # 如果比k大,则说明我们找到还不够小,要往左边再找elif k > temp:return qsort(num, temp+1, r, k) # 同上,只不过是不够大# 得到基准位置
def qsort_num(num, l, r, p):store = l temp = num[p]num[p], num[r] = num[r], num[p] # 把基准数移到列表最后一个for i in range(l, r): if num[i] < temp: # 如果比基准数小num[store], num[i] = num[i], num[store] # 交换,应该在基准数位置的左边store += 1 # 移动基准位置num[store], num[r] = num[r], num[store] # 最后就是我们基准数该呆的位置return storeif __name__ == "__main__":n, k = map(int, input().split())num = [int(i) for i in input().split()]print(qsort(num, 0, n-1, k))