排序概述及Python实现
1. 定义与目的
排序是将一组数据按照特定顺序排列的过程，其目的是为了便于数据的查找和处理，提高数据处理效率。
2. 分类
排序可以分为内部排序和外部排序。
2.1 内部排序
内部排序是指所有数据都在内存中进行排序。例如，对一个列表中的整数进行排序。
# 内部排序示例：对列表进行排序
lst = [5, 2, 8, 1, 9]
lst.sort()
print(lst)2.2 外部排序
外部排序是指数据量过大，部分数据存储在外存中，需要分批调入内存进行排序。比如对一个大型文件中的数据进行排序，无法一次性将所有数据读入内存。
3. 算法好坏衡量标准
衡量排序算法的好坏可以从空间效率、稳定性和时间效率三个方面来评估。
4. 内部排序方法
内部排序是指待排序的数据元素全部存放在计算机内存中的排序算法。常见的内部排序方法有插入排序、交换排序、选择排序、归并排序和基数排序等。
4.1 插入排序
插入排序的基本思想是将待排序的元素插入到已排序的部分序列中，逐步构建有序序列。
直接插入排序
def insertion_sort(lst):
for i in range(1, len(lst)):
key = lst[i]
j = i - 1
while j >= 0 and lst[j] > key:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = key
return lst
# 测试直接插入排序
lst = [5, 2, 8, 1, 9]
print(insertion_sort(lst))折半插入排序
def binary_insertion_sort(lst):
for i in range(1, len(lst)):
key = lst[i]
low, high = 0, i - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] > key:
high = mid - 1
else:
low = mid + 1
for j in range(i - 1, high, -1):
lst[j + 1] = lst[j]
lst[high + 1] = key
return lst
# 测试折半插入排序
lst = [5, 2, 8, 1, 9]
print(binary_insertion_sort(lst))希尔排序
def shell_sort(lst):
n = len(lst)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = lst[i]
j = i
while j >= gap and lst[j - gap] > temp:
lst[j] = lst[j - gap]
j -= gap
lst[j] = temp
gap //= 2
return lst
# 测试希尔排序
lst = [5, 2, 8, 1, 9]
print(shell_sort(lst))4.2 交换排序
交换排序的基本思想是通过不断交换相邻元素的位置，将逆序对调整为顺序对，从而实现排序。
起泡排序
def bubble_sort(lst):
n = len(lst)
for i in range(n):
for j in range(0, n - i - 1):
if lst[j] > lst[j + 1]:
lst[j], lst[j + 1] = lst[j + 1], lst[j]
return lst
# 测试起泡排序
lst = [5, 2, 8, 1, 9]
print(bubble_sort(lst))快速排序
def quick_sort(lst):
if len(lst) <= 1:
return lst
pivot = lst[0]
left = []
right = []
for x in lst[1:]:
if x <= pivot:
left.append(x)
else:
right.append(x)
return quick_sort(left) + [pivot] + quick_sort(right)
# 测试快速排序
lst = [5, 2, 8, 1, 9]
print(quick_sort(lst))4.3 选择排序
选择排序的基本思想是每一趟在待排序元素中选择最小（或最大）的元素，放到已排序序列的末尾。
简单选择排序
def selection_sort(lst):
for i in range(len(lst)):
min_idx = i
for j in range(i + 1, len(lst)):
if lst[j] < lst[min_idx]:
min_idx = j
lst[i], lst[min_idx] = lst[min_idx], lst[i]
return lst
# 测试简单选择排序
lst = [5, 2, 8, 1, 9]
print(selection_sort(lst))堆排序
def heapify(lst, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and lst[i] < lst[l]:
largest = l
if r < n and lst[largest] < lst[r]:
largest = r
if largest != i:
lst[i], lst[largest] = lst[largest], lst[i]
heapify(lst, n, largest)
def heap_sort(lst):
n = len(lst)
for i in range(n // 2 - 1, -1, -1):
heapify(lst, n, i)
for i in range(n - 1, 0, -1):
lst[i], lst[0] = lst[0], lst[i]
heapify(lst, i, 0)
return lst
# 测试堆排序
lst = [5, 2, 8, 1, 9]
print(heap_sort(lst))4.4 归并排序
归并排序的定义是将两个或多个已排序的子序列合并成一个有序序列。
2 - 路归并排序过程
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left_half = merge_sort(lst[:mid])
right_half = merge_sort(lst[mid:])
return merge(left_half, right_half)
def merge(left, right):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
# 测试归并排序
lst = [5, 2, 8, 1, 9]
print(merge_sort(lst))4.5 基数排序
基数排序的基本思想是根据关键字的各位数字来分配和收集元素，不需要关键字之间的比较。
链式基数排序步骤
def radix_sort(lst):
max_value = max(lst)
exp = 1
while max_value // exp > 0:
counting_sort(lst, exp)
exp *= 10
return lst
def counting_sort(lst, exp):
n = len(lst)
output = [0] * n
count = [0] * 10
for i in range(n):
index = (lst[i] // exp) % 10
count[index] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = (lst[i] // exp) % 10
output[count[index] - 1] = lst[i]
count[index] -= 1
i -= 1
for i in range(n):
lst[i] = output[i]
# 测试基数排序
lst = [170, 45, 75, 90, 802, 24, 2, 66]
print(radix_sort(lst))