在没有电脑的情况下,可以通过纸和笔来理清快速排序的思路。以下是一个简化的快速排序的伪代码:

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

现在我们通过纸和笔来理清快速排序的思路:

  1. 准备一张纸和一支笔,将纸分成若干方格,每个方格代表一个变量或者数组元素。

  2. 根据伪代码开始编写快速排序的流程。画出一个方格表示 arr 数组,将数组中的元素填入方格中。

  3. 根据 quickSort 函数的伪代码,画出一个方格表示 low 变量和一个方格表示 high 变量。填入初始值(即数组的起始索引和结束索引)。

  4. 按照 if 语句的判断条件,判断 low 是否小于 high。如果是,则继续执行 if 语句块内的代码。

  5. 根据 partition 函数的伪代码,画出一个方格表示 pivot 变量,并从 arr 数组中选择一个元素作为主元,并填入 pivot 方格中。

  6. 根据 partition 函数的伪代码,画出一个方格表示 i 变量,并将其初始值设为 low - 1

  7. 根据 for 循环语句的伪代码,画出一个方格表示 j 变量,并将其初始值设为 low

  8. 按照 for 循环语句的判断条件,判断 j 是否小于 high - 1。如果是,则继续执行 for 循环语句块内的代码。

  9. 根据 if 语句的判断条件,判断 arr[j] 是否小于 pivot。如果是,则继续执行 if 语句块内的代码。

  10. 根据 if 语句块内的代码,画出两个方格表示 ij 变量,并交换 arr[i]arr[j]

  11. 根据 for 循环语句的伪代码,将 j 的值加一。

  12. 根据 partition 函数的伪代码,画出一个方格表示 i+1,并将其填入。

  13. 根据 partition 函数的伪代码,画出一个方格表示 i+1high,并进行交换 arr[i+1]arr[high]

  14. 根据 partition 函数的伪代码,返回 i+1

  15. 根据 quickSort 函数的伪代码,将 pivotIndex 的值填入一个方格。

  16. 根据 quickSort 函数的伪代码,递归调用 quickSort(arr, low, pivotIndex - 1)quickSort(arr, pivotIndex + 1, high)

  17. 根据递归调用的伪代码,将 lowhigh 的值更新为新的范围。

  18. 重复步骤4-17,直到不满足 if 语句的判断条件。

以上是通过纸和笔从伪代码中理清快速排序思路的一种方法。可以根据个人习惯和需求进行适当的调整和改进。

手把手教你:用纸笔理解快速排序算法

原文地址: https://www.cveoy.top/t/topic/qvFA 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录