冒泡排序

稳定排序,时间复杂度: $ O(n^{2}) $ ,额外空间: $ O(1) $ ,基于比较

1
2
3
4
5
6
7
8
9
10
11
12
def bubble_sort(array):
# 从数组末尾到数组头遍历
for i in range(len(array) - 1, 0, -1):
flag = True # 排序是否结束的标准
for j in range(0, i):
if (array[j] < array[j + 1]):
flag = False
array[j], array[j + 1] = array[j + 1], array[j]
# 如果一次排序未发生数据交换,则说明排序结束
if flag:
return array
return array

选择排序

稳定,时间复杂度:$ O(n^{2}) $,额外空间:$O(1)$,基于比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def selection_sort(list):
N = len(list)
# 从数组头到尾
for i in range(N - 1):
# 设第一个值为最小
min_index = i
# 从外层循环+1到数组尾,找到最小的值的下标
for j in range(i + 1, N):
if (list[j] < list[min_index]):
min_index = j
# 交换到一次循环找到的最小位置
if min_index != i:
list[i], list[min_index] = list[min_index], list[i]
return list

插入排序

稳定,时间复杂度:$O(n^{2})$,空间复杂度:$O(1)$,基于比较

1
2
3
4
5
6
7
8
9
10
11
def insertion_sort(list):
n = len(list)
if n == 1:
return list
# 从第二个值到末尾,递增
for i in range(1, n):
# 从外层循环到数组头,递减
for j in range(i, 0, -1):
# 比较前一个和后一个并交换
if list[j] < list[j - 1]: list[j], list[j - 1] = list[j - 1], list[j]
return list

快速排序

不稳定,时间复杂度:$O(nlog n)$,空间复杂度:$O(log n)$,基于比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def quick_sort(list,left,right):
if left >= right :
return
index = partition(list,left,right)
quick_sort(list,left,index-1)
quick_sort(list,index+1,right)

def partition(list,left,right):
key = list[left]
while left < right:
while list[right] >= key and left < right:
right -= 1
if left < right:
list[left],list[right] = list[right],list[left]
while list[left] < key and left < right:
left += 1
if left < right:
list[left],list[right] = list[right],list[left]
return left

if __name__ == '__main__':
list = [6,1,4,8,5,3,5,5,6]
quick_sort(list,0,len(list)-1)
print list