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

常用的排序算法

程序员文章站 2024-01-28 13:44:40
常用的排序算法 拿 来举例 一.冒泡排序 空间复杂度O(n的2次方) 原理:例如你把一组数据从头开始依次遍历过去把最大的或者最小的放在末尾,除了最后一个每个依次进行遍历 二.选择排序 空间复杂度O(n的2次方) 原理:例如你把一篮子苹果让你从大到小进行排序,你就算先拿出一个,再拿出第二个和第一个比按 ......

常用的排序算法

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)