博客

稳定排序算法是指在排序过程中，对于相同大小的元素，算法能够保证经过排序后它们在序列中的相对位置不变。相应地，非稳定排序算法是无法保证元素相对位置不变的。以下将详细介绍稳定排序算法的作用、使用方法以及几个常见的稳定排序算法。

稳定排序算法的作用

稳定排序算法的作用一方面是为了保证元素相对位置不变，方便后续的处理。另一方面，某些情况下，我们需要根据多个属性对数据进行排序，而使用稳定排序算法可以保证先按照一个属性排序后，再按照另一个属性排序时，先前排序的结果不会被打乱。

稳定排序算法的使用方法

稳定排序算法的使用方法和其他排序算法基本相同，只需按照自己的需求选择合适的算法，并将待排序的序列作为输入参数即可。下面介绍几个常见的稳定排序算法。

冒泡排序

冒泡排序是稳定的交换排序算法，每次比较相邻两个元素的大小，如果前一个元素大于后一个元素，则交换它们的位置。

def bubble_sort(lst):
    n = len(lst)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
    return lst

插入排序

插入排序是稳定的排序算法，将待排序的序列分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的合适位置。

def insertion_sort(lst):
    n = len(lst)
    for i in range(1, n):
        j = i
        while j > 0 and lst[j - 1] > lst[j]:
            lst[j - 1], lst[j] = lst[j], lst[j - 1]
            j -= 1
    return lst

示例说明

示例 1

假设有如下学生信息列表，需要按照年龄和成绩分别进行排序。首先按照年龄进行排序，然后再按照成绩进行排序。如果使用非稳定排序算法，就可能出现按照年龄排序后，成绩的顺序被打乱的情况。

使用稳定排序算法，我们可以比较容易地实现上述需求。

def sort_by_age_and_score(lst):
    # 先按照成绩排序
    lst = insertion_sort(lst, key=lambda x: x[2])
    # 再按照年龄排序
    lst = insertion_sort(lst, key=lambda x: x[1])
    return lst

示例 2

假设我们需要对一个包含多个相同元素的列表进行排序，同时需要保证这些相同元素的相对位置不变。如果使用非稳定排序算法，就有可能出现相同元素的顺序被打乱的情况。

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
lst_sorted = sorted(lst)
print(lst_sorted)  # 输出 [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

上述代码使用了Python内置的sorted函数，该函数使用的是非稳定排序算法，因此相同元素的相对位置有可能发生变化。

要保持相对位置不变，我们可以使用稳定排序算法，比如插入排序。

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
lst_sorted = insertion_sort(lst)
print(lst_sorted)  # 输出 [3, 1, 4, 1, 5, 2, 6, 5, 3, 5, 9]

上述代码使用了插入排序算法，因此相同元素的相对位置得到了保持。