首页 / 算法 / 大话算法-排序-快排序
大话算法-排序-快排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了大话算法-排序-快排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2390字，纯文字阅读大概需要4分钟。
内容图文
快速排序是一种划分交换排序
基本思想是：
1．先从数列中取出一个数作为基准数，一般是第一个数。
2．将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
若序列基本有序时，蜕变成冒泡排序，最坏情况是已经排好序
平均时间复杂度O(nlogn)
快速排序采用“分而治之、各个击破”的观念，此为原地（In-place）分割版本。
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
1、从数列中挑出一个元素，称为“基准”（pivot），
2、重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
3、递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
4、递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
def partaion(data, left, right):
less = left - 1 #小区域是从列表初始位置前一位开始
more = right #大区域是从列表末尾位置开始，因为末尾位置的数是分隔值，可以视为末尾位置无值
# 遍历整个待定区域 left < 待定区域 < more
while left < more:
# data[right] 是选择的那个比较项
# 如果数 小于 比较项，小于区向右移动一位
if data[left] < data[right]:
less += 1
data[left], data[less] = data[less], data[left]
left += 1
# 如果数 大于 比较项，大于区向左移动一位
elif data[left] > data[right]:
more -= 1
data[left], data[more] = data[more], data[left]
# 如果等于比较项 直接跳过
else:
left += 1
# 整个列表分隔完后，此时left已经来到大区域的第一个位置（等于区 < left 大于区域），和末尾值交换（末尾值是分隔值）
data[more], data[right] = data[right], data[more]
# 此时返回小于区域的末尾边界 和大于区域的开始边界
return less, more+1
def sort(data, left, right):
# 如果列表为空或者，所需区域不存在，则返回
if not data or left > right:
return
# 随机选择一位作为分界点，将整个排序过程变成时间复杂度的期望值
index = random.randint(left, right)
# 交换到末尾，节省一个变量
data[right], data[index] = data[right], data[index]
# 将列表的数按分隔值分开
mid = partaion(data, left, right)
# 递归排序分隔值左边的列表
sort(data, left, mid[0])
# 递归排序分隔值右边的列表
sort(data, mid[1], right)
return data
if __name__ == '__main__':
a = [5, 3, 4, 2, 6, 1, 1, 7, 8, 5, 9, 5, 5, 6, 5]
a = [-1, -1, 0, -3, -99, 9, 11, 2, 5, 0]
a = [27, 13, 30, 14, 11, 11,13,13, 5, 6, 16, 18, 7, 17, 5,11,13]
print(sort(a, 0, len(a)-1))
内容总结
以上是互联网集市为您收集整理的大话算法-排序-快排序全部内容，希望文章能够帮你解决大话算法-排序-快排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。