博客

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

当我们提到排序算法的时候，常常会将其分为两类：稳定排序算法和非稳定排序算法。稳定排序算法是指在排序过程中，具有相同关键字的记录，排序后仍然保持排序前的先后顺序。稳定排序算法相对于非稳定排序算法有更为明显的优势，例如可以保留有先后顺序相关的信息，方便后续的处理。

下面让我们来详细讲解稳定排序算法的使用方法和实现。

稳定排序算法的分类

通常使用的稳定排序算法包括冒泡排序、插入排序、归并排序和基数排序等。接下来对这几种算法进行一一讲解。

冒泡排序

冒泡排序是一种简单的排序算法，算法思想是将要排序的数据按照大小进行比较，并根据比较结果交换它们的位置，使较小或较大的元素逐渐“冒泡”到数列的顶端。这个过程类似于水中的气泡从深处升至水面。

以下是冒泡排序的Python实现代码：

def bubbleSort(arr):
    n = len(arr)

    # 遍历所有数组元素
    for i in range(n):
        # 最后 i 个元素已经排好序了
        for j in range(0, n-i-1):
            # 如果当前元素大于下一个元素，则交换它们的位置
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)

print("排序后的数组:")
for i in range(len(arr)):
    print("%d" %arr[i])

插入排序

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

以下是插入排序的Python实现代码：

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

arr = [12, 11, 13, 5, 6]
insertionSort(arr)

print ("排序后的数组:")
for i in range(len(arr)):
    print ("%d" %arr[i])

归并排序

归并排序是一种分而治之的算法，它将原始数组划分成较小的数组，直到每个小数组都可以由单个元素排序。然后，排序过程发生在合并相邻的小数组时，直到合并回原始数组的单个数组为止。

以下是归并排序的Python实现代码：

def mergeSort(arr):
    if len(arr) > 1:

        # Divide the array into two halves
        mid = len(arr)//2
        leftArray = arr[:mid]
        rightArray = arr[mid:]

        # Recursively sort both halves
        mergeSort(leftArray)
        mergeSort(rightArray)

        # Merge the halves
        i = j = k = 0

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

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

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

arr = [38, 27, 43, 3, 9, 82, 10]
mergeSort(arr)
print("排序后的数组:")
for i in range(len(arr)):
    print("%d" %arr[i])

基数排序

基数排序是一种非比较型整数排序算法，它的原理是根据数位来排序，比较适用于位数较少的数列排序。

以下是基数排序的Python实现代码：

def radixSort(arr):
    maxNumber = max(arr)
    currPosition = 1
    while maxNumber / currPosition > 0:
        countingSort(arr, currPosition)
        currPosition *= 10

def countingSort(arr, currPosition):
    output = [0] * len(arr)
    count = [0] * 10

    for i in range(len(arr)):
        index = arr[i] // currPosition
        count[index % 10] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = len(arr) - 1
    while i >= 0:
        index = arr[i] // currPosition
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    i = 0
    for i in range(0, len(arr)):
        arr[i] = output[i]

arr = [170, 45, 75, 90, 802, 24, 2, 66, 550]
radixSort(arr)
print("排序后的数组:")
for i in range(len(arr)):
    print("%d" %arr[i])

总之，稳定排序算法有很多，我们可以根据算法复杂度有所区分，选择最适合自己的算法。

Tags: