快速排序算法Python实现

快速排序原理和步骤

快速排序是一种高效的排序算法,基于分治法(Divide and Conquer)来实现。其基本思想是通过一次排序将数组分成两部分,其中一部分的所有元素都小于另一部分,然后递归地对这两部分进行排序。以下是快速排序的详细步骤:

1. 选择基准元素

首先,从数组中选择一个基准元素(pivot)。基准元素的选择方法有多种,例如选择第一个元素、最后一个元素、中间元素或随机选择一个元素。基准元素用于将数组分成两部分。

2. 分区

通过遍历数组,将所有小于基准元素的元素放到基准元素的左边,所有大于基准元素的元素放到基准元素的右边。这个过程称为分区(partitioning)。分区后,基准元素的位置是其在最终排序数组中的正确位置。

3. 递归排序

对基准元素左边的子数组和右边的子数组分别递归地应用快速排序。这个过程将不断分割和排序子数组,直到所有子数组的长度为1,表示数组已经有序。

4. 合并

由于快速排序是原地排序(in-place sorting),不需要额外的合并步骤。递归过程结束后,整个数组已经有序。

快速排序的完整步骤

  1. 选择基准: 选择一个基准元素。
  2. 分区: 将数组分成两部分,一部分小于基准元素,另一部分大于基准元素。
  3. 递归排序: 递归地对基准元素左边和右边的子数组进行排序。
  4. 完成: 递归结束后,数组有序。

快速排序的伪代码

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // 获取分区点
        int pi = partition(arr, low, high);

        // 对分区点左边的子数组进行递归排序
        quickSort(arr, low, pi - 1);

        // 对分区点右边的子数组进行递归排序
        quickSort(arr, pi + 1, high);
    }
}

int partition(vector<int>& arr, int low, int high) {
    // 选择最后一个元素作为基准
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++;
            // 交换 arr[i] 和 arr[j]
            swap(arr[i], arr[j]);
        }
    }
    // 交换 arr[i + 1] 和 arr[high] (或基准)
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

Python实现:

def quick_sort(arr):
    """
    对数组进行快速排序
    :param arr: 待排序的数组
    :return: 已排序的数组
    """
    # 如果数组的长度为0或1,直接返回数组
    if len(arr) <= 1:
        return arr

    # 选择数组的最后一个元素作为基准
    pivot = arr[-1]

    # 定义两个空列表,分别存放小于和大于基准的元素
    left = []
    right = []

    # 遍历数组(不包括最后一个元素,即基准)
    for element in arr[:-1]:
        if element < pivot:
            left.append(element)
        else:
            right.append(element)

    # 递归地对左右两个子数组进行快速排序,并合并
    return quick_sort(left) + [pivot] + quick_sort(right)



相关推荐

  1. 快速排序算法Python实现

    2024-07-10 07:36:04       6 阅读
  2. (算法入门)基于python实现快速排序

    2024-07-10 07:36:04       13 阅读
  3. 快速排序算法的基本思想以及Python实现

    2024-07-10 07:36:04       3 阅读
  4. 快速排序算法Python版)

    2024-07-10 07:36:04       14 阅读
  5. C语言实现快速排序算法

    2024-07-10 07:36:04       13 阅读
  6. 排序算法——快速排序

    2024-07-10 07:36:04       42 阅读

最近更新

  1. MySQL-显示所有错误信息

    2024-07-10 07:36:04       0 阅读
  2. Python 爬虫技术 第06节 HTTP协议与Web基础知识

    2024-07-10 07:36:04       0 阅读
  3. Oracle19.24发布,打补丁到19.24

    2024-07-10 07:36:04       0 阅读
  4. android audio 相机按键音:(一)资源加载与替换

    2024-07-10 07:36:04       0 阅读

热门阅读

  1. python爬虫入门(二)之Requests库

    2024-07-10 07:36:04       4 阅读
  2. RTK_ROS_导航(4):ROS中空地图的生成与加载

    2024-07-10 07:36:04       8 阅读
  3. PCL + Qt + Ribbon 风格(窗口自由组合) demo展示

    2024-07-10 07:36:04       15 阅读
  4. Android Studio Download Gradle 时慢问题解决

    2024-07-10 07:36:04       5 阅读
  5. ASPICE是汽车软件开发中的质量保证流程

    2024-07-10 07:36:04       6 阅读
  6. 游戏开发面试题2

    2024-07-10 07:36:04       9 阅读
  7. 4.10-7.9

    2024-07-10 07:36:04       7 阅读
  8. Django ModelForm用法详解 —— Python

    2024-07-10 07:36:04       6 阅读