博客

稳定排序算法可以保证排序后相同大小的元素在排序前的相对顺序不变。常见的几种稳定排序算法包括冒泡排序、插入排序和归并排序。

冒泡排序

冒泡排序是一种简单的排序算法，其基本思想是多次遍历待排序序列，每次都将相邻的两个元素比较并交换位置。这样经过多次遍历后，最大（小）的元素就被排到了序列的最前（后）面，因此称之为冒泡排序。

冒泡排序的代码如下：

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

例如，对于一个需要排序的列表[3,2,3,1,5]，使用冒泡排序算法进行排序，得到的结果为[1,2,3,3,5]。

插入排序

插入排序算法是一种简单的排序算法，其基本思想是将待排序序列分为已排序和未排序部分，每次从未排序部分取出一个元素，插入到已排序部分的合适位置。因为插入元素的过程类似于实际生活中插入一张扑克牌，因此被称为插入排序。

插入排序的代码如下：

def insert_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

例如，对于一个需要排序的列表[3,2,3,1,5]，使用插入排序算法进行排序，得到的结果为[1,2,3,3,5]。

归并排序

归并排序算法是一种分治策略的排序算法，将待排序序列分解为若干个子序列，对子序列进行排序，再将排序好的子序列合并成一个有序序列。因为将若干个子序列进行合并的过程类似于归并操作，因此被称为归并排序。

归并排序的代码如下：

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    left_lst = lst[:mid]
    right_lst = lst[mid:]
    left_lst = merge_sort(left_lst)
    right_lst = merge_sort(right_lst)
    return merge(left_lst, right_lst)

def merge(left_lst, right_lst):
    i = j = 0
    merged_lst = []
    while i < len(left_lst) and j < len(right_lst):
        if left_lst[i] < right_lst[j]:
            merged_lst.append(left_lst[i])
            i += 1
        else:
            merged_lst.append(right_lst[j])
            j += 1
    merged_lst.extend(left_lst[i:])
    merged_lst.extend(right_lst[j:])
    return merged_lst

例如，对于一个需要排序的列表[3,2,3,1,5]，使用归并排序算法进行排序，得到的结果为[1,2,3,3,5]。

稳定排序算法的作用是保证排序后，相同大小的元素在排序前的相对顺序不变，这样可以更加稳定地处理数据。稳定排序算法的使用方法是根据具体排序需求选择不同的算法，例如冒泡排序适用于小规模的排序，插入排序适用于基本有序的数据排序，归并排序适用于大规模的排序。