快速排序算法与归并排序算法的比较

# 1. 排序算法的概述

排序算法是一种通过比较和交换元素来使序列按照特定顺序排列的算法。它在各种场景中得到广泛应用，例如数据库查询优化、日程安排、编译器等。排序算法的重要性不言而喁，它直接影响数据处理效率，能够根据特定需求灵活选择适合的排序算法。一个高效的排序算法可以大大提高数据处理的效率和准确性，进而影响整个系统的性能和用户体验。因此，深入理解和掌握各种排序算法是每个计算机领域从业者的基本功。在接下来的章节中，我们将详细介绍常见的排序算法分类、快速排序算法的原理与实现、归并排序算法的原理与实现，最后比较排序算法的选择与性能。

# 2. 常见的排序算法分类

2.1 比较排序算法
2.1.1 冒泡排序
冒泡排序是一种简单的排序算法，重复遍历要排序的列表，一次比较两个元素，并根据大小交换它们的位置。
这个过程持续进行直到没有需要交换的元素，即列表已经排序完成。
冒泡排序的时间复杂度为 O(n^2)，是一种稳定的排序算法。

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

# 测试
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Sorted array is:", sorted_arr)

2.1.2 插入排序
插入排序的原理是将未排序的元素逐个插入到已排序部分的合适位置中，直到全部元素有序。
插入排序的时间复杂度为 O(n^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
    return arr

# 测试
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Sorted array is:", sorted_arr)

2.1.3 选择排序
选择排序每次选择未排序部分的最小元素放到已排序部分的末尾，直到全部元素有序。
选择排序的时间复杂度为 O(n^2)，是一种不稳定的排序算法。

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

# 测试
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Sorted array is:", sorted_arr)

2.2 非比较排序算法
2.2.1 计数排序
计数排序通过统计每个元素出现的次数，然后根据这个次数重新排列元素，得到有序序列。
计数排序的时间复杂度为 O(n+k)，其中 k 是元素的范围，适合非负整数排序。

def counting_sort(arr):
    max_val, min_val = max(arr), min(arr)
    counts = [0] * (max_val - min_val + 1)
    for num in arr:
        counts[num - min_val] += 1

    result = []
    for i, count in enumerate(counts):
        result.extend([i + min_val] * count)

    return result

# 测试
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("Sorted array is:", sorte