【python】sort函数的时间+空间复杂度（包括py内
置.sort（））
python有个内置的nums.sort()排序函数，其内部实现机制为：Timesort
最坏时间复杂度为：O（n log n）
空间复杂度为：O（n）
顺便整理⼀下其他的各种排序算法：
排序算法平均时间复杂度最好情况最坏情况空间复杂度排序⽅式稳定性插⼊排序O(n²)O(n)O(n²)O(1)In-place稳定冒泡排序O(n²)O(n)O(n²)O(1)In-place稳定选择排序O(n²)O(n²)O(n²)O(1)In-place不稳定
排序算法平均时间复杂度最好情况最坏情况空间复杂度排序⽅式稳定性快速排序O(n log n)O(n log n)O(n²)O(log n)In-place不稳定
希尔排序O(n log n)O(n log n)O(n log n)O(1)In-place不稳定
堆排序O(n log n)O(n log n)O(n log n)O(1)In-place不稳定
归并排序O(n log n)O(n log n)O(n log n)O(n)Out-place稳定直接插⼊排序：
def insert_sort(array):
for i in range(len(array)):
for j in range(i):
if array[i] < array[j]:
array.insert(j, array.pop(i))
break
return array
希尔排序：
def shell_sort(array):
gap = len(array)
while gap > 1:
gap = gap // 2
for i in range(gap, len(array)):
for j in range(i % gap, i, gap):
if array[i] < array[j]:
array[i], array[j] = array[j], array[i]
return array
选择排序：
def select_sort(array):
for i in range(len(array)):
x = i  # min index
for j in range(i, len(array)):
if array[j] < array[x]:
x = j
array[i], array[x] = array[x], array[i]
return array
快速排序python实现堆排序：
def heap_sort(nums):
# 调整堆
# 迭代写法
def adjust_heap(nums, startpos, endpos):
newitem = nums[startpos]
pos = startpos
childpos = pos * 2 + 1
while childpos < endpos:
rightpos = childpos + 1
if rightpos < endpos and nums[rightpos] >= nums[childpos]:                childpos = rightpos
if newitem < nums[childpos]:
nums[pos] = nums[childpos]
pos = childpos
childpos = pos * 2 + 1
else:
break
nums[pos] = newitem
# 递归写法
def adjust_heap(nums, startpos, endpos):
pos = startpos
chilidpos = pos * 2 + 1
if chilidpos < endpos:
rightpos = chilidpos + 1
if rightpos < endpos and nums[rightpos] > nums[chilidpos]:                chilidpos = rightpos
if nums[chilidpos] > nums[pos]:
nums[pos], nums[chilidpos] = nums[chilidpos], nums[pos]                adjust_heap(nums, pos, endpos)
def heap_sort(array):
def heap_adjust(parent):
child = 2 * parent + 1  # left child
while child < len(heap):
if child + 1 < len(heap):
if heap[child + 1] > heap[child]:
child += 1  # right child
if heap[parent] >= heap[child]:
break
heap[parent], heap[child] = \
heap[child], heap[parent]
parent, child = child, 2 * child + 1
heap, array = py(), []
for i in range(len(heap) // 2, -1, -1):
heap_adjust(i)
while len(heap) != 0:
heap[0], heap[-1] = heap[-1], heap[0]
array.insert(0, heap.pop())
heap_adjust(0)
return array
冒泡排序：
def bubble_sort(array):
for i in range(len(array)):
for j in range(i, len(array)):
if array[i] > array[j]:
array[i], array[j] = array[j], array[i]
return array
快速排序：
def Quick_sort(num_list):
'''
快速排序，时间复杂度：O(nlog₂n)，空间复杂度：O(nlog₂n)，不是稳定排序
'''
if len(num_list)<2:
return num_list
left_list = []  #存放⽐基准结点⼩的元素
right_list = []  #存放⽐基准元素⼤的元素
base_node = num_list.pop(0) #在这⾥采⽤pop()⽅法的原因就是需要移除这个基准结点，并且赋值给base_node这个变量                                #在这⾥不能使⽤del()⽅法，因为删除之后⽆法再赋值给其他变量使⽤，导致最终数据缺失
#快排每轮可以确定⼀个元素的位置，之后递归地对两边的元素进⾏排序
for one_num in num_list:
if one_num < base_node:
left_list.append(one_num)
else:
right_list.append(one_num)
return Quick_sort(left_list) + [base_node] + Quick_sort(right_list)
归并排序：
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
# 分
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
# 合并
return merge(left, right)
def merge(left, right):
res = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res += left[i:]
res += right[j:]
return res
基数排序：
def radix_sort(array):
bucket, digit = [[]], 0
while len(bucket[0]) != len(array):
bucket = [[], [], [], [], [], [], [], [], [], []]
for i in range(len(array)):
num = (array[i] // 10 ** digit) % 10
bucket[num].append(array[i])
array.clear()
for i in range(len(bucket)):
array += bucket[i]
digit += 1
return array
参考⼤佬整理内容，附链接：