跳到主要内容

排序算法稳定性

什么是排序算法稳定性？​

排序算法的稳定性是指当排序算法在处理具有相同关键字的元素时，是否能够保持它们原有的相对顺序。换句话说，如果两个元素的值相同，排序后它们的相对位置是否保持不变。

备注

稳定排序算法：保持相同关键字元素的相对顺序。
不稳定排序算法：不保证相同关键字元素的相对顺序。

为什么稳定性重要？​

稳定性在某些应用场景中非常重要。例如，当我们需要对数据进行多次排序时，保持相同关键字元素的相对顺序可以确保排序结果的正确性。一个常见的例子是对学生成绩进行排序：先按分数排序，再按姓名排序。如果排序算法是稳定的，那么相同分数的学生将按姓名的顺序排列。

稳定排序算法示例​

冒泡排序（Bubble Sort）​

冒泡排序是一种简单的稳定排序算法。它通过重复地遍历列表，比较相邻的元素并交换它们的位置，直到列表排序完成。

python
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, 3, 8, 4, 6]
print("排序前:", arr)
print("排序后:", bubble_sort(arr))

输出：

排序前: [5, 3, 8, 4, 6]
排序后: [3, 4, 5, 6, 8]

归并排序（Merge Sort）​

归并排序是一种分治算法，它将列表分成两半，分别排序，然后合并。归并排序也是稳定的。

python
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

    return arr

# 示例输入
arr = [5, 3, 8, 4, 6]
print("排序前:", arr)
print("排序后:", merge_sort(arr))

输出：

排序前: [5, 3, 8, 4, 6]
排序后: [3, 4, 5, 6, 8]

不稳定排序算法示例​

快速排序（Quick Sort）​

快速排序是一种常用的不稳定排序算法。它通过选择一个“基准”元素，将列表分成两部分，一部分小于基准，另一部分大于基准，然后递归地对这两部分进行排序。

python
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 示例输入
arr = [5, 3, 8, 4, 6]
print("排序前:", arr)
print("排序后:", quick_sort(arr))

输出：

排序前: [5, 3, 8, 4, 6]
排序后: [3, 4, 5, 6, 8]
警告

快速排序是不稳定的，因为它可能会改变相同关键字元素的相对顺序。

实际应用场景​

多条件排序​

假设我们有一个学生列表，每个学生有姓名和分数。我们首先按分数排序，然后按姓名排序。如果排序算法是稳定的，那么相同分数的学生将按姓名的顺序排列。

python
students = [
    {"name": "Alice", "score": 90},
    {"name": "Bob", "score": 85},
    {"name": "Charlie", "score": 90},
    {"name": "David", "score": 85}
]

# 先按分数排序
students_sorted_by_score = sorted(students, key=lambda x: x["score"])

# 再按姓名排序
students_sorted_by_name = sorted(students_sorted_by_score, key=lambda x: x["name"])

print(students_sorted_by_name)

输出：

[
    {"name": "Bob", "score": 85},
    {"name": "David", "score": 85},
    {"name": "Alice", "score": 90},
    {"name": "Charlie", "score": 90}
]
提示

在这个例子中，我们使用了Python的sorted函数，它是稳定的。因此，相同分数的学生按姓名的顺序排列。

总结​

排序算法的稳定性在处理具有相同关键字的元素时非常重要。稳定排序算法（如冒泡排序和归并排序）保持相同关键字元素的相对顺序，而不稳定排序算法（如快速排序）则不保证这一点。在实际应用中，稳定性可以确保多条件排序的正确性。

附加资源​

练习​

  1. 实现一个稳定的排序算法（如归并排序）并对一个包含重复元素的列表进行排序。
  2. 尝试使用不稳定的排序算法（如快速排序）对同一个列表进行排序，并观察结果。
  3. 编写一个多条件排序的程序，确保排序结果的正确性。