python实现快速排序
快速排序是利用分而治之的思想,算法的描叙看起来很容易让人理解,但想通过代码来高效的实现却不容易,主要是要考虑高效, 不能使用instert, 而应该使用在原地交换元素的方法来代替插入。从插入排序算法的实现就可以看出这点。
可以参考:数据结构(下) 邓俊辉教授 清华大学
要实现选取一个基准数(key),比它大的都在它的右边,比它小的都在它的左边,
通常选取数组第一个元素为基准数,把它存到一个变量里面。
有两个指针,left指针初始指上数组头部, right指针初始指上数组尾部, 从数组前后两处开始比较,若尾部的元素比key大,则hight指针往中间跳一格(减去1),若比key小,则把right指针指上的元素存放在left指针的指向的位置
然后左边也如此,
最后左右指针到达同一位置, 把key 放到指针处,
文字过于难描述, 建议看邓俊辉教授的视频。
具体代码实现:
l = [4,5,3,2,8]
def quick_sort(lists, left, right):
if left >= right:
return lists
key = lists[left]
low = left
high = right
while left < right:
while left < right and lists[right] >= key:
right -= 1
lists[left] = lists[right]
while left< right and lists[left] <= key:
left +=1
lists[right] = lists[left]
lists[right] = key
quick_sort(lists, low, left-1)
quick_sort(lists, left+1, high)
return lists
quick_sort(l, 0 , len(l)-1)
print(l)
快速排序简单版本
此版本比上版本会多占一点内存空间
l = [3, 1, 9, 4, 2, 8, 5, 7]
def ks_sort(l):
if len(l) < 2:
return l
else:
st = l[0]
max_l = []
min_l = []
for i in l[1:]:
if i > st:
max_l.append(i)
else:
min_l.append(i)
return ks_sort(min_l) + [st] + ks_sort(max_l)
print(ks_sort(l))
1
1
1
1