Python排序算法实例代码

下面就给您详细讲解“Python排序算法实例代码”的完整攻略：

一、排序算法简介

排序算法（sorting algorithm）是计算机程序中最基础的算法之一，它是指将一组无序的数据元素，按照某种规则进行排列的过程。

常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等，它们的实现方式不同，但总体思路都是通过比较和交换元素位置来完成排序的。

在Python中，也有很多内置的排序函数，比如sort()、sorted()等。但是，理解和掌握基本的排序算法，对于编写高效的程序和解决实际问题非常有帮助。

二、Python排序算法实例代码

下面，我们将分别展示冒泡排序、选择排序和插入排序的Python实现代码。

1. 冒泡排序

冒泡排序（Bubble Sort）是最基础的排序算法之一，它的基本思想是通过相邻元素的比较和交换，使得每一趟排序都能确定一个当前未排序部分的最大值。

冒泡排序的时间复杂度为O(n^2)，不适用于大规模数据。

以下是Python实现的冒泡排序代码：

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

代码中，外层循环遍历未排序部分，内层循环遍历相邻的元素，并进行比较和交换。

2. 选择排序

选择排序（Selection Sort）也是一种简单的排序算法，它的基本思想是通过不断选择未排序部分的最小值，并将其放到已排序部分的最后面，最终实现整个序列的排序。

选择排序的时间复杂度为O(n^2)，不适用于大规模数据。

以下是Python实现的选择排序代码：

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

代码中，外层循环遍历未排序部分，内层循环遍历未排序部分的元素，并记录最小值的索引，最后将最小值与未排序部分的第一个元素进行交换。

3. 插入排序

插入排序（Insertion Sort）也是一种简单的排序算法，它的基本思想是通过逐步构建有序序列，不断将未排序部分的元素插入到已排序部分的合适位置，从而实现整个序列的排序。

插入排序的时间复杂度为O(n^2)，适用于小规模数据。

以下是Python实现的插入排序代码：

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

代码中，外层循环遍历未排序部分，内层循环遍历已排序的元素，并将当前元素插入到合适的位置。

三、示例说明

下面，我们举两个例子来说明如何应用以上排序算法。

1. 按照成绩进行排序

假设我们有一个由学生姓名和成绩组成的列表，现在要按照成绩从高到低进行排序。代码如下：

students = [('Tom', 85), ('Bob', 92), ('Mary', 78), ('Jerry', 99)]

# 按照成绩从高到低排序
scores = [s[1] for s in students]
sorted_scores = bubble_sort(scores)[::-1]
sorted_students = [(students[scores.index(score)][0], score) for score in sorted_scores]
print(sorted_students)

代码中，我们先将学生成绩提取出来，然后进行排序，最后再根据排序结果重新构造学生列表。

输出结果为：

[('Jerry', 99), ('Bob', 92), ('Tom', 85), ('Mary', 78)]

2. 丢失的数字

给定一个由0~n之间的n个不同的整数组成的列表，其中有一个数字丢失了，现在要找到它。代码如下：

nums = [3, 1, 0, 5, 2, 7, 6, 4]

# 找到丢失的数字
sorted_nums = selection_sort(nums)
for i in range(len(sorted_nums)):
    if sorted_nums[i] != i:
        print(i)
        break

代码中，我们先对列表进行从小到大的排序，然后依次检查每个数字，找到第一个与下标不一致的数字即为缺失的数字。