内容字号:默认大号超大号

段落设置:段首缩进取消段首缩进

字体设置:切换到微软雅黑切换到宋体

python简单排序

2018-04-16 16:30 出处:清屏网 人气: 评论(0

1. 冒泡排序
--> 两两比较,交换位置
--> 属交换排序
-->  n个数从左至右,编号从0开始到n-1,索引0和1的值比较,如果索引0的值大,则交换两者位置,如
果索引1大,则不交换。继续比较索引1和2的值,将大值放在右侧。直至n-2和n-1比较完,第
一轮比较完成。第二轮从索引0比较到n-2,因为最右侧n-1位置上已经是最大值了。依次类推,
每一轮都会减少最右侧的不参与比较,直至剩下最后2个数比较 
 
冒泡排序方法(一)
lst = [1,9,4,8,3,7,5,2,6,10]
length = len(lst)
for i in range(length):
    for j in range(length-1-i):   
        if lst[j] > lst[j+1]:
            lst[j], lst[j+1] = lst[j+1], lst[j]
print(lst)
第四行, length-1-i,为什么要减i呢? 
    因为每次比较过程,都可以确定出当前这轮的极值(极大),并且放置在最右端,形成一个有序区域. 
    不减i也不会影响最终比较结果,只是做了一些无用的比较
如果列表内是字符串,上面代码依然适用.因为'>' '<' 可用于同类型比较,(不同类型的比较,需要设定key的类型)
上面代码的时间复杂度为O(n**2),优化点,如果某一轮比较过程中并没有交换发生,意味着序列已经排好

冒泡排序方法(二)
lst = [1,9,4,8,3,7,5,2,6,10]
length = len(lst)
for i in range(length):
    flag = False
    for j in range(length-1-i):
        if lst[j] > lst[j+1]:
            lst[j], lst[j+1] = lst[j+1], lst[j]
            flag = True
    if not flag:
        break
print(lst)

红色部分为方法一二的区别,用标记辅助排序,记录此轮比较是否有交换发生, 如果没有发生交换,排序结束

总结

冒泡法需要数据一轮轮比较

最好的情况是,初始顺序是最终的期望,遍历n-1次

最差的情况是,初始顺序与期望相反,遍历n(n-1)/2

用标记记录此轮是否有交换发生,如果没有发生交换,排序结束

时间复杂度为O(n**2)

2. 简单选择排序

–> 两两比较,找极值

–>

n个数从左至右,索引从0开始到n-1, 两两依次比较 ,记录大值索引,此轮所有数比较完毕,将

大数和索引0数交换,如果大数就是索引1,不交换。第二轮,从1开始比较,找到最大值,将它

和索引1位置交换,如果它就在索引1位置则不交换。依次类推,

每次左边都会固定下一个大数 (降序排列)

简单排序实现(一)

lst = [1,9,4,8,3,7,5,2,6,10]
length = len(lst)
for i in range(length):
    maxindex = i                 # 默认迭代值i对应的值为最大值
    for j in range(i+1,length):
        if lst[maxindex] < lst[j]:
            maxindex = j
    if i != maxindex:           # 避免两数相等的情况(相邻数字大小相等,不交换位置)
        lst[i], lst[maxindex] = lst[maxindex], lst[i]
print(lst)

总结
-> 需要数据一轮轮比较,并在每一轮中发现极值
-> 没有办法知道当前轮是否已经达到排序要求,但是可以知道极值是否在目标索引位置上
-> 遍历次数n(n-1)/2
-> 时间复杂度O(n2)

插入排序
-> 在前端增加哨兵位置,构建有序区域,迭代无序区数据和有序区的数据做比较运算

-> 增加一个哨兵位,每轮放入待比较数
哨兵依次和待比较的前一个数据比较,大数靠右移动,找到哨兵 (中的值的位置) 位置插入
每一轮结束后,得到一个从开始到待比较数位置的一个有序序列
<!--5f39ae17-8c62-4a45-bc43-b32064c9388a:W3siYmxvY2tJZCI6IjY0NjktMTUyMzM2OTM5OTE3OCIsImJsb2NrVHlwZSI6InBhcmFncmFwaCIsInN0eWxlcyI6eyJsaW5lLWhlaWdodCI6MS4yNSwiYWxpZ24iOiJsZWZ0IiwiaW5kZW50IjowLCJ0ZXh0LWluZGVudCI6MH0sInR5cGUiOiJwYXJhZ3JhcGgiLCJyaWNoVGV4dCI6eyJkYXRhIjpbeyJjaGFyIjoi4oaRIn0seyJjaGFyIjoiXyJ9LHsiY2hhciI6IiAifSx7ImNoYXIiOiItIn0seyJjaGFyIjoiPiJ9LHsiY2hhciI6IiAifSx7ImNoYXIiOiLlop4ifSx7ImNoYXIiOiLliqAifSx7ImNoYXIiOiLkuIAifSx7ImNoYXIiOiLkuKoifSx7ImNoYXIiOiLlk6gifSx7ImNoYXIiOiLlhbUifSx7ImNoYXIiOiLkvY0ifSx7ImNoYXIiOiIsIn0seyJjaGFyIjoi5q+PIn0seyJjaGFyIjoi6L2uIn0seyJjaGFyIjoi5q+UIn0seyJjaGFyIjoi6L6DIn0seyJjaGFyIjoi5b6FIn0seyJjaGFyIjoi5q+UIn0seyJjaGFyIjoi6L6DIn0seyJjaGFyIjoi5pWwIn0seyJjaGFyIjoi5pS+In0seyJjaGFyIjoi5YWlIn0seyJjaGFyIjoiLCJ9XSwiaXNSaWNoVGV4dCI6dHJ1ZSwia2VlcExpbmVCcmVhayI6dHJ1ZX19LHsiYmxvY2tJZCI6IjcyODItMTUyMzUwMzk1ODM2OCIsImJsb2NrVHlwZSI6InBhcmFncmFwaCIsInN0eWxlcyI6eyJsaW5lLWhlaWdodCI6MS4yNSwiYWxpZ24iOiJsZWZ0IiwiaW5kZW50IjowLCJ0ZXh0LWluZGVudCI6MH0sInR5cGUiOiJwYXJhZ3JhcGgiLCJyaWNoVGV4dCI6eyJkYXRhIjpbeyJjaGFyIjoiICJ9LHsiY2hhciI6InwifSx7ImNoYXIiOiIgIn0seyJjaGFyIjoiICJ9LHsiY2hhciI6IiAifSx7ImNoYXIiOiItIn0seyJjaGFyIjoiPiJ9LHsiY2hhciI6IiAifSx7ImNoYXIiOiLlk6gifSx7ImNoYXIiOiLlhbUifSx7ImNoYXIiOiLkvp0ifSx7ImNoYXIiOiLmrKEifSx7ImNoYXIiOiLlkowifSx7ImNoYXIiOiLlvoUifSx7ImNoYXIiOiLmr5QifSx7ImNoYXIiOiLovoMifSx7ImNoYXIiOiLnmoQifSx7ImNoYXIiOiLliY0ifSx7ImNoYXIiOiLkuIAifSx7ImNoYXIiOiLkuKoifSx7ImNoYXIiOiLmlbAifSx7ImNoYXIiOiLmja4ifSx7ImNoYXIiOiLmr5QifSx7ImNoYXIiOiLovoMifSx7ImNoYXIiOiIsIn0seyJjaGFyIjoi5aSnIn0seyJjaGFyIjoi5pWwIn0seyJjaGFyIjoi5o2uIn0seyJjaGFyIjoi6Z2gIn0seyJjaGFyIjoi5Y+zIn0seyJjaGFyIjoi56e7In0seyJjaGFyIjoi5YqoIn0seyJjaGFyIjoiLCJ9LHsiY2hhciI6IuaJviJ9LHsiY2hhciI6IuWIsCJ9LHsiY2hhciI6IuWTqCJ9LHsiY2hhciI6IuWFtSJ9LHsiY2hhciI6IiAifSx7ImNoYXIiOiIoIn0seyJjaGFyIjoi5LitIn0seyJjaGFyIjoi55qEIn0seyJjaGFyIjoi5YC8In0seyJjaGFyIjoi55qEIn0seyJjaGFyIjoi5L2NIn0seyJjaGFyIjoi572uIn0seyJjaGFyIjoiKSJ9LHsiY2hhciI6IiAifSx7ImNoYXIiOiLkvY0ifSx7ImNoYXIiOiLnva4ifSx7ImNoYXIiOiLmj5IifSx7ImNoYXIiOiLlhaUifSx7ImNoYXIiOiIgIn1dLCJpc1JpY2hUZXh0Ijp0cnVlLCJrZWVwTGluZUJyZWFrIjp0cnVlfX0seyJibG9ja0lkIjoiODQ0MC0xNTIzNTAzODgyMzM3IiwiYmxvY2tUeXBlIjoicGFyYWdyYXBoIiwic3R5bGVzIjp7ImxpbmUtaGVpZ2h0IjoxLjI1LCJhbGlnbiI6ImxlZnQiLCJpbmRlbnQiOjAsInRleHQtaW5kZW50IjowfSwidHlwZSI6InBhcmFncmFwaCIsInJpY2hUZXh0Ijp7ImRhdGEiOlt7ImNoYXIiOiIgIn0seyJjaGFyIjoifCJ9LHsiY2hhciI6IiAifSx7ImNoYXIiOiIgIn0seyJjaGFyIjoiICJ9LHsiY2hhciI6Ii0ifSx7ImNoYXIiOiI+In0seyJjaGFyIjoiICJ9LHsiY2hhciI6IuavjyJ9LHsiY2hhciI6IuS4gCJ9LHsiY2hhciI6Iui9riJ9LHsiY2hhciI6Iue7kyJ9LHsiY2hhciI6IuadnyJ9LHsiY2hhciI6IuWQjiJ9LHsiY2hhciI6IiwifSx7ImNoYXIiOiLlvpcifSx7ImNoYXIiOiLliLAifSx7ImNoYXIiOiLkuIAifSx7ImNoYXIiOiLkuKoifSx7ImNoYXIiOiLku44ifSx7ImNoYXIiOiLlvIAifSx7ImNoYXIiOiLlp4sifSx7ImNoYXIiOiLliLAifSx7ImNoYXIiOiLlvoUifSx7ImNoYXIiOiLmr5QifSx7ImNoYXIiOiLovoMifSx7ImNoYXIiOiLmlbAifSx7ImNoYXIiOiLkvY0ifSx7ImNoYXIiOiLnva4ifSx7ImNoYXIiOiLnmoQifSx7ImNoYXIiOiLkuIAifSx7ImNoYXIiOiLkuKoifSx7ImNoYXIiOiLmnIkifSx7ImNoYXIiOiLluo8ifSx7ImNoYXIiOiLluo8ifSx7ImNoYXIiOiLliJcifV0sImlzUmljaFRleHQiOnRydWUsImtlZXBMaW5lQnJlYWsiOnRydWV9fV0=-->
插入排序实现(一)
lst = [1,9,8,5,6,7,4,3,10]
num1 = [0] + lst               # 列表前补0,做哨兵位
length = len(num1)
for i in range(2,length):      # 索引0为哨兵,1位有序区
    num1[0] = num1[i]
    j = i - 1                  # j为有序区边界(极大)值索引
    if num1[j] > num1[0]:      # 大数右移,找到可插入位置(当前哨兵值)
        while num1[j] > num1[0]:
            num1[j+1] = num1[j] # 依次右移
            j -= 1
        num1[j+1] = num1[0]    # 将哨兵插入, 
print(num1)
print(num1[1:])
~~~~~~~~~~~~~~~~~以下为函数输出~~~~~~~~~~~
[10, 1, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 3, 4, 5, 6, 7, 8, 9, 10]

分享给小伙伴们:
本文标签: python排序

相关文章

发表评论愿您的每句评论,都能给大家的生活添色彩,带来共鸣,带来思索,带来快乐。

CopyRight © 2015-2016 QingPingShan.com , All Rights Reserved.

清屏网 版权所有 豫ICP备15026204号