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

量化交易吧 /  源码分享 帖子：3365764 新帖：18

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

量化课程

    移动端课程