Python列表排序的五种方法——稳定排序。

稳定排序是一种稳定的排序算法，它可以在保持元素相对顺序的同时进行排序。

本文将介绍Python中五种常用的稳定排序方法，包括冒泡排序、插入排序、选择排序、归并排序和希尔排序，并提供相应的代码示例。

1. 冒泡排序。

这个过程会持续进行直到没有更多的需要交换的元素，这意味着该列表已经排序完成。

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]

2. 插入排序。

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

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

3. 选择排序。

def selection_sort(lst):
    for i in range(len(lst)):
        min_idx = i
        for j in range(i+1, len(lst)):
            if lst[min_idx] > lst[j]:
                min_idx = j
        lst[i], lst[min_idx] = lst[min_idx], lst[i]

4. 归并排序。

它将数组分成两半，分别对这两半进行排序，然后将两个有序的子数组合并成一个有序的数组。

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

def merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0))
    return result

5. 希尔排序。

它的基本思想是将待排序的数据分割成若干个子序列，先对这若干个子序列进行插入排序，然后再将它们合并为一个整体。

def shell_sort(lst):
    gap = len(lst) // 2
    while gap > 0:
        for i in range(gap, len(lst)):
            temp = lst[i]
            j = i - gap
            while j >= gap and lst[j - gap] > temp:
                lst[j] = lst[j - gap]
                j -= gap
            lst[j] = temp
        gap //= 2
    return lst

希望对您有所帮助！

Python列表排序的五种方法——稳定排序 - 集智数据集