冒泡排序、选择排序、插入排序、希尔排序

冒泡排序

基本思想

 

代码实现

# 冒泡排序
def bubble_sort(arr):length = len(arr) - 1for i in range(length):flag = Truefor j in range(length - i):if arr[j] > arr[j + 1]:temp = arr[j]arr[j] = arr[j + 1]arr[j + 1] = tempflag = Falseprint(f'第{i + 1}趟的排序结果为：', arr)if flag:# 代码优化，如果某一趟排序中没有发生交换，表示序列已经有序，可以提前结束循环breakbubble_sort([3, 9, -1, 10, 20])
bubble_sort([3, 9, -1, 10, -2])

选择排序

基本思想

 

代码实现

# 选择排序
def select_sort(arr):for i in range(len(arr) - 1):  # 进行 n-1 趟排序min = arr[i]index = ifor j in range(i + 1, len(arr)):if min > arr[j]:min = arr[j]index = jif index != i:arr[index] = arr[i]arr[i] = minprint(f'第{i + 1}趟排序结果：', arr)select_sort([3, 9, -1, 10, -2])
select_sort([3, 9, -1, 10, 20])

插入排序

基本思想

代码实现

# 插入排序
def insert_sort(arr):# for 循环遍历的是待排序的序列，即无序的序列for i in range(len(arr) - 1):insert_val = arr[i + 1]  # 待插入有序列表的值# 以 insert_index 位置为分割点，可以把 insert_index 及其之前的元素理解为已排序的序列# insert_index 以后的元素是无序序列insert_index = i  # 待插入值的前一个值的下标，即有序列表的最后一个元素的位置# while 循环遍历的是已有序的序列# insert_index >= 0 保证下标不越界# 从后往前访问有序列表# insert_val < arr[insert_index] 当待插入的值比有序列表中的值还小时，往前遍历有序列表，继续比较while insert_index >= 0 and insert_val < arr[insert_index]:# 将 arr[insert_index] 值后移，空出前面的位置存放待插入的值arr[insert_index + 1] = arr[insert_index]# 继续访问有序列表的前一个元素insert_index -= 1# 退出循环时，表示找到了插入的位置# 插入的位置为 insert_index + 1 ，因为 insert_index 位置要么为 -1 ，要么为比待插入值小的数arr[insert_index + 1] = insert_valprint(f'第{i + 1}个待插入的值插入后的结果', arr)insert_sort([3, 9, -1, 10, -2])
insert_sort([3, 9, -1, 10, 20])

希尔排序

基本思想

 

 

代码实现

# 希尔排序——交换法（效率低）
def shell_sort1(arr):"""# 以 [8, 9, 1, 7, 2, 3, 5, 4, 6, 0] 为例进行分析# 希尔排序的第一轮# 第一轮将数组分为 10 // 2 = 5 组for i in range(5, len(arr)):# 遍历各组中所有的元素（共5组，每组2个元素），步长为5j = i - 5while j >= 0:# 如果当前元素大于加上步长后的哪个元素，说明需要交换if arr[j] > arr[j + 5]:temp = arr[j]arr[j] = arr[j + 5]arr[j + 5] = tempj -= 5print('希尔排序的第一轮结果：', arr)# 希尔排序的第二轮 [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]# 第二轮将数组分为 5 // 2 = 2 组for i in range(2, len(arr)):# 遍历各组中所有的元素（共2组，每组5个元素），步长为5j = i - 2while j >= 0:# 如果当前元素大于加上步长后的哪个元素，说明需要交换if arr[j] > arr[j + 2]:temp = arr[j]arr[j] = arr[j + 2]arr[j + 2] = tempj -= 2print('希尔排序的第二轮结果：', arr)# 希尔排序的第三轮 [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]# 第三轮将数组分为 2 // 2 = 1 组for i in range(1, len(arr)):# 遍历各组中所有的元素（共1组，每组10个元素），步长为5j = i - 1while j >= 0:# 如果当前元素大于加上步长后的哪个元素，说明需要交换if arr[j] > arr[j + 1]:temp = arr[j]arr[j] = arr[j + 1]arr[j + 1] = tempj -= 1print('希尔排序的第三轮结果：', arr)"""# 交换法希尔排序gap = len(arr) // 2while gap > 0:for i in range(gap, len(arr)):# 遍历各组中所有的元素，步长为gapj = i - gapwhile j >= 0:# 如果当前元素大于加上步长后的哪个元素，说明需要交换if arr[j] > arr[j + gap]:temp = arr[j]arr[j] = arr[j + gap]arr[j + gap] = tempj -= gapprint('本轮排序结果：', arr)gap //= 2# 希尔排序——移位法（效率更高）
def shell_sort2(arr):# 移位法希尔排序，效率更高gap = len(arr) // 2while gap > 0:for i in range(gap, len(arr)):j = itemp = arr[j]if arr[j] < arr[j - gap]:while j - gap >= 0 and temp < arr[j - gap]:arr[j] = arr[j - gap]j -= gaparr[j] = tempprint('本轮排序结果：', arr)gap //= 2shell_sort1([8, 9, 1, 7, 2, 3, 5, 4, 6, 0])
shell_sort2([8, 9, 1, 7, 2, 3, 5, 4, 6, 0])