常用的排序算法（常用的排序算法,时间、空间复杂度）

常用的排序算法（常用的排序算法,时间、空间复杂度）

常用的排序算法

常用的排序算法

拿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)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。