def select_sort(alist):
for i in range(len(alist) - 1):
min_index = i
for j in range(i + 1, len(alist)):
if alist[j] < alist[min_index]:
min_index = j
alist[i], alist[min_index] = alist[min_index], alist[i]
return alist
def insertion_sort(alist):
# 从索引为 1 的值开始从后向前扫描
for i in range(1, len(alist)):
current_value = alist[i]
position = i
# 如果前一个数大于当前值则将前一个数向右移动一位,直到找到前一个数小于当前值得位置,将该位置的值设为当前值
while position > 0 and alist[position - 1] > current_value:
alist[position] = alist[position - 1]
position -= 1
alist[position] = current_value
return alist
def shell_sort(alist):
sub_list_count = len(alist) // 2
while sub_list_count > 0:
for start_position in range(sub_list_count):
alist = gap_insertion_sort(alist, start_position, sub_list_count)
print('After increments of size', sub_list_count, 'The list is', alist)
sub_list_count = sub_list_count // 2
return alist
def gap_insertion_sort(alist, start, gap):
for i in range(start + gap, len(alist), gap):
current_value = alist[i]
position = i
while position >= gap and alist[position - gap] > current_value:
alist[position] = alist[position - gap]
position = position - gap
alist[position] = current_value
return alist
可视化
舞动的排序算法之希尔排序
快速排序
工作原理
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。步骤如下: