常用的排序算法

常用的排序算法

拿li=[1,3,45,6,78,9,4]来举例

一.冒泡排序

空间复杂度O(n的2次方)

原理:例如你把一组数据从头开始依次遍历过去把最大的或者最小的放在末尾,除了最后一个每个依次进行遍历

def bubble_sort(li):
    for i in range(len(li)-1):
        flag = True
        for j in range(len(li)-1-i):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                flag = False
        if flag:
            return
bubble_sort(li)

二.选择排序

空间复杂度O(n的2次方)

速度比冒泡快一点

原理:例如你把一篮子苹果让你从大到小进行排序,你就算先拿出一个,再拿出第二个和第一个比按大小摆放左还是右,再拿第三个和之前已经拍好顺序的队列进行对比放置合适位置,依次进行

def select_sort(li):
    for i in range(len(li)):
        minLoc = i
        for j in range(i+1, len(li)):
            if li[minLoc] > li[j]:
                li[minLoc], li[j] = li[j], li[minLoc]
select_sort(li)

三. 插入排序

空间复杂度O(n的2次方)

速度比选择快一点

原理:例如打牌手牌先抽出,再所有排进行排序,依次抽出依次进行排序替换

def insert_sort(li):
    for i in range(1, len(li)):
        tmp = li[i]
        j = i - 1
        while j >= 0 and li[j] > tmp:
            li[j+1] = li[j]
            j = j - 1
        li[j+1] = tmp
insert_sort(li)

四.快速排序

时间复杂度：O(nlogn)

原理:有点类似二叉树取出一个值以他为基准大的放右边,小的放左边,然后依次递归下去

#递归调用的函数
def partition(data, left, right):
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:
            right = right - 1
        data[left] = data[right]
        while left < right and data[left] <= tmp:
            left = left + 1
        data[right] = data[left]
    data[left] = tmp
    return left

#递归函数
def quick_sort(data, left, right):
    if left < right:
        mid = partition(data, left, right)
        quick_sort(data, left, mid)
        quick_sort(data, mid + 1, right)