请 [注册] 或 [登录]  | 返回主站

量化交易吧 /  源码分享 帖子:3129659 新帖:15

5种排序算法python代码实现

爱汇小王子发表于:8 月 18 日 22:49回复(1)

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
 
 

全部回复

0/140

量化课程

    移动端课程