题目描述
将一个整数数组进行排序
样例
输入
5
3 1 2 4 5
输出
1 2 3 4 5
算法1
(快速排序) $O(n\log(n))$
采用分治的思想,每次确定一个值的位置,然后将整个数组划分为两个子区间。然后递归去对子区间进行排序。
这里使用两个指针,指针 $i$ 确定小于等于该数的区间边界,指针 $j$ 来遍历整个数组。
Python 代码
n = int(input())
list1 = list(map(int, input().split()))
def quick_sort(list1, low, high):
if low >= high:
return
mid = partition(list1, low, high)
quick_sort(list1, low, mid-1)
quick_sort(list1, mid+1, high)
def partition(list1, low, high):
i = low - 1
pivot = list1[high]
for j in range(low, high):
if list1[j] <= pivot:
i += 1
list1[i], list1[j] = list1[j], list1[i]
list1[i+1], list1[high] = list1[high], list1[i+1]
return i+1
if __name__=="__main__":
low = 0
high = len(list1) - 1
quick_sort(list1, low, high)
print(" ".join(list(map(str, list1))))
我也是用的这个算法为什么过不了,提示runtime error
原来是你啊 大佬 失敬失敬
同学 一次快排我会 可怎么实现递归呢?
我写的这个就是递归形式的啊
为啥别人都是一个函数你是两个,读起来读不懂hhh怎么办
很好理解嘛,先找到分界点,将原始的数组划分为左右两个子数组,然后递归对两个子数组进行快速排序。
谢谢 我通过模仿你的算法 后来就慢慢搞懂了
又学了一招将数组映射到字符 可以可以
做笔试常用的操作,字符串转数组和数组转字符串
以前我都是循环int()hhh
学了一招数组映射到list 不错不错