首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >python常用程序算法

python常用程序算法

作者头像
py3study
发布2020-01-16 00:46:33
2970
发布2020-01-16 00:46:33
举报
文章被收录于专栏:python3python3

一。冒泡排序:

1.冒泡排序是将无序的数字排列成从小到大的有序组合:

过程:对相邻的两个元素进行比较,对不符合要求的数据进行交换,最后达到数据有序的过程。

规律:

1.冒泡排序的趟数时固定的:n-1

2.冒泡排序比较的次数时固定的:n*(n-1)/2

3.冒泡排序交换的次数时不固定的:但是最大值为:n*(n-1)/2

注意:n = 数据个数,排序过程中需要临时变量存储要交换的数据

eg:

l=[688, 888, 711,999,1,4,6]
for i in range(len(l)-1):
    for j in range(len(l)-1):
        if l[j]>l[j+1]:
            tmp=l[j]
            l[j]=l[j+1]
            l[j+1]=tmp
print(l)

二。选择排序:

list=[10,3,5,2,9]

过程,循环当前列表,将当前循环到的值与余下的每个数字相比较,如果比当前值小,就与当前值交换位置。

eg:

l=[688, 888, 711,999,1,4,6]
for i in range(len(l)-1):
    for j in range(i+1,len(l)):
        if l[j]<l[i]:
            tmp=l[i]
            l[i]=l[j]
            l[j]=tmp
print(l)

优化:每次找到最小值后不立即替换,而是等待本次循环结束再替换,减少了操作的次数,效率提高了

l=[688, 888, 711,999,1,4,6]
for i in range(len(l)-1):
    Min=i
    for j in range(i+1,len(l)):
        if l[Min] > l[j]:
            Min=j
    tmp=l[Min]
    l[Min]=l[i]
    l[i]=tmp
print(l)

 三。插入排序:

插入排序(Insertion Sort)的基本思想是:将列表分为2部分,左边为排序好的部分,右边为未排序的部分,循环整个列表,每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。

eg:

array=[9,8,7,6,5,4,3,2,1]

for i in range(1,len(array)):
    current_val=array[i]
    current_position=i
    while current_position >0 and array[current_position-1] > current_val:
        array[current_position]=array[current_position-1]
        current_position-=1
    array[current_position]=current_val
print(array)

 四。快速排序:

def quick_sort(array,first,last):
    if first >= last: #如果first=last证明不能再继续分半操作,每组只剩下一个元素,所有first=end,这时跳出程序
        return
    start=first
    end=last
    mid=array[first]

    while start < end:
        #将end往左移动
        while start < end and array[end] > mid: #如果成立则一直将end往左移动
            end-=1
        array[start]=array[end]  #如果跳出上层循环则证明当前arrary[end]的值小于mid的值,此时将小的值移动至array[start]位置
        #将start往右移动
        while start < end and array[start] < mid:
            start+=1
        array[end]=array[start]
    array[end]=mid  #当最外层循环不成立时证明start与end相等,这时把start或者end位置赋值成mid的值即可
    #继续左边的分半
    quick_sort(array,first,end-1)
    #继续右边的分半
    quick_sort(array,end+1,last)


if __name__ == '__main__':
    import random,time
    array=[]
    for i in range(8):
        array.append(random.randrange(1,10000))
   # array=[11,22,17,9,8,7,6,5,4,3,2]
    quick_sort(array,0,len(array)-1)
    print(array)
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-05-20 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档