| 排序算法 |
平均时间复杂度 |
最坏复杂度 |
空间复杂度 |
稳定性 |
| 冒泡排序 |
O(n2) |
O(n2) |
0(1) |
稳定 |
| 选择排序 |
O(n2) |
O(n2) |
0(1) |
不稳定 |
| 直接插入排序 |
O(n2) |
O(n2) |
0(1) |
稳定 |
| 快速排序 |
O(nlogn) |
O(n2) |
O(logn) |
不稳定 |
| 归并排序 |
O(nlogn) |
O(nlogn) |
O(1) |
稳定 |
| 堆排序 |
O(nlogn) |
O(nlogn) |
0(1) |
不稳定 |
| 希尔排序 |
O(nlogn) |
O(n8)1 |
O(1) |
不稳定 |
| 基数排序 |
O(lognB) |
O(lognB) |
O(n) |
稳定 |
| 二叉树排序 |
O(nlogn) |
O(nlogm) |
O(n) |
稳定 |
| 计数排序 |
O(n + k) |
O(n + k) |
O(n+ k) |
稳定 |
# -*- coding:UTF-8 -*-
def bubble_sort(sort_list):
"""
冒泡排序
:param sort_list:
:return:
"""
length = len(sort_list)
# 第一级遍历
for index in range(length):
# 第二级遍历
for j in range(1, length - index):
if sort_list[j - 1] > sort_list[j]:
# 交换两者数据，这里没用temp是因为python 特性元组。
sort_list[j - 1], sort_list[j] = sort_list[j], sort_list[j - 1]
return sort_list
# -*- coding:UTF-8 -*-
def selection_sort(sort_list):
"""
选择排序
:param sort_list:
:return:
"""
n = len(sort_list)
for i in range(0, n):
min_value = i
for j in range(i+1, n):
if sort_list[j] < sort_list[min_value]:
min_value = j
sort_list[min], sort_list[i] = sort_list[i], sort_list[min]
return sort_list
# -*- coding:UTF-8 -*-
def insert_sort(sort_list):
"""
插入排序
:param sort_list:
:return:
"""
n = len(sort_list)
for i in range(1, n):
# 后一个元素和前一个元素比较
# 如果比前一个小
if sort_list[i] < sort_list[i - 1]:
# 将这个数取出
temp = sort_list[i]
# 保存下标
index = i
# 从后往前依次比较每个元素
for j in range(i - 1, -1, -1):
# 和比取出元素大的元素交换
if sort_list[j] > temp:
sort_list[j + 1] = sort_list[j]
index = j
else:
break
# 插入元素
sort_list[index] = temp
return sort_list
# -*- coding:UTF-8 -*-
def shell_sort(sort_list):
"""
希尔排序
:param sort_list:
:return:
"""
n = len(sort_list)
# 初始步长
gap = n // 2
while gap > 0:
for i in range(gap, n):
# 每个步长进行插入排序
temp = sort_list[i]
j = i
# 插入排序
while j >= gap and sort_list[j - gap] > temp:
sort_list[j] = sort_list[j - gap]
j -= gap
sort_list[j] = temp
# 得到新的步长
gap = gap // 2
return sort_list
# -*- coding:UTF-8 -*-
def quick_sort(arr):
"""
快速排序
:param arr:
:return:
"""
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
return quick_sort([x for x in arr[1:] if x < pivot]) + \
[pivot] + \
quick_sort([x for x in arr[1:] if x >= pivot])