快速排序原理概述

快速排序是一种高效的排序算法，采用分治法的思想。其基本步骤为：选择一个基准元素，将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于基准元素，然后分别对左右两部分递归地进行快速排序，最终得到一个有序的数组。

以中间元素为基准的快速排序步骤

1. 基准元素选择：选取数组中间位置的元素作为基准元素。
2. 分区操作：将数组中小于等于基准元素的数放到左边，大于基准元素的数放到右边。
3. 递归排序：对左右两部分子数组分别递归执行快速排序。

Python 代码实现

def quick_sort(arr):
    # 基准情况：如果数组长度小于等于 1，说明数组已经有序，直接返回
    if len(arr) <= 1:
        return arr
    else:
        # 选择中间位置的元素作为基准元素
        mid_index = len(arr) // 2
        pivot = arr[mid_index]

        # 初始化三个列表，分别存储小于、等于和大于基准元素的数
        left = []
        middle = []
        right = []

        # 遍历数组，将元素分类到不同的列表中
        for num in arr:
            if num < pivot:
                left.append(num)
            elif num == pivot:
                middle.append(num)
            else:
                right.append(num)

        # 递归地对左右两部分子数组进行快速排序，并合并结果
        return quick_sort(left) + middle + quick_sort(right)


# 测试代码
unsorted_array = [3, 6, 8, 10, 1, 2, 1]
sorted_array = quick_sort(unsorted_array)
print("排序前的数组:", unsorted_array)
print("排序后的数组:", sorted_array)

代码解释

1. 基准情况判断：在 quick_sort 函数中，首先判断数组的长度是否小于等于 1。如果是，直接返回该数组，因为长度小于等于 1 的数组本身就是有序的。
2. 基准元素选择：通过 len(arr) // 2 计算出数组中间位置的索引，将该位置的元素作为基准元素。
3. 分区操作：遍历数组中的每个元素，根据元素与基准元素的大小关系，将其添加到 left、middle 或 right 列表中。
4. 递归排序：对 left 和 right 列表分别递归调用 quick_sort 函数，然后将排序好的 left 列表、存储基准元素的 middle 列表和排序好的 right 列表合并起来。

复杂度分析

• 时间复杂度：平均情况下为 $O(n log n)$，最坏情况下为 $O(n^2)$。
• 空间复杂度：平均情况下为 $O(log n)$，最坏情况下为 $O(n)$。

通过以上步骤和代码，你可以理解并实现以中间元素为基准的快速排序算法。

快速排序原理回顾

快速排序是一种分治算法，其核心思想是选择一个基准元素（pivot），把数组分成两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于基准元素，接着分别对左右两部分递归地进行快速排序，直至整个数组有序。

详细执行过程分析

下面以数组 [5, 3, 8, 4, 2] 为例，详细阐述快速排序的执行过程。

1. 初始状态

数组：[5, 3, 8, 4, 2]

2. 第一次分区操作

• 选择基准元素：选择第一个元素 5 作为基准元素。
• 分区过程：
  • 从数组的第二个元素开始，设置两个指针，一个指针 i 从左向右移动，另一个指针 j 从右向左移动。
  • 先让 j 指针向左移动，找到第一个小于基准元素 5 的元素，即 2；再让 i 指针向右移动，找到第一个大于基准元素 5 的元素，即 8。
  • 交换 8 和 2 的位置，此时数组变为 [5, 3, 2, 4, 8]。
  • 继续移动 i 和 j 指针，j 指针找到小于 5 的 4，i 指针找到大于 5 的元素时 i 已经超过 j 了，此时将基准元素 5 和 4 交换位置，数组变为 [4, 3, 2, 5, 8]。
  • 此时，基准元素 5 左边的元素 [4, 3, 2] 都小于它，右边的元素 [8] 都大于它。

3. 递归排序左子数组 [4, 3, 2]

• 选择基准元素：选择 4 作为基准元素。
• 分区过程：
  • j 指针找到小于 4 的 2，i 指针找到大于 4 的元素时 i 已经超过 j 了，将基准元素 4 和 2 交换位置，数组变为 [2, 3, 4]。
  • 此时基准元素 4 左边的元素 [2, 3] 都小于它，右边没有元素。

4. 递归排序左子数组 [2, 3] 的子数组

• 选择基准元素：选择 2 作为基准元素。
  • 因为只有两个元素，且 3 大于 2，无需交换，数组还是 [2, 3]。

5. 递归排序右子数组 [8]

由于右子数组只有一个元素，本身就是有序的。

Python 代码实现

def partition(arr, low, high):
    pivot = arr[low]
    i = low + 1
    j = high
    while True:
        while i <= j and arr[i] <= pivot:
            i = i + 1
        while i <= j and arr[j] >= pivot:
            j = j - 1
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
        else:
            break
    arr[low], arr[j] = arr[j], arr[low]
    return j


def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)


arr = [5, 3, 8, 4, 2]
quick_sort(arr, 0, len(arr) - 1)
print("排序后的数组:", arr)

代码解释

• partition 函数：该函数实现了分区操作，选择第一个元素作为基准元素，通过两个指针 i 和 j 移动，将小于基准元素的元素放到左边，大于基准元素的元素放到右边，最后返回基准元素的最终位置。
• quick_sort 函数：这是递归函数，它会不断调用 partition 函数对数组进行分区，然后递归地对左右子数组进行排序。

复杂度分析

• 时间复杂度：平均情况下是 $O(n log n)$，最坏情况下是 $O(n^2)$。
• 空间复杂度：平均情况下是 $O(log n)$，最坏情况下是 $O(n)$。

通过上述步骤和代码，你可以清晰地看到快速排序的执行过程，以及如何使用 Python 实现该算法。

快速排序基本原理

快速排序是一种分治算法，它的基本思想是通过选择一个基准元素（pivot），将数组分成两部分，使得左边部分的所有元素都小于等于基准元素，右边部分的所有元素都大于基准元素，然后分别对左右两部分递归地进行快速排序，最终得到一个有序的数组。

递归版本快速排序执行过程

以下是递归版本快速排序的详细执行步骤：

1. 选择基准元素：从数组中选择一个元素作为基准元素。通常可以选择数组的第一个元素、最后一个元素或者中间元素。
2. 分区操作：将数组中的元素重新排列，使得所有小于等于基准元素的元素位于基准元素的左边，所有大于基准元素的元素位于基准元素的右边。这个过程称为分区（partitioning）。
3. 递归排序：对基准元素左边和右边的子数组分别递归地应用快速排序算法，直到子数组的长度为 0 或 1，此时子数组已经有序。

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)

例题分析

假设我们有一个数组 [3, 6, 8, 10, 1, 2, 1]，下面我们来详细分析快速排序的执行过程。

初始数组

[3, 6, 8, 10, 1, 2, 1]

第一次分区

• 选择基准元素 pivot = 3。
• 小于等于 3 的元素组成的子数组 less_than_pivot = [1, 2, 1]。
• 大于 3 的元素组成的子数组 greater_than_pivot = [6, 8, 10]。

递归排序左子数组 [1, 2, 1]

• 选择基准元素 pivot = 1。
• 小于等于 1 的元素组成的子数组 less_than_pivot = [1]。
• 大于 1 的元素组成的子数组 greater_than_pivot = [2]。
• 递归排序 [1]，由于长度为 1，直接返回 [1]。
• 递归排序 [2]，由于长度为 1，直接返回 [2]。
• 合并结果得到 [1, 1, 2]。

递归排序右子数组 [6, 8, 10]

• 选择基准元素 pivot = 6。
• 小于等于 6 的元素组成的子数组 less_than_pivot = []。
• 大于 6 的元素组成的子数组 greater_than_pivot = [8, 10]。
• 递归排序 []，由于长度为 0，直接返回 []。
• 递归排序 [8, 10]：
  • 选择基准元素 pivot = 8。
  • 小于等于 8 的元素组成的子数组 less_than_pivot = []。
  • 大于 8 的元素组成的子数组 greater_than_pivot = [10]。
  • 递归排序 []，由于长度为 0，直接返回 []。
  • 递归排序 [10]，由于长度为 1，直接返回 [10]。
  • 合并结果得到 [8, 10]。
• 合并结果得到 [6, 8, 10]。

合并最终结果

将左子数组 [1, 1, 2]、基准元素 [3] 和右子数组 [6, 8, 10] 合并，得到最终的有序数组 [1, 1, 2, 3, 6, 8, 10]。

测试代码

arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("排序前的数组:", arr)
print("排序后的数组:", sorted_arr)

通过以上步骤，你可以清晰地看到递归版本快速排序的执行过程。每次分区操作都会将数组分成两部分，然后递归地对这两部分进行排序，最终得到一个有序的数组。

快速排序通常采用递归的方式实现，但递归可能会在处理大规模数据时导致栈溢出问题，因此可以使用非递归的方式，借助栈来模拟递归调用的过程。以下是对非递归版本快速排序的详细介绍，包含基本思想、实现步骤、Python 代码及代码解释。

基本思想

非递归的快速排序利用栈来模拟递归调用的过程。递归调用时，系统会自动使用栈来保存每一层的调用信息；非递归实现时，需要手动维护一个栈，在栈中存储待排序子数组的起始和结束索引。

实现步骤

1. 初始化栈：将整个数组的起始和结束索引压入栈中。
2. 循环处理栈：当栈不为空时，从栈中弹出一个子数组的起始和结束索引。
3. 分区操作：对弹出的子数组进行分区操作，得到基准元素的最终位置。
4. 更新栈：如果基准元素左边的子数组还有元素，将其起始和结束索引压入栈；如果基准元素右边的子数组还有元素，同样将其起始和结束索引压入栈。
5. 重复步骤 2 - 4：直到栈为空，此时数组排序完成。

Python 代码实现

def partition(arr, low, high):
    # 选择最后一个元素作为基准元素
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i = i + 1
            # 交换元素
            arr[i], arr[j] = arr[j], arr[i]
    # 将基准元素放到正确的位置
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


def quick_sort_non_recursive(arr):
    # 初始化栈
    stack = []
    # 初始数组的起始和结束索引
    stack.append((0, len(arr) - 1))

    # 循环处理栈
    while stack:
        # 从栈中弹出一个子数组的起始和结束索引
        low, high = stack.pop()
        # 进行分区操作
        pivot_index = partition(arr, low, high)

        # 如果基准元素左边的子数组还有元素，将其起始和结束索引压入栈
        if pivot_index - 1 > low:
            stack.append((low, pivot_index - 1))

        # 如果基准元素右边的子数组还有元素，将其起始和结束索引压入栈
        if pivot_index + 1 < high:
            stack.append((pivot_index + 1, high))

    return arr


# 测试代码
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort_non_recursive(arr)
print("排序前的数组:", arr)
print("排序后的数组:", sorted_arr)

代码解释

1. partition 函数：该函数用于对给定的子数组进行分区操作，选择最后一个元素作为基准元素，将小于等于基准元素的元素放到左边，大于基准元素的元素放到右边，最后返回基准元素的最终位置。
2. quick_sort_non_recursive 函数：
   • 初始化一个栈，并将整个数组的起始和结束索引压入栈。
   • 进入循环，只要栈不为空，就从栈中弹出一个子数组的起始和结束索引。
   • 调用 partition 函数对该子数组进行分区操作，得到基准元素的最终位置。
   • 根据基准元素的位置，判断其左右子数组是否还有元素，如果有则将相应的起始和结束索引压入栈。
   • 循环结束后，数组排序完成。

复杂度分析

• 时间复杂度：平均情况下为 $O(n log n)$，最坏情况下为 $O(n^2)$。
• 空间复杂度：平均情况下为 $O(log n)$，最坏情况下为 $O(n)$。

通过以上步骤和代码，你可以理解并实现非递归版本的快速排序算法。

快速排序是一种高效的排序算法，它采用分治法的思想。下面为你详细介绍递归版本的快速排序算法，并给出 Python 代码示例，即使你是零基础也能轻松理解。

快速排序的基本思想

快速排序的核心在于选取一个基准元素（pivot），把数组分成两部分：一部分的元素都小于等于基准元素，另一部分的元素都大于基准元素。接着分别对这两部分递归地进行快速排序。

快速排序的步骤

1. 选择基准元素：从数组里挑选一个元素当作基准元素。
2. 分区操作：重新排列数组，让所有小于等于基准元素的元素位于基准元素左边，所有大于基准元素的元素位于基准元素右边。此操作结束后，基准元素就处于其最终的排序位置。
3. 递归排序：对基准元素左右两边的子数组分别递归地进行快速排序。

Python 代码实现

def quick_sort(arr):
    # 如果数组长度小于等于 1，说明已经有序，直接返回
    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 = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("排序前的数组:", arr)
print("排序后的数组:", sorted_arr)

代码解释

1. 基准情况：若数组长度小于等于 1，说明数组已经有序，直接返回该数组。
2. 选择基准元素：选取数组的第一个元素作为基准元素。
3. 分区操作：借助列表推导式把数组分成两部分：小于等于基准元素的元素组成的子数组和大于基准元素的元素组成的子数组。
4. 递归排序：对左右子数组分别递归地调用 quick_sort 函数，并将结果合并。

复杂度分析

• 时间复杂度：平均情况下为 $O(n log n)$，最坏情况下为 $O(n^2)$。
• 空间复杂度：平均情况下为 $O(log n)$，最坏情况下为 $O(n)$。

通过上述步骤和代码，你就能理解并实现递归版本的快速排序算法了。

什么是快速排序

快速排序是一种高效的排序算法，它运用了分治法的思想。其核心步骤是先从数组里选一个元素作为基准值，接着把数组分成两部分，一部分元素都小于等于基准值，另一部分元素都大于基准值，最后分别对这两部分继续进行排序。

递归版本快速排序的实现思路

1. 基准情况：若数组长度小于等于 1，意味着数组已经是有序的，可直接返回该数组。
2. 选择基准值：通常选取数组的第一个元素作为基准值。
3. 分区操作：将数组中小于等于基准值的元素放到左边，大于基准值的元素放到右边。
4. 递归排序：对基准值左右两边的子数组分别递归调用快速排序函数。

Python 代码实现

def quick_sort(arr):
    # 基准情况：如果数组长度小于等于 1，直接返回数组
    if len(arr) <= 1:
        return arr
    else:
        # 选择数组的第一个元素作为基准值
        pivot = arr[0]
        # 初始化两个空列表，用于存放小于等于基准值和大于基准值的元素
        less_than_pivot = []
        greater_than_pivot = []
        # 遍历数组中除基准值之外的元素
        for num in arr[1:]:
            if num <= pivot:
                # 如果元素小于等于基准值，添加到 less_than_pivot 列表
                less_than_pivot.append(num)
            else:
                # 如果元素大于基准值，添加到 greater_than_pivot 列表
                greater_than_pivot.append(num)
        # 递归地对 less_than_pivot 和 greater_than_pivot 列表进行快速排序
        # 并将结果与基准值合并
        return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)


# 测试代码
unsorted_list = [34, 12, 5, 78, 23, 45, 1]
sorted_list = quick_sort(unsorted_list)
print("排序前的列表:", unsorted_list)
print("排序后的列表:", sorted_list)

代码解释

1. 基准情况判断：在 quick_sort 函数里，先判断数组的长度是否小于等于 1。若满足条件，就直接返回数组，因为此时数组已经有序。
2. 基准值选择：选取数组的第一个元素当作基准值。
3. 分区操作：借助 for 循环遍历数组中除基准值之外的元素，把小于等于基准值的元素添加到 less_than_pivot 列表，大于基准值的元素添加到 greater_than_pivot 列表。
4. 递归调用：对 less_than_pivot 和 greater_than_pivot 列表分别递归调用 quick_sort 函数，再将排序后的结果与基准值合并。

复杂度分析

• 时间复杂度：平均情况下是 $O(n log n)$，最坏情况下为 $O(n^2)$。
• 空间复杂度：平均情况下为 $O(log n)$，最坏情况下是 $O(n)$。

总结

递归版本的快速排序借助分治法和递归的思想，把一个大的排序问题分解成多个小的排序问题。只要掌握了基准情况、基准值选择、分区操作和递归调用这些关键步骤，就能轻松理解和实现快速排序算法。

快速排序简介

快速排序（Quick Sort）是一种高效的排序算法，由 Tony Hoare 在 1959 年提出。它采用了分治法（Divide and Conquer）的策略，平均时间复杂度为 $O(n log n)$，最坏情况下为 $O(n^2)$。

快速排序的基本思想

快速排序的基本思想是：

1. 选择基准值：从数组中选择一个元素作为基准值（pivot）。
2. 分区操作：将数组中小于基准值的元素放到基准值的左边，大于基准值的元素放到基准值的右边。这个过程称为分区（partitioning）。
3. 递归排序：对基准值左右两边的子数组分别递归地进行快速排序。

Python 代码实现

def quick_sort(arr):
    # 如果数组长度小于等于 1，直接返回该数组
    if len(arr) <= 1:
        return arr
    else:
        # 选择第一个元素作为基准值
        pivot = arr[0]
        # 初始化两个空列表，分别用于存放小于等于基准值和大于基准值的元素
        left = []
        right = []
        # 遍历数组中除基准值之外的元素
        for num in arr[1:]:
            if num <= pivot:
                # 如果元素小于等于基准值，添加到 left 列表
                left.append(num)
            else:
                # 如果元素大于基准值，添加到 right 列表
                right.append(num)
        # 递归地对 left 和 right 列表进行快速排序，并将结果合并
        return quick_sort(left) + [pivot] + quick_sort(right)


# 测试代码
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("排序前的数组:", arr)
print("排序后的数组:", sorted_arr)

代码解释

1. 函数定义：quick_sort 函数接受一个数组 arr 作为参数。
2. 基准情况：如果数组的长度小于等于 1，说明数组已经有序，直接返回该数组。
3. 选择基准值：选择数组的第一个元素作为基准值 pivot。
4. 分区操作：遍历数组中除基准值之外的元素，将小于等于基准值的元素添加到 left 列表，大于基准值的元素添加到 right 列表。
5. 递归排序：对 left 和 right 列表分别递归地调用 quick_sort 函数，并将结果合并。

复杂度分析

• 时间复杂度：平均情况下为 $O(n log n)$，最坏情况下为 $O(n^2)$。
• 空间复杂度：平均情况下为 $O(log n)$，最坏情况下为 $O(n)$。

总结

快速排序是一种高效的排序算法，通过分治法将问题分解为更小的子问题。在 Python 中，我们可以使用递归的方式轻松实现快速排序。希望这个教程能帮助你理解快速排序的基本原理和实现方法。