python 常见排序算法

一、冒泡排序

两两对比，大的向后移位，多次循环

def maopao(mylist):
    length = len(mylist)
    for i in range(length - 1, -1, -1):
        for j in range(0, i):
            num = mylist[j]
            if mylist[j] > mylist[j + 1]:
                mylist[j] = mylist[j + 1]
                mylist[j + 1] = num
mylist = [1, 3, 45, 67, 8, 9, 75, 33, 22]
maopao(mylist)
print(mylist)

最好的情况，顺序时间复杂度：0(n), 最坏的时间复杂度: o(n^2)

二、快速排序

def kuaipai(mylist):
    left = []
    right = []
    num = []
    print(mylist)
    if len(mylist) < 2 or len(set(mylist)) == 1:
        return mylist
    else:
        a = mylist[0]
        for i in mylist:
            if i > a:
                right.append(i)
            elif i == a:
                num.append(i)
            else:
                left.append(i)
        return kuaipai(left) + kuaipai(num) + kuaipai(right)


mylist = [1, 3, 45, 22, 67, 8, 1, 3, 9, 75, 33, 22, 22, 22]
va = kuaipai(mylist)
print(va)



# 列表推推倒式写法
def kauipai(mylist):
  if len(mylist) < 2:
     return mylist
  a = mylist[0]
  left = [i for i in mylist if i < a]
  right = [i for i in mylist if i >a]
  num = [i for i in mylist if i ==a]
  return kuaipai(left) + kuaipai(num) + kuaipai(right)
mylist = [1, 3, 45, 67, 8, 9, 75, 33, 22]
va = kuaipai(mylist)
print(va)

快排是从中取出一个基准数，进行对比，晓大的在左边，小的在右边。然后再排序左边，和右边
时间复杂度：最好的韦o(nlogn), 最坏为o(n^2)
三、快排

def xuanze(mylist):
    for i in range(len(mylist) - 1):
        num = i
        for j in range(i + 1, len(mylist)):
            if mylist[j] < mylist[num]:
                num = j
        mylist[num], mylist[i] = mylist[i], mylist[num]
    return mylist


mylist = [1, 3, 45, 67, 8, 9, 75, 33, 22]
va = xuanze(mylist)
print(va)