python排序算法（一）

py3study

发布于 2020-01-09 16:47:30

3390

发布于 2020-01-09 16:47:30

文章被收录于专栏：python3

接触python这么些日子下来，感触最深的就是有的知识是相通的，是无论编程语言的，比如说算法O(∩_∩)O~。So，今天开始用python再把之前学过的排序算法重写一遍，权当复习提升吧。

第一个是冒泡排序：

def bubble(x):
    counter=0
    n=len(x)
    for i in range(n):
        for j in range(i,n-1):
            counter+=1
            if x[j]>x[j+1]:
                t=x[j]
                x[j]=x[j+1]
                x[j+1]=t
    return counter
x=[1,3,9,7,12,23,4,16,20]
counter=bubble(x)
for a in x:
    print(a)
print('times:'+str(counter))

为了比较几种算法的复杂度，我把它们的循环次数也输出出来了。

冒泡排序的原理就是通过一个个比较来得到各个排位的数，比较容易懂，但是复杂度也是最高的。这里counter输出是36。

第二个是插入排序：

def insert(x,key,i):
    counter=0
    while (i>=0 and key<x[i]):
        x[i+1]=x[i]
        i-=1
        counter+=1
    x[i+1]=key
    return counter
def InsertionSort(x,n):
    counter=0
    for j in range(1,n):
        counter+=1
        counter+=insert(x,x[j],j-1)
    return counter
x=[1,3,9,7,12,23,4,16,20]
counter=InsertionSort(x,len(x))
for a in x:
    print(a)
print('times:'+str(counter))

insert函数是确保一个数通过与一个已经排好序的序列比较能知道自己所处的位置并正确插入。InsertionSort则是不停传入这个排好序的序列的参数调用insert函数，从初始的只有一个数，每次逐渐加一个数，但是加一个数就要确保它能在排好序的序列中处于正确的位置。所以这也是它取名插入排序的原因啦~~

这里counter输出的结果是15，明显比冒泡排序提升了一个档次啊