插入排序和选择排序的实现_实现插入排序或选择排序(5分)

1.插入排序

            这种方法思路是有一个空数组每次按大小将数据插入进去(放到数组最后,或者与数组中成员交换位置之后成员都向后移动),到最后就可以得到一个按顺序排列的数组,这里用Python加以实现(降序排列)

def sort(x):
    for i in range(2,len(x)):
        key=x[i]
        j=i-1
        while i>0 and x[j]>key:
            x[j+1]=x[j]
            j=j-1
            x[j+1]=key
    return x

可以计算出增长量级为O(n^2)

2.选择排序

      这种算法思路更为直接,找到数组中最大的元素放在数组第0位，第二大的元素放在数组第1位.....

这里用Python实现(降序排列)

def choose(x):
    count=0
    y=[]
    for num in range(len(x)):
        y.append(0)
    for i in range(len(x)):
        for j in range(len(x)):
            if i != j and x[i]<x[j]:
                count+=1
        y[count]=x[i]
        count=0
    return y
    
            
#算法分析
#算法思路
def gaijin(x):
    temp=0                             #1
    count=0                            #1
    for i in range(len(x)):            #x
        for j in range(len(x)):        #x^2
            if i != j and x[i]<x[j]:   #x(x-1)
                count+=1               #y
        temp=x[count]                  #x-1
        x[count]=x[i]                  #x-1
        x[i]=temp                      #x-1
        count=0                        #x-1
    return x                           #1
 
from random import *
x=[1,2,3,4,5]
shuffle(x)
print(x)

第一个函数需要新建一个列表 改进后不再需要建立新的列表

计算出2增长量级O(n^2)