一些排序算法的Python实现

最近总结了一下一些经典的排序算法,并用 Python 算法自己实现了一遍,同时我把代码上传到了 GitHub 上。
在这边,我也顺便写篇博客贴一下排序算法代码。Python 语法简单清晰,同时代码中都已经写上了注释,了解算法原理的话,非常好看懂,我就不另外详细解释了。

插入类排序

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
def insert_sort(array):
"""
直接插入排序
"""
for i in range(1, len(array)):
value = array[i] # 复制当前元素,用来比较
j = i - 1
# 一边寻找插入位置,一边移动
while j >= 0 and array[j] > value:
array[j + 1] = array[j] # 当前比较元素比准备插入的元素大,则当前元素后移
j -= 1
array[j + 1] = value # 找到插入位置

折半插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def BInsert_sort(array):
"""
折半插入排序
"""
for i in range(1, len(array)):
value = array[i]
left = 0
right = i - 1
# 先寻找插入位置
while left <= right:
mid = (left + right) / 2
if array[mid] > value: # 插入点在低半区
right = mid - 1
else: # 插入点在高半区
left = mid + 1
# 上述循环结束之时,一定是 right + 1 == left,该 left 的位置即为插入点
# 插入点及之后的元素位置后移
for j in range(i, left, -1):
array[j] = array[j - 1]
array[left] = value

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def shell_sort(array):
"""
希尔排序
"""
gap = len(array) / 2 # 步长,初始取数组长度整除2,之后一直整除2,直到为0
while gap > 0:
# 以下排序方法与直接插入排序相同,区别就是步长从 1 变为了每次不同的 gap,最后一次步长必定为 1,就变成了普通的直接插入排序
for i in range(gap, len(array)):
value = array[i]
j = i - gap
while j >= 0 and array[j] > value:
array[j + gap] = array[j]
j -= gap
array[j + gap] = value
gap = gap / 2 # 修改步长

交换类排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
def bubble_sort(array):
"""
冒泡排序
"""
for i in range(len(array)):
swaped = False
# 从后往前冒泡,小的元素浮到前面
for j in range(len(array) - 1, i, -1):
if array[j] < array[j - 1]:
array[j - 1], array[j] = array[j], array[j - 1]
swaped = True
if swaped is False: # 最后一趟没有交换任何元素,则表明数组已经有序
break

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def quick_sort(array):
"""
快速排序
"""
qsort(array, 0, len(array) - 1)


def qsort(array, left, right):
"""
递归排列子序列
"""
if left < right:
pivot = partition(array, left, right) # 将数组划分为左右两部分,并找到枢轴
qsort(array, left, pivot - 1)
qsort(array, pivot + 1, right)


def partition(array, left, right):
"""
将数组序列分为左右两部分,找到枢轴元素,枢轴元素的左边都不大于枢轴的值,右边的元素都不小于枢轴的值
枢轴元素当前所在的位置都是它在最终有序序列中的位置
返回枢轴索引
"""
pivot = left # 起始枢轴设为最左边的元素的索引
pivot_value = array[left]
for i in range(left + 1, right + 1):
# 如果当前元素比枢轴元素小,就将枢轴往右移动一格,然后与该元素互换位置
if array[i] < pivot_value:
pivot += 1
if pivot != i:
array[pivot], array[i] = array[i], array[pivot]
# 将枢轴元素交换到正确的位置上
array[left], array[pivot] = array[pivot], array[left]
return pivot

选择类排序

简单选择排序

1
2
3
4
5
6
7
8
9
10
11
12
def select_sort(array):
"""
简单选择排序
"""
for i in range(len(array)):
min_index = i
# 从无序数列中找出最小的元素的索引
for j in range(i + 1, len(array)):
if array[j] < array[min_index]:
min_index = j
# 将最小元素与无序数列的第一个元素交换位置
array[i], array[min_index] = array[min_index], array[i]

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def heap_sort(array):
"""
堆排序
"""
# 建初始堆
build_heap(array)
# 开始排序
for i in range(len(array) - 1, -1, -1):
array[0], array[i] = array[i], array[0] # 将堆顶记录与无序子序列的最后一个元素交换位置
adjust_heap(array, 0, i - 1) # 继续排列剩余的无序子序列


def build_heap(array):
"""
建初始堆
"""
first_node = len(array) / 2 - 1 # 从第一个非叶子节点开始,从下往上,调整元素建堆
for i in range(first_node, -1, -1):
adjust_heap(array, i, len(array) - 1)


def adjust_heap(array, head, tail):
"""
假设 array 数组中,从 head - 1 到 tail 的元素均满足堆的定义,现调整 head 对应元素使之成为大顶堆
"""
while True:
left_child = 2 * head + 1
right_child = 2 * head + 2
# 当前 head 节点已经没有子节点,则表明已到达最下层,调整堆完成
if left_child > tail:
break
# 寻找两个孩子节点中较大的节点
max_child = left_child
if left_child < tail and array[left_child] < array[right_child]:
max_child = right_child
# 如果较大的孩子节点比父节点大,则与父节点交换位置
if array[max_child] > array[head]:
array[max_child], array[head] = array[head], array[max_child]
# 如果父节点比子节点大,则不需要调整,说明后续都满足堆定义,直接完成
else:
break
# 以刚才调整的孩子节点作为父节点,继续向下调整
head = max_child

归并类排序

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def merge_sort(array):
"""
归并排序
"""
msort(array, 0, len(array) - 1)


def msort(array, left, right):
"""
递归二分原数组
"""
if left < right: # left == right 的时候,原数组已经划分为单个元素了
mid = (left + right) / 2
msort(array, left, mid) # 左半部分继续二分
msort(array, mid + 1, right) # 右半部分继续二分
merge(array, left, mid, right) # 两两合并 left ~ mid, mid + 1 ~ right


def merge(array, left, mid, right):
"""
归并
"""
tmp = [] # 临时数组
i = left
j = mid + 1
while i <= mid and j <= right: # 两个数组按顺序合并
if array[i] <= array[j]:
tmp.append(array[i])
i += 1
else:
tmp.append(array[j])
j += 1
# 其中一个数组合并完了,就把另一个数组的剩余部分拼接上去
while i <= mid:
tmp.append(array[i])
i += 1
while j <= right:
tmp.append(array[j])
j += 1
# 将合并好的临时数组替换到原数组上
for k in range(len(tmp)):
array[left + k] = tmp[k]