Python - 排序算法_Python 数据结构和算法教程

排序是指以特定格式排列数据。排序算法指定按特定顺序排列数据的方式。最常见的顺序是数字或字典顺序。

排序的重要性在于，如果数据以排序方式存储，则可以将数据搜索优化到非常高的级别。排序还用于以更具可读性的格式表示数据。下面我们看到 python 中排序的五种实现。

冒泡排序
合并排序
插入排序
Shell 排序
选择排序

冒泡排序

这是一种基于比较的算法，其中每对相邻元素都进行比较，如果元素不按顺序，则交换这些元素。

例

def bubblesort(list):

# 交换元素以按顺序排列
	 	for iter_num in range(len(list)-1,0,-1):
	 	 	 for idx in range(iter_num):
	 	 	 	 	if list[idx]>list[idx+1]:
	 	 	 	 	 	 temp = list[idx]
	 	 	 	 	 	 list[idx] = list[idx+1]
	 	 	 	 	 	 list[idx+1] = temp
list = [19,2,31,45,6,11,121,27]
bubblesort(list)
print(list)

输出

执行上述代码时，它会产生以下结果 -

[2, 6, 11, 19, 27, 31, 45, 121]

合并排序

合并排序首先将数组分成相等的两半，然后以排序的方式将它们合并。

例

def merge_sort(unsorted_list):
	 	if len(unsorted_list) <= 1:
	 	 	 return unsorted_list
# 找到中间点并将其分割
	 	middle = len(unsorted_list) // 2
	 	left_list = unsorted_list[:middle]
	 	right_list = unsorted_list[middle:]

	 	left_list = merge_sort(left_list)
	 	right_list = merge_sort(right_list)
	 	return list(merge(left_list, right_list))

# 合并已排序的两半
def merge(left_half,right_half):
	 	res = []
	 	while len(left_half) != 0 and len(right_half) != 0:
	 	 	 if left_half[0] < right_half[0]:
	 	 	 	 	res.append(left_half[0])
	 	 	 	 	left_half.remove(left_half[0])
	 	 	 else:
	 	 	 	 	res.append(right_half[0])
	 	 	 	 	right_half.remove(right_half[0])
	 	if len(left_half) == 0:
	 	 	 res = res + right_half
	 	else:
	 	 	 res = res + left_half
	 	return res
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(unsorted_list))

输出

执行上述代码时，它会产生以下结果 -

[11, 12, 22, 25, 34, 64, 90]

插入排序

插入排序涉及在排序列表中为给定元素查找正确的位置。因此，在开始时，我们比较前两个元素并通过比较它们来对它们进行排序。然后我们选择第三个元素，并在前两个排序的元素中找到它的适当位置。通过这种方式，我们将 Elements 放在适当的位置，逐渐地继续向已经排序的列表中添加更多元素。

例

def insertion_sort(InputList):
	 	for i in range(1, len(InputList)):
	 	 	 j = i-1
	 	 	 nxt_element = InputList[i]
# 将当前元素与下一个元素进行比较
	 	while (InputList[j] > nxt_element) and (j >= 0):
	 	 	 InputList[j+1] = InputList[j]
	 	 	 j=j-1
	 	InputList[j+1] = nxt_element
list = [19,2,31,45,30,11,121,27]
insertion_sort(list)
print(list)

输出

执行上述代码时，它会产生以下结果 -

[19, 2, 31, 45, 30, 11, 27, 121]

Shell 排序

Shell 排序涉及对彼此不同的元素进行排序。我们对给定列表的一大块子列表进行排序，并继续减小列表的大小，直到所有元素都排序完毕。下面的程序通过将间隙等于列表大小长度的一半来找到间隙，然后开始对其中的所有元素进行排序。然后我们不断重置间隙，直到整个列表都排序完毕。

例

def shellSort(input_list):
	 	gap = len(input_list) // 2
	 	while gap > 0:
	 	 	 for i in range(gap, len(input_list)):
	 	 	 	 	temp = input_list[i]
	 	 	 	 	j = i
# 对此差距的子列表进行排序
	 	while j >= gap and input_list[j - gap] > temp:
	 	 	 input_list[j] = input_list[j - gap]
	 	 	 j = j-gap
	 	 	 input_list[j] = temp
# 缩小下一个元素的间距
	 	gap = gap//2
list = [19,2,31,45,30,11,121,27]
shellSort(list)
print(list)

输出

执行上述代码时，它会产生以下结果 -

[2, 11, 19, 27, 30, 31, 45, 121]

选择排序

在选择排序中，我们首先在给定列表中找到最小值，然后将其移动到排序列表中。然后，我们对 unsorted 列表中的其余每个元素重复该过程。进入排序列表的下一个元素将与现有元素进行比较，并将其放置在正确的位置。因此，最后 unsorted 列表中的所有元素都被排序。

例

def selection_sort(input_list):
	 	for idx in range(len(input_list)):
	 	 	 min_idx = idx
	 	 	 for j in range( idx +1, len(input_list)):
	 	 	 	 	if input_list[min_idx] > input_list[j]:
	 	 	 	 	 	 min_idx = j
	 	 	 # 将最小值与比较值交换
	 	 	 input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]
l = [19,2,31,45,30,11,121,27]
selection_sort(l)
print(l)

输出

执行上述代码时，它会产生以下结果 -

[2, 11, 19, 27, 30, 31, 45, 121]

<< Python - 回溯 Python - 搜索算法 >>