|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 qiuyouzhi 于 2020-3-6 10:05 编辑
Python 排序方法： 冒泡排序（3)
继续改进冒泡排序
假设这里有一个列表：(不用代码格式的原因是排版很难看)
[3, 4, 2, 1, 5, 6, 7, 8]
这个列表的特点是前半部分无序(3,4,2,1)，后半部分有序(5,6,7,8)
并且后半部分的最小值也大于前半部分元素的最大值。
如果按照冒泡排序的思路，那么排序起来是这样的：
第一轮：
[3, 4, 2, 1, 5, 6, 7, 8] 8是有序的
第二轮：
[3, 2, 1, 4, 5, 6, 7, 8] 8，7是有序的
第三轮:
[3, 2, 1, 4, 5, 6, 7, 8]8, 7, 6是有序的
......
我们很容易就能发现，其实后面的元素有些已经是有序的了，
可是每一轮还是白白地比较了许多次。
如何优化呢？就是如何判断数列（列表，这里说准确一点）的有序区。
按照现有的逻辑，有序区的长度和排序的轮数是相等的，
实际上，数列真正的有序区可能会大于这个长度，例如上面的例子，
在第二轮排序中，已经有5个元素是有序的了，可是还要白白比较好多遍。
该如何避免呢？我们只需要在每一轮排序后，记录下来最后一次
元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了。
代码：def quick_sort(list1):
# 记录最后一次元素交换的位置
lastExchangeIndex = 0
sortBorder = len(list1) - 1
for i in range(len(list1) - 1):
# 默认值为True
isSorted = True
for j in range(sortBorder):
if list1[j] > list1[j+1]:
temp = list1[j]
list1[j] = list1[j+1]
list1[j+1] = temp
# 有元素进行交换，所以设它为False
isSorted = False
# 更新为最后一次交换元素的位置
lastExchangeIndex = j
sortBorder = lastExchangeIndex
if isSorted:
break
list1 = [5, 2, 6, 9, 3, 4, 1, 8, 7]
quick_sort(list1)
print(list1)
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2020-3-6 09:53:02
置顶卡
千斤顶
显身卡
楼主
发表于 2020-3-6 10:05:12
