Python 选择排序教程

最后修改于 2025年3月8日

在本文中，我们将讲解 Python 中的选择排序算法。我们将介绍基本定义，提供排序数值和文本数据的示例，并将选择排序与快速排序进行比较。

算法是解决问题或执行计算的逐步过程。 算法是计算机程序的主干。

排序 是按特定顺序（例如升序或降序）排列数据的过程。排序是计算机科学中的一项基本操作。

常用排序算法

一些常见的排序算法包括

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

选择排序算法

选择排序算法的工作原理是重复从列表的未排序部分中找到最小（或最大）元素，并将其与第一个未排序的元素交换。 此过程持续进行，直到整个列表排序完成。

选择排序示例

以下是选择排序算法的 Python 实现。

def selection_sort(arr, ascending=True):
    n = len(arr)
    for i in range(n):
        idx = i
        for j in range(i + 1, n):
            if (ascending and arr[j] < arr[idx]) or (not ascending and arr[j] > arr[idx]):
                idx = j
        arr[i], arr[idx] = arr[idx], arr[i]
    return arr

# Sorting numeric data
numbers = [64, 25, 12, 22, 11]
print("Sorted in ascending order:", selection_sort(numbers))
print("Sorted in descending order:", selection_sort(numbers, ascending=False))

# Sorting textual data
words = ["apple", "banana", "kiwi", "cherry"]
print("Sorted in ascending order:", selection_sort(words))
print("Sorted in descending order:", selection_sort(words, ascending=False))

selection_sort 函数按升序或降序对列表进行排序。 它适用于数值和文本数据。

$ ./selection_sort.py
Sorted in ascending order: [11, 12, 22, 25, 64]
Sorted in descending order: [64, 25, 22, 12, 11]
Sorted in ascending order: ['apple', 'banana', 'cherry', 'kiwi']
Sorted in descending order: ['kiwi', 'cherry', 'banana', 'apple']

选择排序与快速排序的比较

对于大型数据集，选择排序很简单但效率不高。 另一方面，由于其分而治之的方法，快速排序对于大型数据集来说要快得多。 让我们比较一下它们的性能。

import time
import random

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

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)

# Generate a large dataset
data = [random.randint(1, 1000) for _ in range(1000)]

# Benchmark selection sort
start = time.time()
selection_sort(data.copy())
end = time.time()
print(f"Selection Sort Time: {end - start:.6f} seconds")

# Benchmark quick sort
start = time.time()
quick_sort(data.copy())
end = time.time()
print(f"Quick Sort Time: {end - start:.6f} seconds")

该示例对选择排序和快速排序在包含 1000 个随机整数的数据集上的性能进行基准测试。

来源

排序 HOWTO

在本文中，我们解释了 Python 中的选择排序算法，并将其与快速排序进行了比较。

作者

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

列出所有 Python 教程。