博客

详解稳定排序算法原理与使用方法

稳定排序算法是一种能够保证相等元素在排序后的相对位置不变的排序算法。在实际应用中，稳定排序算法广泛应用于需要维护元素相对位置的场景。

常见的稳定排序算法有冒泡排序、插入排序、归并排序等。下面分别对它们进行详细讲解。

  1. 冒泡排序

冒泡排序的基本思想是从数组的第一个元素开始，比较相邻的两个元素，如果前一个元素大于后一个元素，则交换这两个元素的位置。重复执行这个过程，直到数组中的所有元素都被排序。

代码示例：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
  1. 插入排序

插入排序的基本思想是将数组分为已排序和未排序两个部分，初始时已排序部分只包含第一个元素，然后将未排序部分中的每个元素插入到已排序部分中的正确位置，直到所有元素都被排序。

代码示例：

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
  1. 归并排序

归并排序的基本思想是将数组分治，将一个大问题分解成若干个小问题，分别解决后再将结果合并起来。具体实现时，先将数组拆分为左右两个子数组，递归地对左右子数组进行排序，然后合并左右子数组得到排好序的数组。

代码示例：

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        merge_sort(left)
        merge_sort(right)
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1
    return arr

使用这些稳定排序算法时，只需调用相应的函数即可。例如，对数组进行插入排序可以使用如下代码：

arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = insertion_sort(arr)
print(sorted_arr)

总之，稳定排序算法在实际应用中是非常重要的，具有保持元素相对位置不变的优良特性，能够为我们解决许多实际问题提供便利。

Tags: