Python排序算法的稳定性分析
Python排序算法的稳定性指的是在排序过程中，对于相等的元素，在排序后是否仍保持其原来的相对位置不变。具体来说，如果两个相等的元素A和B，在原数列中A在B的前面，那么排序后，如果A仍在B的前面，则认为该排序算法是稳定的。如果不保持原来的相对位置，认为该排序算法是不稳定的。
以下是常见的Python排序算法的稳定性分析：
1.冒泡排序（Bubble Sort）：稳定
冒泡排序是通过相邻元素的比较和交换来完成排序的，因为每次比较和交换只涉及相邻元素，所以它是稳定的排序算法。以下是一个示例代码：
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# 测试示例
arr = [5, 2, 6, 1, 8, 4, 9, 3, 7]
bubble_sort(arr)
print(arr) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
2.插入排序（Insertion Sort）：稳定
插入排序是将一个元素插入到已排好序的序列中，因为同等大小的元素在插入时会插到后面，所以插入排序是稳定的排序算法。以下是一个示例代码：
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i-1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr
# 测试示例
arr = [5, 2, 6, 1, 8, 4, 9, 3, 7]
insertion_sort(arr)
print(arr) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
3.归并排序（Merge Sort）：稳定
归并排序是将一个序列分成两个子序列，分别排序再合并的过程，因为合并的过程会保持相等元素的原有顺序，所以归并排序是稳定的排序算法。以下是一个示例代码：
def merge_sort(arr):
def merge(left, right):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
# 测试示例
arr = [5, 2, 6, 1, 8, 4, 9, 3, 7]
result = merge_sort(arr)
print(result) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
4.快速排序（Quick Sort）：不稳定
快速排序是选择一个枢轴元素，将小于它的元素放到左边，大于它的元素放到右边，之后递归地对左右子集进行快速排序。快速排序不保证相等大小的元素在排序前和排序后的相对位置不变，所以是不稳定的。以下是一个示例代码：
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
less = [ele for ele in arr[1:] if ele <= pivot]
greater = [ele for ele in arr[1:] if ele > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
# 测试示例
arr = [5, 2, 6, 1, 8, 4, 9, 3, 7]
result = quick_sort(arr)
print(result) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
综上可知，冒泡排序、插入排序、归并排序是稳定的排序算法，而快速排序是不稳定的排序算法。所以，在需要保持相同元素的相对位置不变的情况下，应该优先考虑使用稳定的排序算法。
相关文章