时间复杂度总结排序算法代码（Python实现）
冒泡排序插入排序希尔排序选择排序堆排序快速排序归并排序
时间复杂度总结| 算法 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O ( n ) O(n) O(n) | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( 1 O(1 O(1） | 稳定 |
| 选择排序 | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 不稳定 |
| 插入排序 | O ( n ) O(n) O(n) | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( 1 O(1 O(1） | 稳定 |
| 希尔排序 | / / / | / / / | O ( n 1.3 ) O(n^{1.3}) O(n1.3) | O ( 1 ) O(1) O(1) | 不稳定 |
| 堆排序 | O ( n l o g n ) O(nlogn) O(nlogn) | O ( n l o g n ) O(nlogn) O(nlogn) | O ( n l o g n ) O(nlogn) O(nlogn) | O ( 1 O(1 O(1） | 不稳定 |
| 快速排序 | O ( n l o g n ) O(nlogn) O(nlogn) | O ( n 2 ) O(n^2) O(n2) | O ( n l o g n ) O(nlogn) O(nlogn) | O ( l o g n ) O(logn) O(logn) | 不稳定 |
| 归并排序 | O ( n l o g n ) O(nlogn) O(nlogn) | O ( n l o g n ) O(nlogn) O(nlogn) | O ( n l o g n ) O(nlogn) O(nlogn) | O ( n ) O(n) O(n) | 稳定 |
# 排序：就是将数据按从小到大或从大到小进行排列
# 冒泡排序
# 思路：从数据开头开始，每个数据和相邻的数据进行比较，若当前的数据比后一个数据小，则进行交换
# 一直到数据末尾前一个数据，这样为一轮，每一轮至少可以使得最后一个数据是在其正确的位置上，
# 所以最多只需要经过n-1轮即可保证数据有序
# 同时为了提高效率，可以进行记录，若在某一轮比较中没有发生一次交换，就说明数据已经有序，不需要再进行排序
# 稳定性：稳定
# 空间复杂度：原地排序 O(1)
# 时间复杂度：最好：O(n)
# 最坏：O(n^2)
# 平均：O(n^2)
def bubble_sort(date):
n = len(date)
l = n - 1
for i in range(l):
flag = 1
for j in range(l - i):
if date[j] > date[j + 1]:
# 交换数据
temp = date[j]
date[j] = date[j + 1]
date[j + 1] = temp
flag = 0
if flag == 1:
break
return date
if __name__ == "__main__":
# 要进行排序的数组列表
date1 = [4, 5, 10, 3, 1, 5, 3, 89, -1]
date2 = [1]
date3 = [1, 2, 3]
date4 = []
print(bubble_sort(date1))
print(bubble_sort(date2))
print(bubble_sort(date3))
print(bubble_sort(date4))
插入排序
# 插入排序
# 思路：将数据分为有序区和无序区，每次将无序区的第一个数据插入到有序区中，直到无序区为空
# 插入方法不断向前比较，直到要插入的数据大于等于前一个数据，即可进行插入
# 稳定性：稳定
# 空间复杂度：O(1)
# 时间复杂度：最好：O(n)
# 最差：O(n^2)
# 平均：O(n^2)
def insertion_sort(date):
n=len(date)
l=n-1
for i in range(1,n):
temp=date[i]
insert_index=i
while insert_index>0:
if temp>=date[insert_index-1]:
break
else:
date[insert_index]=date[insert_index-1]
insert_index=insert_index-1
# 插入数据
date[insert_index]=temp
return date
if __name__=="__main__":
# 要进行排序的数组列表
date1 = [4, 5, 10, 3, 1, 5, 3, 89, -1]
date2 = [1]
date3 = [1, 2, 3]
date4 = []
print(insertion_sort(date1))
print(insertion_sort(date2))
print(insertion_sort(date3))
print(insertion_sort(date4))
希尔排序
# 希尔排序
# 思路：希尔排序其实就是插入排序的优化，由于插入排序在数据有序的情况下时间复杂度为O(n),效率很高，
# 希尔排序就是先进行多次小规模大间隔的插入排序，先使得数据变得有序，再通过不断缩小间隔，直到间隔
# 为1，保证数据有序
# 稳定性：不稳定
# 空间复杂度：O(1)
# 时间复杂度：平均O(n^1.3)
def shell_sort(date):
n = len(date)
l = n - 1
# gap:数据的间隔
gap=int(n/2)
while gap>=1:
for i in range(gap):
for m in range(i+gap,n,gap):
temp=date[m]
insert_index=m
while insert_index>i:
if temp>=date[insert_index-gap]:
break
else:
date[insert_index]=date[insert_index-gap]
insert_index-=gap
# 插入数据
date[insert_index]=temp
gap=int(gap/2)
return date
import random
import time
if __name__=="__main__":
# 要进行排序的数组列表
date = [4, 5, 10, 3, 1, 5, 3, 89, -1]
print(shell_sort(date))
date=[]
for i in range(10000):
date.append(random.randint(0,1000000))
start = time.perf_counter()
date=shell_sort(date)
end = time.perf_counter()
print(end - start)
for i in range(len(date)-2):
if date[i]>date[i+1]:
print(i)
print("shell_sort false")
选择排序
# 选择排序
# 思路：将数据分为有序区和无序区，初始有序区为空，所有数据都在无序区，每次从无序区选择一个最小的数据和无序区第一个数据交换，
# 有序区范围加1，无序区范围减1。重复上述操作直到无序区只剩下一个数据
# 稳定性：稳定
# 空间复杂度：O(1)
# 时间复杂度：O(n^2)
def selecttion_sort(date):
n=len(date)
l=n-1
for i in range(l):
min_index=i
for j in range(i+1,n):
if date[min_index]>date[j]:
min_index=j
# 交换数据
temp=date[min_index]
date[min_index]=date[i]
date[i]=temp
return date
if __name__=="__main__":
# 要进行排序的数组列表
date1 = [4, 5, 10, 3, 1, 5, 3, 89, -1]
date2 = [1]
date3 = [1, 2, 3]
date4 = []
print(selecttion_sort(date1))
print(selecttion_sort(date2))
print(selecttion_sort(date3))
print(selecttion_sort(date4))
堆排序
# 堆排序
# 堆；完全二叉树，除了最后一层，每一层的节点都满了，所以用数组存储极为方便。
# 分为最大堆和最小堆（最大堆：父亲节点比子节点的数据大，子节点的数据比父亲节点的数据小）
# 建堆：方法1:不断从堆的尾部插入数据，再通过向上比较交换使得新插入的数据在堆中处于正确的位置
# 方法2：从最后一个节点的父亲节点开始，不断向前进行堆化，直到根节点。堆化就是比较当前节点及其子节点的数据
# 令三者中较大的数据和父亲节点交换数据，使其满足堆的特性。若发生了交换则还需要对交换之后的子节点
# 继续调用堆化操作，直到不发生交换或者到达叶节点
# 删除根节点：令根节点和最后一个节点交换，然后对新的根节点进行堆化操作，使得新的根节点位于其正确的位置上
# 堆排序：先对数据进行建堆，再进行删除根节点操作，删除一次根节点就相当于将堆中最大的数据放到堆的末尾，当
# 进行了n-1次删除根节点操作，数据就有序了
# 稳定性：不稳定
# 空间复杂度：O(1)
# 时间复杂度：建堆：O(n) 删除根节点O(logn)
# 总：O(nlogn)
def heap_sort(date):
n=len(date)
l=n-1
# 父亲节点下标为n 左子节点：(n+1)*2-1 右子节点：O(n+1)*2
# 子节点下标为n 父亲接点：int((n-1)/2)
# 建堆
m=int((l-1)/2)
while m>=0:
next_=m
while True:
next=get_heap(date,next_,l)
if next==next_:
break
else:
next_=next
m=m-1
# 堆排序
for i in range(l):
del_heap_top(date,l-i)
return date
def get_heap(date,m,n):
left=(m+1)*2-1
right=(m+1)*2
max_index=m
if left<=n and date[left]>date[max_index]:
max_index=left
if right<=n and date[right]>date[max_index]:
max_index=right
# 交换数据
temp=date[m]
date[m]=date[max_index]
date[max_index]=temp
return max_index
# 删除根节点
def del_heap_top(date,n):
# 交换根节点和最后一个节点
temp=date[n]
date[n]=date[0]
date[0]=temp
# 更新的堆的范围
n=n-1
father_index=0
while True:
next=get_heap(date,father_index,n)
if next==father_index:
break
else:
father_index=next
import random, time
if __name__ == "__main__":
# # 要进行排序的数组列表
# date = [15, 29, 10]
# print(heap_sort(date))
date = []
for i in range(10000):
date.append(random.randint(0, 1000000))
start = time.perf_counter()
date = heap_sort(date)
end = time.perf_counter()
print(end - start)
for i in range(len(date) - 2):
if date[i] > date[i + 1]:
print("heap_sort false")
快速排序
# 快速排序
# 思路：利用分治的思想。选择一个基准值，将所有小于等于其的数据放到基准值的左侧，将大于其的数据放到其右侧
# 再对左侧和右侧的数据重复上述操作。截止条件为数据长度为1
# 稳定性：不稳定
# 空间复杂度：O(logn)
# 时间复杂度：最好O(nlogn)
# 最坏O(n^2)
# 平均O(nlogn)
def quick_sort(date):
n=len(date)
l=n-1
quick_sort_func(date,0,l)
return date
def quick_sort_func(date,m,n):
if m>=n:
return
else:
# 选取第一个数据为基准值
standard=date[m]
i=m+1
j=n
while i<=j:
if date[i]>standard and date[j]<=standard:
# 交换数据
temp=date[i]
date[i]=date[j]
date[j]=temp
if date[i]<=standard:
i=i+1
if date[j]>standard:
j=j-1
# 将基准值至于正确的位置
temp=date[m]
date[m]=date[j]
date[j]=temp
# 递归处理基准值两侧的数据
quick_sort_func(date,m,j-1)
quick_sort_func(date,j+1,n)
import time,random
if __name__=="__main__":
# # 要进行排序的数组列表
# date = [0,5, 10, 3, 1, 5, 3, 89, -1]
# print(quick_sort(date))
date = []
for i in range(10000):
date.append(random.randint(0, 1000000))
start = time.perf_counter()
quick_sort(date)
end = time.perf_counter()
print(end - start)
for i in range(len(date)-2):
if date[i]>date[i+1]:
print("quick_sort false")
print(i)
归并排序
# 归并排序
# 思路：利用分治的思想。将对数据的排序分解为分别对两部分数据进行排序，再合并两个有序序列
# 终止条件：数据长度小于等于1
# 稳定性：稳定
# 空间复杂度：O(n)
# 时间复杂度：O(nlogn) T(n)=2T(N/2)+n
def merge_sort(date):
if len(date) < 2:
return date
else:
middle = int(len(date) / 2)
left = merge_sort(date[0:middle])
right = merge_sort(date[middle:])
return merge(left, right)
def merge(left, right):
left_n = len(left)
right_n = len(right)
date = []
i = 0
j = 0
while i < left_n and j < right_n:
if left[i] <= right[j]:
date.append(left[i])
i = i + 1
else:
date.append(right[j])
j = j + 1
while i < left_n:
date.append(left[i])
i = i + 1
while j < right_n:
date.append(right[j])
j = j + 1
return date
import random, time
if __name__ == "__main__":
# # 要进行排序的数组列表
# date = [15, 29, 10]
# print(heap_sort(date))
date = []
for i in range(10000):
date.append(random.randint(0, 10000))
start = time.perf_counter()
date = merge_sort(date)
end = time.perf_counter()
print(end - start)
for i in range(len(date) - 2):
if date[i] > date[i + 1]:
print("merge_sort false")
print(i)
