繁簡切換您正在訪問的是FX168財經網,本網站所提供的內容及信息均遵守中華人民共和國香港特別行政區當地法律法規。

FX168财经网>人物频道>帖子

5种排序算法python代码实现

作者/爱汇小王子 2019-08-18 22:49 0 来源: FX168财经网人物频道

5种排序算法¶

#.1 选择排序
def select_sort(lists):
    count=len(lists)
    for i in range(0,count):
        mini=i
        for j in range(i+1,count):
            
            if lists[mini]>lists[j]:
                mini=j # mini 保存最小
        
        #交换i 和mini 索引 所在的 元素 【当前i的 for循环中,只交换 一次  】    
        lists[mini],lists[i]=lists[i],lists[mini]
        print('当前行为',i)
        for i1 in lists:
            print(i1)
        
    return lists

if __name__=='__main__':
    lists=[3,4,2,8,9,5,1]
    print('before')
    for i in lists:
        print(i)
    print('after')
    for i in select_sort(lists):
        print(i)
        
before
3
4
2
8
9
5
1
after
当前行为 0
1
4
2
8
9
5
3
当前行为 1
1
2
4
8
9
5
3
当前行为 2
1
2
3
8
9
5
4
当前行为 3
1
2
3
4
9
5
8
当前行为 4
1
2
3
4
5
9
8
当前行为 5
1
2
3
4
5
8
9
当前行为 6
1
2
3
4
5
8
9
1
2
3
4
5
8
9
# 冒泡排序
def bubble_sort(lists):
    count=len(lists)
    for i in range(0,count):
        for j in range(i+1,count):
            
            if lists[i]>lists[j]:
                #【当前i的 for循环中,交换 多次  】 
                #交换i,j ;j 比i 小
                lists[i],lists[j]=lists[j],lists[i]
               
        print('当前行为',i)
        for i1 in lists:
            print(i1)
                
    return lists


if __name__=='__main__':
    lists=[3,4,2,8,9,5,1]
    print('before')
    for i in lists:
        print(i)
    print('after')
    for i in bubble_sort(lists):
        print(i)               
            
            
            
before
3
4
2
8
9
5
1
after
当前行为 0
1
4
3
8
9
5
2
当前行为 1
1
2
4
8
9
5
3
当前行为 2
1
2
3
8
9
5
4
当前行为 3
1
2
3
4
9
8
5
当前行为 4
1
2
3
4
5
9
8
当前行为 5
1
2
3
4
5
8
9
当前行为 6
1
2
3
4
5
8
9
1
2
3
4
5
8
9

排序 选择排序(Selection sort) 是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 冒泡排序(Bubble Sort) 是一种计算解学领域的较简单的排序算法。 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。 冒泡排序的基本思想是将数组中的每个相邻元素进行两两比较,按照小元素在前(或大元素在前)的原则确定是否进行交换。这样每一轮执行之后,最大(或最小)的元素就会被交换到了最后一位。 完成一轮之后,我们可以再从头进行第二轮的比较,直到倒数第二位(因为最后一位已经是被排序好的了)时结束。这样一轮之后,第二大(或第二小)的元素就会被交换到了倒数第二位。同样的过程会依次进行,直到所有元素都被排列成预期的顺序为止。这个过程是不是很像是水中的起泡一个个冒起来的过程.。

区别: 主要在于交换方式: 冒泡法每次比较和移动 ,当前项j和第i项 ; 选择排序,for循环中,找出最小元素,交换一次,当前项j和第min项 。

总的来说,两种排序比较的次数是相同的 ; 但交换的次数,选择排序是更少的 。 但通常,选择排序更快一点 , 冒泡排序是每一次都可能要交换 ; 而选择排序是在比较时记下a[i]的位置 最后来交换 ;

所以他们的交换过程是不一样的 而查找的过程是一样的 。

#.4 归并排序
def merge(left,right):
    i,j=0,0
    result=[]
    while i<len(left) and j<len(right):
        if left[i]<=right[j]:
            result.append(left[i])
            i+=1
        else:
            result.append(right[j])
            j+=1
    result+=left[i:]
    result+=right[j:]
    return result
def merge_sort(lists):
    if len(lists)<=1:
        return lists
    num=int(len(lists)/2)
    
    left=merge_sort(lists[:num])
    right=merge_sort(lists[num:])
    return merge(left,right)

if __name__=='__main__':
    lists=[3,4,2,8,9,5,1]
    
    print('before')
    for i in lists:
        print(i)
        
    print('after')
    for i in merge_sort(lists):
        print(i)   
before
3
4
2
8
9
5
1
after
1
2
3
4
5
8
9
#.5 快排
def quick_sort(lists,left,right):
    if left>=right:
        return lists
    key=lists[left]
    low=left
    high=right
    while left<right:
        while left<right and lists[right]>=key:
            right-=1
        lists[left]=lists[right]
        while left<right and lists[left]<=key:
            left+=1
        lists[right]=lists[left]
    lists[right]=key
    
    quick_sort(lists,low,left-1)
    quick_sort(lists,left+1,high)
    return lists

if __name__=='__main__':
    lists=[3,4,2,8,9,5,1]
    
    print('before')
    for i in lists:
        print(i)
        
    print('after')
    for i in quick_sort(lists,0,len(lists)-1):
        print(i)               
            
            
before
3
4
2
8
9
5
1
after
1
2
3
4
5
8
9
#.7 堆排序
def adjust_heap(lists,i,size):
    lchild=2*i+1
    rchild=2*i+2
    maxs=i
    if i<size/2:
        if lchild<size and lists[lchild]>lists[maxs]:
            maxs=lchild
        if rchild<size and lists[rchild]>lists[maxs]:
            maxs=rchild
        if maxs!=i:
            lists[maxs],lists[i]=lists[i],lists[maxs]
            adjust_heap(lists,maxs,size)
            
def build_heap(lists,size):
    for i in range(0,int(size/2))[::-1]:
        adjust_heap(lists,i,size)
        
def heap_sort(lists):
    size=len(lists)
    build_heap(lists,size)
    for i in range(0,size)[::-1]:
        lists[0],lists[i]=lists[i],lists[0]
        adjust_heap(lists,0,i)
        
if __name__=='__main__':
    lists=[3,4,2,8,9,5,1]
    
    print('before')
    for i in lists:
        print(i)
        
    print('after')
    heap_sort(lists)
    for i in lists:
        print(i) 
    
    
before
3
4
2
8
9
5
1
after
1
2
3
4
5
8
9
 
 
分享到:
举报财经168客户端下载

全部回复

0/140

投稿 您想发表你的观点和看法?

更多人气分析师

  • 金算盘

    人气2696文章7761粉丝124

    高级分析师,混过名校,厮杀于股市和期货、证券市场多年,专注...

  • 李冉晴

    人气2296文章3821粉丝34

    李冉晴,专业现贷实盘分析师。

  • 张迎妤

    人气1896文章3305粉丝34

    个人专注于行情技术分析,消息面解读剖析,给予您第一时间方向...

  • 指导老师

    人气1856文章4423粉丝52

    暂无个人简介信息

  • 梁孟梵

    人气2152文章3177粉丝39

    qq:2294906466 了解群指导添加微信mfmacd

  • 刘钥钥1

    人气2016文章3119粉丝34

    专业从事现货黄金、现货白银模似实盘操作分析指导

  • 张亦巧

    人气2144文章4145粉丝45

    暂无个人简介信息

  • 金帝财神

    人气4720文章8329粉丝118

    本文由资深分析师金帝财神微信:934295330,指导黄金,白银,...

  • 金泰铬J

    人气2320文章3925粉丝51

    投资问答解咨询金泰铬V/信tgtg67即可获取每日的实时资讯、行情...