文章目录
- 1. 选择排序
- 1.1 思想
- 1.2 实现
- 2. 冒泡排序
- 2.1 思想
- 2.2 实现
1. 选择排序
1.1 思想
选择排序的思想很简单,如上图所示。在每一次遍历子数组的过程中,选择最小的和子数组的第一位交换。子数组的选择从一开始的整个数组,到后面范围逐渐向原数组最后一位缩减。复杂度
O
(
n
2
)
O(n^2)
O(n2)
1.2 实现
def swap(arr, i, j):
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
if __name__ == '__main__':
arr = [6, 3, 1, 4, 2, 5]
print("原数组:" + str(arr))
for i in range(0, len(arr) - 1):
min_idx = i
for j in range(i + 1, len(arr)):
min_idx = j if arr[j] < arr[min_idx] else min_idx
swap(arr, i, min_idx)
print("排序后的数组:" + str(arr))
main方法里是对选择排序的实现。选择排序就是,从剩下的数里面选择最小/最大的数,与当前子数组的第一位数进行交换。
2. 冒泡排序
2.1 思想
如上图所示,冒泡排序的思想是,在每一轮将最大的数换到子数组的最后一位上去。通过多地置换,最终实现数组的有序。复杂度
O
(
n
2
)
O(n^2)
O(n2)
2.2 实现
def swap(arr, i, j):
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
if __name__ == '__main__':
arr = [6, 3, 1, 4, 2, 5]
print("排序前的数组:" + str(arr))
for i in range(len(arr) - 1, 0, -1):
for j in range(0, i):
if arr[j] > arr[j + 1]:
swap(arr, j, j + 1)
print("排序后的数组:" + str(arr))