欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

排序算法总结-python实现

程序员文章站 2022-04-19 15:41:01
最近在复习软考,把看到的排序算法整理了一下,之所以用python写,是因为python写起来简单....好吧,后来写的时候发现有些地方用c写还方便些。python虽然简洁,但用起来...

最近在复习软考,把看到的排序算法整理了一下,之所以用python写,是因为python写起来简单....好吧,后来写的时候发现有些地方用c写还方便些。python虽然简洁,但用起来效率感觉还是有些低,不过这不是重点啦。。。

# -*- coding: utf-8 -*-

def bubblesort(data):
    '''冒泡排序: 时间复杂度最好o(n),平均o(n*n),最坏o(n*n),辅助空间 o(1),算法稳定
       n个数,每次从第一个数开始和相邻的数比较,将大的冒泡到后面去。第一趟将最大的冒泡到最后,
       然后第二次只需比较0~n-1,将其中最大的冒泡到n-1,依次下去...总共进行n-1趟排序即可
    '''
    if data:
        for i in range(len(data)):
            for j in range(len(data)-i-1):
                if data[j]>data[j+1]:
                    data[j],data[j+1]=data[j+1],data[j]
    return data

def quicksort(data,low,high):
    '''快速排序:o(n*logn),o(n*logn),o(n*n),o(n*logn),不稳定
        冒泡的改进,被认为是当前最优秀的内部排序算法,实现基于分治法:分解-解决-合并。
        基本思想:
        1.从数列中取出一个基数,
        2.将数列中比他大的放在右边,小的在左边。
        3.两边区间重复2,直到各区间只有一个数。
        整个算法中的基数就是个坑,跳来跳去,总之比他小始终放一边,大的放另一边就行
        参考:https://blog.csdn.net/morewindows/article/details/6684558
    '''
    if low =base:
                right-=1
            if left =0 and data[j] > key:
                data[j+1]=data[j]
                j-=1
            data[j+1]=key
    return data

def selectsort(data):
    '''选择排序: 时间复杂度最好o(n*n),平均o(n*n),最坏o(n*n),辅助空间 o(1),算法不稳定
        n个数,每一趟从待排序列l2中选择最大(或最小)数顺序放在已排好序列l1后面(或前面)
        总共经过n-1趟可排好,与插入排序相比,都是将数据分为已排和未排序列并将未排元素整理
        到已排序列中,不同的是插入排序在未排序列中按序整理,选排则是按大小选择整理。
    '''
    if data:
        for i in range(len(data)-1):
            minnum=i
            for j in range(i+1,len(data)):#在l2中寻找最小值
                if data[j] 1:
        gap=n/2 
        while gap > 0:   
            for i in range(gap):#按步长插入排序
                for j in range(i+gap,n,gap):
                    if data[j] =0 and data[k] > key:
                            data[k+gap]=data[k]
                            k-=gap
                        data[k+gap]=key
            gap/=2
    return data
                    
        
if __name__ =="__main__":
    data=[3,5,1,56,3,7,34,21,8]
    print data
    #insertsort(data)
    #bubblesort(data)
    #selectsort(data)
    #shellsort(data)
    quicksort(data,0,len(data)-1)
    print data