Python 快速排序教程

最后修改于 2025年3月8日

在本文中，我们将解释快速排序算法并演示其在 Python 中的用法。

“算法”是解决问题或执行计算的循序渐进的过程。算法是计算机科学和编程的基础。

排序是按照特定顺序（例如升序或降序）排列数据的过程。排序是编程中的常见操作。

常用排序算法

一些常见的排序算法包括

• 快速排序
• 归并排序
• 气泡排序
• 插入排序
• 选择排序

快速排序算法

快速排序是一种分治算法。它通过从数组中选择一个“枢轴”元素，并将其他元素根据它们小于或大于枢轴的值划分为两个子数组来工作。然后递归地对子数组进行排序。

快速排序示例

以下是快速排序算法的 Python 实现。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    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)

# Example usage
numbers = [3, 6, 8, 10, 1, 2, 1]
sorted_numbers = quick_sort(numbers)
print("Sorted numbers:", sorted_numbers)

words = ["banana", "apple", "cherry", "date"]
sorted_words = quick_sort(words)
print("Sorted words:", sorted_words)

quick_sort 函数以升序对数字或单词列表进行排序。

$ ./quick_sort.py 
Sorted numbers: [1, 1, 2, 3, 6, 8, 10]
Sorted words: ['apple', 'banana', 'cherry', 'date']

降序排序

要以降序排序，我们可以修改快速排序函数。

def quick_sort_desc(arr):
    if len(arr) <= 1:
        return arr
    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_desc(left) + middle + quick_sort_desc(right)

# Example usage
numbers = [3, 6, 8, 10, 1, 2, 1]
sorted_numbers_desc = quick_sort_desc(numbers)
print("Sorted numbers (descending):", sorted_numbers_desc)

words = ["banana", "apple", "cherry", "date"]
sorted_words_desc = quick_sort_desc(words)
print("Sorted words (descending):", sorted_words_desc)

quick_sort_desc 函数以降序对列表进行排序。

$ ./quick_sort_desc.py 
Sorted numbers (descending): [10, 8, 6, 3, 2, 1, 1]
Sorted words (descending): ['date', 'cherry', 'banana', 'apple']

将快速排序与插入排序进行比较

对于大型数据集，快速排序通常比插入排序更快。让我们通过基准测试来比较它们的性能。

import time
import random

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    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)

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

# Generate a large list of random numbers
data = [random.randint(0, 1000) for _ in range(10000)]

# Benchmark Quick Sort
start_time = time.time()
quick_sort(data.copy())
quick_sort_time = time.time() - start_time

# Benchmark Insertion Sort
start_time = time.time()
insertion_sort(data.copy())
insertion_sort_time = time.time() - start_time

print(f"Quick Sort time: {quick_sort_time:.6f} seconds")
print(f"Insertion Sort time: {insertion_sort_time:.6f} seconds")

基准测试比较了快速排序和插入排序对 10,000 个随机数列表进行排序所需的时间。

来源

维基百科上的快速排序

在本文中，我们解释了快速排序算法并演示了其在 Python 中的用法。

作者

我叫 Jan Bodnar，我是一名充满热情的程序员，拥有丰富的编程经验。我自 2007 年以来一直撰写编程文章。迄今为止，我已撰写了 1400 多篇文章和 8 本电子书。我在编程教学方面拥有十多年的经验。

列出所有 Python 教程。