Python教程：使用Python实现冒泡排序和快速排序

1.冒泡排序

1.1介绍

冒泡排序（Bubble Sort）是一种简单直观的排序算法，它重复地遍历待排序序列，每次比较相邻的两个元素，如果它们的顺序错误就交换它们。经过一轮的遍历，最大（或最小）的元素就像气泡一样“冒”到了最后，因此得名冒泡排序。

1.2冒泡排序算法的原理

冒泡排序算法的基本原理如下：

1. 从第一个元素开始，依次比较相邻的两个元素，如果顺序不正确则交换它们。
2. 经过第一轮遍历后，最大（或最小）的元素被“冒泡”到了最后一个位置。
3. 重复以上步骤，每次遍历都会将剩余未排序部分的最大（或最小）元素“冒泡”到合适的位置。
4. 直到所有元素都排好序为止。

1.3Python 实现冒泡排序算法

下面是用 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]
 
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("排序后的数组:", arr)  # 输出: [11, 12, 22, 25, 34, 64, 90]

2.快速排序

2.1介绍

快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家 Tony Hoare 在 1960 年提出。它是一种分治算法，通过选择一个基准元素，将数组分成两个子数组，小于基准的放在左边，大于基准的放在右边，然后对子数组递归地应用快速排序算法，最终使整个数组有序。

2.2 快速排序算法的原理

快速排序算法的基本原理如下：

1. 选择一个基准元素（通常选择数组的第一个元素）。
2. 使用两个指针，一个从数组的起始位置向后移动（称为左指针），一个从数组的末尾向前移动（称为右指针）。
3. 左指针不断向右移动，直到找到一个大于基准元素的元素，右指针不断向左移动，直到找到一个小于基准元素的元素。
4. 如果左指针小于等于右指针，则交换它们所指向的元素，并继续移动指针；否则，停止移动。
5. 重复以上步骤，直到左指针超过右指针。
6. 将基准元素与右指针所指向的元素交换位置，此时基准元素左边的元素都小于等于基准元素，右边的元素都大于等于基准元素。
7. 分别对基准元素左边和右边的子数组递归地应用快速排序算法。

2.3 Python 实现快速排序算法

下面是用 Python 实现快速排序算法的代码：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less_than_pivot = [x for x in arr[1:] if x <= pivot]
        greater_than_pivot = [x for x in arr[1:] if x > pivot]
        return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)
 
# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print("排序后的数组:", sorted_arr)  # 输出: [11, 12, 22, 25, 34, 64, 90]