6种排序

  • 各种排序的简介
  • 冒泡排序
  • 选择排序
  • 直接插入排序
  • 希尔排序
  • 归并排序
  • 快速排序

各种排序的简介

(声明:最基础的排序公认有 8 种,我目前了解并学习的只有当前的 6 种,剩下的还有堆排序桶排序基数排序等等,算法的范围很大,需要慢慢学习)

冒泡排序实现代码

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
# 类冒泡排序,并非正统的冒泡排序,是效率最低的排序方法
def BobbleSort0(arr):
for i in range(len(arr) - 1):
for j in range(i + 1, len(arr)):
if arr[i] > arr[j]:
arr[i], arr[j] = arr[j], arr[i]


# 冒泡排序方法 1
def BobbleSort1(arr):
# 指定冒泡的顶点位置
for i in range(len(arr)):
# 开始冒泡
for j in range(len(arr) - 1, i, -1):
# 满足条件就开始交换
if arr[j] < arr[j - 1]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]


# 优化的冒泡排序
def BobbleSort2(arr):
# 指定一个标志位,表示是否有交换操作
flag = True
# 指定冒泡的顶点位置
for i in range(len(arr)):
if flag:
flag = False
# 开始冒泡
for j in range(len(arr) - 1, i, -1):
if arr[j] < arr[j - 1]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
# 发生交换,修改标志位
flag = True


if __name__ == '__main__':
arr = [1, 3, 2, 5, 7, 4, 9, 0, 8, 6]
BobbleSort2(arr)
print(arr)

选择排序实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def SelectSort0(arr):
# 第一重循环选择位置
for i in range(len(arr) - 1):
# 选择当前位置
min = i
for j in range(i + 1, len(arr)):
# 满足条件就重设当前位置
if arr[min] > arr[j]:
min = j
# 如果选择值发生了改变说明需要交换位置了
if i != min:
arr[min], arr[i] = arr[i], arr[min]


if __name__ == '__main__':
arr = [1, 3, 2, 5, 7, 4, 9, 0, 8, 6]
SelectSort0(arr)
print(arr)

直接插入排序实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def InsertSort0(arr):
# 从第一位选择一个值向前插入
for i in range(1, len(arr)):
# 向前插入该值知道满足规律
for j in range(i, 0, -1):
# 找到合适的位置插入
if arr[j] < arr[j - 1]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]


if __name__ == '__main__':
arr = [1, 3, 2, 5, 7, 4, 9, 0, 8, 6]
InsertSort0(arr)
print(arr)

希尔排序实现代码

简要说明:希尔排序就是插入排序的改进版本,因为直接插入排序面向的本来就是基本有序全局无序的序列,如果全局无序,就会造成效率变低,所以就引入了希尔排序,先按照一定的步长排序,然后逐渐减少步长直至步长为 1,提高了一定的效率,但是时间复杂度和直接插入排序相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def ShellSort(arr):
# 设置第一次的步长为排序序列的长度的一半
dk = int(len(arr) / 2)
# 保证最后的步长一定为 1
while dk >= 1:
# 这里就是直接插入排序
for i in range(dk, len(arr), dk):
for j in range(i, 0, -dk):
if arr[j] < arr[j - dk]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
# 重设步长为当前步长的一半
dk = int(dk / 2)


if __name__ == '__main__':
arr = [1, 3, 2, 5, 7, 4, 9, 0, 8, 6]
ShellSort(arr)
print(arr)

归并排序实现代码

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
44
45
46
47
def MergeSort(arr):
# 保证最后切割出来的值只有一个
if len(arr) == 1:
return arr

# 获得中间位置
mid = len(arr) // 2

# 获得左边的序列
left = arr[:mid]
# 获得右边的序列
right = arr[mid:]

# 递归切割左边序列
ll = MergeSort(left)
# 递归切割右边序列
rl = MergeSort(right)

# 合并左右序列
return Merge(ll, rl)


# 合并(归并两个序列)
def Merge(ll, rl):
# 用于存储结果的容器
result = []

# 归并过程
while len(ll) > 0 and len(rl) > 0:
if ll[0] < rl[0]:
result.append(ll.pop(0))
else:
result.append(rl.pop(0))

# 合并剩下的左序列
result += ll
# 合并剩下的右序列
result += rl

# 返回合并的序列
return result


if __name__ == '__main__':
arr = [1, 3, 2, 5, 7, 4, 9, 0, 8, 6]
arr = MergeSort(arr)
print(arr)

快速排序实现代码

简要说明:归并排序和快速排序使用的都是分治策略,从局部有序到全局有序,但是实现的方法不同

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
def QuickSort(arr, left, right):
# 如果左指针等于右指针说明无法继续分区
if left >= right:
return

# 获得一个分区节点
index = left
# 存储分区节点的值
value = arr[left]

# 快速排序核心
# 将分区内的序列按照小的放到节点左边,大的放到节点右边
for i in range(left, right + 1):
if value > arr[i]:
arr[index] = arr[i]
arr[i] = arr[index + 1]
index = index + 1

# 重新放置分区节点的值
arr[index] = value

# 递归调用快排函数
QuickSort(arr, left, index - 1)
QuickSort(arr, index + 1, right)


if __name__ == '__main__':
arr = [1, 3, 2, 5, 7, 4, 9, 0, 8, 6]
QuickSort(arr, 0, len(arr) - 1)
print(arr)
坚持原创技术分享,您的支持将鼓励我继续创作!