手把手教你:用纸笔理解快速排序算法
在没有电脑的情况下,可以通过纸和笔来理清快速排序的思路。以下是一个简化的快速排序的伪代码:
quickSort(arr, low, high)
if low < high
pivotIndex = partition(arr, low, high)
quickSort(arr, low, pivotIndex - 1)
quickSort(arr, pivotIndex + 1, high)
partition(arr, low, high)
pivot = arr[high]
i = low - 1
for j = low to high - 1
if arr[j] < pivot
i = i + 1
swap arr[i] and arr[j]
swap arr[i + 1] and arr[high]
return i + 1
现在我们通过纸和笔来理清快速排序的思路:
-
准备一张纸和一支笔,将纸分成若干方格,每个方格代表一个变量或者数组元素。
-
根据伪代码开始编写快速排序的流程。画出一个方格表示
arr数组,将数组中的元素填入方格中。 -
根据
quickSort函数的伪代码,画出一个方格表示low变量和一个方格表示high变量。填入初始值(即数组的起始索引和结束索引)。 -
按照
if语句的判断条件,判断low是否小于high。如果是,则继续执行if语句块内的代码。 -
根据
partition函数的伪代码,画出一个方格表示pivot变量,并从arr数组中选择一个元素作为主元,并填入pivot方格中。 -
根据
partition函数的伪代码,画出一个方格表示i变量,并将其初始值设为low - 1。 -
根据
for循环语句的伪代码,画出一个方格表示j变量,并将其初始值设为low。 -
按照
for循环语句的判断条件,判断j是否小于high - 1。如果是,则继续执行for循环语句块内的代码。 -
根据
if语句的判断条件,判断arr[j]是否小于pivot。如果是,则继续执行if语句块内的代码。 -
根据
if语句块内的代码,画出两个方格表示i和j变量,并交换arr[i]和arr[j]。 -
根据
for循环语句的伪代码,将j的值加一。 -
根据
partition函数的伪代码,画出一个方格表示i+1,并将其填入。 -
根据
partition函数的伪代码,画出一个方格表示i+1和high,并进行交换arr[i+1]和arr[high]。 -
根据
partition函数的伪代码,返回i+1。 -
根据
quickSort函数的伪代码,将pivotIndex的值填入一个方格。 -
根据
quickSort函数的伪代码,递归调用quickSort(arr, low, pivotIndex - 1)和quickSort(arr, pivotIndex + 1, high)。 -
根据递归调用的伪代码,将
low和high的值更新为新的范围。 -
重复步骤4-17,直到不满足
if语句的判断条件。
以上是通过纸和笔从伪代码中理清快速排序思路的一种方法。可以根据个人习惯和需求进行适当的调整和改进。
原文地址: https://www.cveoy.top/t/topic/qvFA 著作权归作者所有。请勿转载和采集!