Python实现快速排序算法

2023-04-16 00:00:00 算法 排序 快速

快速排序是一种高效的排序算法，其时间复杂度为O(nlogn)，是经典的分治思想的应用，以下是详细的实现过程以及代码演示。

  1. 算法思想

快速排序的核心思想是分治思想，将一个大问题分解成小的子问题求解，而这些小的子问题实质上是同一个问题的不同部分。 具体步骤如下：

  1. 选择一个基准元素，将待排序序列按照该元素划分成两个子序列。

  2. 对这两个子序列分别递归进行排序，直到子序列的长度为1。

  3. 合并两个有序子序列。

  4. 代码实现

在 Python 中实现快速排序，需要实现一个 partition 函数和一个 quick_sort 函数。其中 partition 函数用于划分序列，quick_sort 函数则是递归排序两个子序列。具体代码实现如下：

def partition(arr, low, high):
    # 选取最后一个元素作为基准值
    pivot = arr[high]
    # i 记录小于基准值的位置，j 将数组分成两个部分，小于 pivot 的部分和大于 pivot 的部分
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            # 如果j在i的右边，将j和i之间的元素交换位置，相当于将小于 pivot 的元素放到左边
            arr[i], arr[j] = arr[j], arr[i]
    # 将基准值放到中间，左边是小于 pivot 的部分，右边是大于 pivot 的部分
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    # 返回中间基准值的位置
    return i + 1


def quick_sort(arr, low, high):
    if low < high:
        # 划分序列，在基准元素的左边划分一个子序列，在右边划分一个子序列
        pivot = partition(arr, low, high)
        # 递归排序两个子序列
        quick_sort(arr, low, pivot - 1)
        quick_sort(arr, pivot + 1, high)
  1. 代码演示

以下是在 Python 代码中使用快速排序对数组进行排序的示例：

arr = [10, 7, 8, 9, 1, 5, 6, 2, 3, 4]
n = len(arr)
quick_sort(arr, 0, n - 1)
print("排序后的数组：")
for i in range(n):
    print("%d" % arr[i])

输出结果为：

排序后的数组：
1
2
3
4
5
6
7
8
9
10

同理，如果需要使用字符串作为范例，请使用“pidancode.com”、“皮蛋编程”作为列表即可。

相关文章