八个排序算法python

### 八种排序算法的Python实现

#### 插入排序 Insertion Sort
此方法通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入[^1]。

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

#### 归并排序 Merge Sort
采用分治法策略，将数组分成两半分别排序再合并结果。这种方法能保证稳定性和O(n log n)的时间复杂度[^2]。

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

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

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

#### 快速排序 Quick Sort
快速排序是一种高效的排序算法，它利用了分而治之的原则来减少比较次数.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]

        return quick_sort(left) + middle + quick_sort(right)

#### 堆排序 Heap Sort
堆排序基于二叉堆的数据结构，能够在线性时间内完成初始化，并保持较好的性能表现[^4].

import heapq as hq

def heap_sort(nums):
    h = []
    for value in nums:
        hq.heappush(h,value)
    return [hq.heappop(h) for _ in range(len(h))]

#### 计数排序 Counting Sort
适用于整数值范围有限的情况下的线性时间排序方案.

def counting_sort(nums,max_val):
    m = max_val + 1
    count = [0] * m                
    
    for a in nums:
        count[a] += 1             
    i = 0
    for a in range(m):            
        for c in range(count[a]):  
            nums[i] = a
            i += 1
    return nums

#### 桶排序 Bucket Sort
当输入服从均匀分布时可以达到接近线性的效率.

from collections import defaultdict 

def bucket_sort(nums,k=5):
    buckets = [[] for _ in range(k)]
    mx,mn = max(nums),min(nums)
    rng = (mx-mn)/k
    for num in nums:
        diff =(num - mn) / rng - int((num - mn) / rng)

        into_bucket = int((num - mn) / rng)
        if into_bucket==k: 
            into_bucket-=1
            
       buckets[into_bucket].append(num)

    output = []

    for bucket in buckets:
        output.extend(sorted(bucket))
        
    return output

#### 基数排序 Radix Sort
针对多位数字的一种非比较型整数排序算法.

def radix_sort(nums):
    RADIX = 10
    placement = 1
    max_digit = max(nums)

    d = len(str(max(abs(min(nums)), abs(max(nums)))))

    for i in range(d):
        # 创造桶
        buckets = [[] for _ in range(RADIX)]

        for i in nums:
            tmp = int(((i % (RADIX*placement)) / placement))
            buckets[tmp].append(i)
        # 放回原列表
        a = 0
        for b in range(RADIX):
            buck = buckets[b]
            for i in buck:
                nums[a] = i
                a += 1

        # 移动到下一位
        placement *= RADIX
    return nums

#### 冒泡排序 Bubble Sort
简单直观但是效率较低的选择之一，适合教学用途[^3].

def bubble_sort(nums):
    swapped = False
    for n in range(len(nums)-1, 0, -1):
        for i in range(n):
            if nums[i] > nums[i + 1]:
                swapped = True
                nums[i], nums[i + 1] = nums[i + 1], nums[i]       
        if not swapped:
            return nums
    return nums