排序算法案例

排序算法概述

• 排序算法是计算机科学中的一个重要主题，用于将一组数据按特定顺序排列。排序算法有很多种，每种算法在不同情况下有不同的性能表现。
• 不同的排序算法适用于不同的场景和数据特征。在选择排序算法时，需要考虑数据规模、数据分布以及性能要求。了解各种排序算法的原理和实现方法有助于在实际应用中选择最合适的排序方法。
  以下是一些常见的排序算法：

1.冒泡排序（Bubble Sort）

原理：反复遍历要排序的列表，每次比较相邻的两个元素，如果顺序错误就交换，直到没有需要交换的元素为止。
时间复杂度：最坏和平均情况下都是 𝑂(𝑛2)
空间复杂度：O(1)

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

2.选择排序（Selection Sort）

原理：每次从未排序部分选择最小的元素，放到已排序部分的末尾。
时间复杂度：最坏和平均情况下都是 𝑂(𝑛2)
空间复杂度：𝑂(1)

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

3.插入排序（Insertion Sort）

原理：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
时间复杂度：最坏和平均情况下都是
𝑂(𝑛2)，最佳情况（已排序）是 𝑂(𝑛)
空间复杂度：𝑂(1)

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
    return arr

4.归并排序（Merge Sort）

原理：采用分治法，将数组分成两个子数组，分别排序后合并。

时间复杂度：最坏和平均情况下都是 𝑂(𝑛log𝑛)
空间复杂度：O(n)

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
    return arr

5.快速排序（Quick Sort）

原理：采用分治法，选择一个基准元素，将数组分成两部分，一部分比基准小，一部分比基准大，然后递归排序两部分。
时间复杂度：最坏情况下是 O(n2)，平均情况下是 O(nlogn)。
空间复杂度：O(logn)（递归调用栈）

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

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)
    return arr

6. 希尔排序（Shell Sort）

原理：改进版的插入排序，通过将数据按一定间隔分组，对每组进行插入排序，然后逐渐减少间隔进行多次排序。

时间复杂度：最坏情况下是 O(n2)，但通常比插入排序快得多。
空间复杂度：O(1)

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

7. 堆排序（Heap Sort）

原理：利用堆这种数据结构来排序，首先将数组构建成最大堆，然后将堆顶元素（最大值）与末尾元素交换，再对剩余元素进行堆调整，重复此过程。
时间复杂度：最坏和平均情况下都是O(nlogn)
空间复杂度：O(1)

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

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

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

8. 计数排序（Counting Sort）

原理：适用于整数排序，通过计数数组记录每个整数的出现次数，然后按照顺序输出。
时间复杂度：O(n+k)，其中 𝑘是数列中的最大值
空间复杂度：O(k)

def counting_sort(arr):
    max_val = max(arr)
    m = max_val + 1
    count = [0] * m                

    for a in arr:
        count[a] += 1              
    i = 0
    for a in range(m):            
        for c in range(count[a]):  
            arr[i] = a
            i += 1
    return arr

9. 桶排序（Bucket Sort）

原理：将数组分成若干个桶，每个桶内的元素分别进行排序，然后合并所有桶内的元素得到有序序列。
时间复杂度：最坏情况下是
O(n2)，但通常情况下是 O(n+k)
空间复杂度：O(n+k)

def bucket_sort(arr):
    bucket = []
    slot_num = 10 
    for i in range(slot_num):
        bucket.append([])

    for j in arr:
        index_b = int(slot_num * j)
        bucket[index_b].append(j)

    for i in range(slot_num):
        bucket[i] = insertion_sort(bucket[i])

    k = 0
    for i in range(slot_num):
        for j in range(len(bucket[i])):
            arr[k] = bucket[i][j]
            k += 1
    return arr

10. 基数排序（Radix Sort）

原理：按照个位、十位、百位等进行多次排序，每次排序使用稳定的排序算法（如计数排序）。
时间复杂度：
O(nk)，其中k 是数的位数。
空间复杂度：O(n+k)

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

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

def radix_sort(arr):
    max1 = max(arr)
    exp = 1
    while max1 / exp > 1:
        counting_sort_for_radix(arr, exp)
        exp *= 10
    return arr

• 调用测试

arr = [1,4,3,0,2]
print(f'冒泡排序：{bubble_sort(arr)}')
print(f'选择排序：{selection_sort(arr)}')
print(f'插入排序：{insertion_sort(arr)}')
print(f'归并排序：{merge_sort(arr)}')
print(f'快速排序：{quick_sort(arr,0,4)}')
print(f'希尔排序：{shell_sort(arr)}')
print(f'堆排序： {heap_sort(arr)}')
print(f'计数排序：{counting_sort(arr)}')
print(f'桶排序：{bucket_sort([num/10 for num in arr])}')
print(f'基数排序：{radix_sort(arr)}')

冒泡排序：[0, 1, 2, 3, 4]
选择排序：[0, 1, 2, 3, 4]
插入排序：[0, 1, 2, 3, 4]
归并排序：[0, 1, 2, 3, 4]
快速排序：[0, 1, 2, 3, 4]
希尔排序：[0, 1, 2, 3, 4]
堆排序： [0, 1, 2, 3, 4]
计数排序：[0, 1, 2, 3, 4]
桶排序：[0.0, 0.1, 0.2, 0.3, 0.4]
基数排序：[0, 1, 2, 3, 4]