快速排序算法的原理图解(快速排序法排序过程图解)

快速排序算法的原理图解

简介

快速排序是一种高效的排序算法,它通过分治法将一个无序列表逐渐排序。其平均时间复杂度为 O(n log n),最坏情况下的时间复杂度为 O(n²)。

步骤

快速排序算法主要包含以下步骤:1.

选择一个基准元素:

从列表中选择一个元素作为基准。 2.

分区:

将列表划分为两部分:小于基准元素的部分和大于基准元素的部分。 3.

递归:

对两个分区中的每个部分重复步骤 1 和 2,直到所有部分都排序好。

图解

以下是一个快速排序算法的分步图解:

步骤 1:选择基准元素

![图 1:选择基准元素](https://www.cs.usfca.edu/~galles/visualization/ComparisonSortApplet.html#quicksort)

从列表中选择一个元素作为基准。通常选择列表的中间元素或随机元素。

在本例中,选择 50 作为基准。

步骤 2:分区

![图 2:分区](https://www.cs.usfca.edu/~galles/visualization/ComparisonSortApplet.html#quicksort)

从列表的末尾开始遍历,找到第一个小于基准的元素。

将该元素交换到第一个小于基准的部分。

从列表的开头开始遍历,找到第一个大于基准的元素。

将该元素交换到第二个大于基准的部分。

重复这些步骤,直到遍历完整个列表。

步骤 3:递归

![图 3:递归](https://www.cs.usfca.edu/~galles/visualization/ComparisonSortApplet.html#quicksort)

对小于基准的部分递归应用快速排序算法。

对大于基准的部分递归应用快速排序算法。

重复步骤

重复步骤 1 到 3,直到列表的每个部分都排序好。

伪代码

以下是一个快速排序算法的伪代码:```python def quick_sort(arr):if len(arr) <= 1:return arrpivot = 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) ```

标签列表