算法札记10——快速排序

浏览: 1388

快速排序

算法思想

快速排序算法首先会在序列中随机选择一个基准值(pivot),然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别,再将其排列成以下形式:

[ 比基准值小] 基准值 [比基准值大]

接着,对两个“[ ]”中的数据进行排序之后,整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序,即使用递归的思想。

时间复杂度

时间复杂度nlog_2(n)
不稳定

https://www.cnblogs.com/onepixel/articles/7674659.html

栗子

image.png


image.png

image.png

image.png


image.png

image.png

image.png

image.png

代码实现

def quick_sort(data):    
"""快速排序"""
if len(data) >= 2: # 递归入口及出口
mid = data[len(data)//2] # 选取基准值,也可以选取第一个或最后一个元素
left, right = [], [] # 定义基准值左右两侧的列表
data.remove(mid) # 从原始数组中移除基准值
for num in data:
# 关于data中的数据,大于mid的放在left中,小于mid的放在right
if num >= mid:
right.append(num)
else:
left.append(num)
# 返回值中对left和right两个子列表分别递归调用函数
return quick_sort(left) + [mid] + quick_sort(right)
else:
return data
def quick_sort(alist, first ,last):
# 快速排序
if first >= last:
return

# 先选择基准值,即第一个元素
mid_value = alist[first]
# 通过两个游标的从头部和尾部的移动来确定基准值的位置
# 满足左边的比基准值小,右边的比基准值大
low = first
high = last

while low < high:
# 下面两个循环交替执行,不断的左右移动

# 如果high指向的元素比基准值大,说明该值应该留在右边
while low < high and alist[high] >= mid_value:
# 同时high的指针往左移动
high -= 1
# 如果不满足循环条件,则说明high指向的值比基准值小,和前面low指向的值交换位置
alist[low] = alist[high]

# 对于左边的low指向的值小于基准值,放在左边
while low < high and alist[low] < mid_value:
low += 1
# 不满足while循环则交换位置
alist[high] = alist[low]
# 从循环退出,low == high
alist[low] = mid_value

# 递归调用函数自身:传入下标的起始值不同,还是原来的列表

# 基准值左边的列表进行快排
quick_sort(alist,first, low-1)

# 基准值右边的列表进行快排
quick_sort(alist,low+1, last)

if __name__ == "__main__":
li = [1, 9, 6, 3, 8, 4, 7, 5, 2]
print(li)
quick_sort(li, 0, len(li)-1)
print(li)

《算法图解》这本书上的代码很好理解

def quicksort(array):
# 判断只有一个元素的情况
if len(array) < 2:
return array
else:
# 指定基数
pivot = array[0]
# 基准数左边:从原有列表中选择出 <= 基准值的元素
less = [i for i in array[1:] if i <= pivot]
# 基准数右边
greater = [i for i in array[1:] if i > pivot]
# 调用函数自身,递归思想
return quicksort(less) + [pivot] + quicksort(greater)
print (quicksort([10, 5, 2, 9, 3, 8, 5]))
推荐 0
本文由 皮大大 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册