网站建设方案免费/通州优化公司

时间复杂度（最好）

时间复杂度（最坏）

时间复杂度（平均）

空间复杂度

稳定性

选择排序

O(n^2)

O(n^2)

O(n^2)

O(1)

不稳定

插入排序

O(n)

O(n^2)

O(n^2)

O(1)

稳定

冒泡排序

O(n)

O(n^2)

O(n^2)

O(1)

稳定

快速排序

O(nlog(n))

O(n^2)

O(nlog(n))

O(nlog(n))

不稳定

归并排序

O(nlog(n))

O(nlog(n))

O(nlog(n))

O(n)

稳定

1、选择排序

选择排序：选择最大/最小的数字，与未排好序的数组部分最前面的数字进行交换。

def select_sort(data):

for i in range(len(data)-1):

min_index = i

for j in range(i+1,len(data)):

if data[min_index]>data[j]:

min_index = j

data[min_index],data[i] = data[i],data[min_index]

return data

2、插入排序

插入排序：遍历n个数字，对于第i个数字，在0到i之间找到它的适合位置，替换进去。

def insert_sort(data):

for i in range(len(data)):

j = i

while j>0:

if data[j]

data[j-1],data[j] = data[j],data[j-1]

j -= 1

return data

3、冒泡排序

冒泡排序：反复对相邻的两个数字两两比较，从而将较大的数字排到后面去。

def bubble_sort(data):

for i in range(len(data)-1):

for j in range(len(data)-i-1):

if data[j]>data[j+1]:

data[j],data[j+1] = data[j+1],data[j]

return data

4、快速排序

快速排序：它选择一个基准值，将待排序数组分割成比基准值大的和比基准值小的两部分，对两部分再次选择基准值进行分割，最终完成排序。

def quick_sort(data):

if len(data)<2:

return data

base = data[0]

left = [i for i in data[1:] if i<=base]

right = [i for i in data[1:] if i>base]

return quick_sort(left) + [base] +quick_sort(right)

5、归并排序

归并排序：将原数组分割成二项子集，分别对各个子集进行排序。接着将两两二项子集进行合并，重复多次直至将整个数组合并回来。

def merge_sort(data):

if len(data)<2:

return data

middle = len(data)//2

left = merge_sort(data[:middle])

right = merge_sort(data[middle:])

return merge(left, right)

def merge(left, right):

res = []

left_index = right_index = 0

while left_index

if left[left_index]

res.append(left[left_index])

left_index += 1

else:

res.append(right[right_index])

right_index += 1

if left_index==len(left):

for i in right[right_index:]:

res.append(i)

if right_index == len(right):

for i in left[left_index:]:

res.append(i)

return res