各种排序算法的稳定性

### 各类排序算法的稳定性

#### 插入排序
插入排序是一种稳定的排序方法。该算法通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入[^2]。

def insertion_sort(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

#### 归并排序
归并排序同样属于稳定排序类别。此过程涉及将数组分割成子列表直至每个子列表仅含单个元素；随后逐步合并这些子列表形成新的有序列表[^1]。

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

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

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

#### 基数排序
基数排序也是保持输入项相对顺序的一种方式，因此它是稳定的。它按照低位先处理的原则来排列数值，依次针对每一位执行计数排序作为中间步骤。

def countingSort(arr, exp1): 
  
    n = len(arr) 
  
    output = [0] * (n) 
   
    count = [0] * (10) 
    
    for i in range(0, n): 
        index = (arr[i]//exp1) 
        count[(index)%10] += 1
   
    for i in range(1,10): 
        count[i] += count[i-1] 

    i = n-1
    while i>=0: 
        index = (arr[i]//exp1) 
        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]

def radixsort(arr):

    max1 = max(arr)

    exp = 1
    while max1/exp > 0:
        countingSort(arr,exp)
        exp *= 10

#### 快速排序
快速排序通常不是一种稳定的排序技术。尽管可以通过特定实现使某些版本变得稳定，但这会增加复杂度和时间开销。

def partition(array, low, high):
    pivot = array[high]
    i = low - 1
    
    for j in range(low, high):
        if array[j] <= pivot:
            i = i + 1
            
            (array[i], array[j]) =
             (array[j], array[i])
            
    (array[i + 1], array[high]) = (array[high], array[i + 1])

    return i + 1


def quick_sort(array, low, high):
    if low < high:

        pi = partition(array, low, high)

        quick_sort(array, low, pi - 1)

        quick_sort(array, pi + 1, high)