排序是指将数据按照特定格式进行排列。排序算法定义了如何将数据按某种顺序组织起来。最常见的排序方式包括数值顺序和字典序（字母顺序）。
排序的重要性在于：如果数据以有序方式存储，那么数据的查找效率可以大幅提升。此外，排序也常用于以更易读的方式呈现数据。下面我们将介绍五种在 Python 中实现的排序算法：
- 冒泡排序（Bubble Sort）
- 归并排序（Merge Sort）
- 插入排序（Insertion Sort）
- 希尔排序（Shell Sort）
- 选择排序（Selection Sort）
冒泡排序（Bubble Sort）
冒泡排序是一种基于比较的算法，它依次比较相邻的两个元素，如果它们的顺序错误就交换位置。
示例
def bubblesort(lst):
# 通过交换元素来排序
for iter_num in range(len(lst)-1, 0, -1):
for idx in range(iter_num):
if lst[idx] > lst[idx+1]:
temp = lst[idx]
lst[idx] = lst[idx+1]
lst[idx+1] = temp
lst = [19, 2, 31, 45, 6, 11, 121, 27]
bubblesort(lst)
print(lst)
输出
执行上述代码后，输出结果为：
[2, 6, 11, 19, 27, 31, 45, 121]
归并排序（Merge Sort）
归并排序首先将数组分成相等的两半，然后以有序的方式将它们合并。
示例
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]
插入排序（Insertion Sort）
插入排序的核心思想是：为当前元素在已排序的部分中找到合适的位置。开始时比较前两个元素并排序；接着取第三个元素，在前两个已排序元素中找到其正确位置；依此类推，逐步将新元素插入到已排序序列中的适当位置。
示例
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
lst = [19, 2, 31, 45, 30, 11, 121, 27]
insertion_sort(lst)
print(lst)
输出
执行上述代码后，输出结果为：
[2, 11, 19, 27, 30, 31, 45, 121]
注意：原文示例中的输出有误，实际应为上述正确排序结果。
希尔排序（Shell Sort）
希尔排序是对插入排序的改进，它通过比较相距一定间隔（称为“gap”）的元素来进行排序。算法首先对较大的子列表进行排序，然后逐步缩小间隔，直到间隔为 1，此时相当于进行一次普通的插入排序，但此时列表已基本有序，效率更高。
示例
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
lst = [19, 2, 31, 45, 30, 11, 121, 27]
shellSort(lst)
print(lst)
输出
执行上述代码后，输出结果为：
[2, 11, 19, 27, 30, 31, 45, 121]
注意：原文示例中缩进有误，已在此修正。
选择排序（Selection Sort）
选择排序的工作原理是：首先在未排序序列中找到最小（或最大）元素，将其放到已排序序列的末尾；然后继续从未排序序列中找出下一个最小元素，重复此过程，直到所有元素均排序完毕。
示例
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]