首页 > 编程语言 >CSP-J 算法基础 快速排序

CSP-J 算法基础 快速排序

时间:2024-09-13 19:51:03浏览次数:3  
标签:arr 基准值 int 分区 算法 数组 排序 CSP

文章目录


前言

快速排序(QuickSort)是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它采用分治策略(Divide and Conquer)来将一个大的问题分解为多个更小的问题,从而高效地进行排序。快速排序在最坏情况下的时间复杂度为O(n²),但在大多数情况下,其时间复杂度为O(n log n),因此被广泛应用于实际的排序任务中。快速排序的基本思想是通过一个基准元素(pivot)将待排序数组分为两部分,其中一部分的所有元素都小于基准元素,另一部分的所有元素都大于基准元素,然后递归地对这两部分进行排序。


分治思想

分治思想是一种解决复杂问题的方法,它的核心思路就是把一个大问题分成若干个较小的、相对独立的子问题,分别解决这些小问题,再将它们的结果合并,得到整个问题的解。

什么时候使用分治法?

  • 问题可以被分解成相似的小问题:如果问题能够拆分成规模较小的同类问题,这就适合用分治法。比如归并排序,排序一个大数组可以拆分成两个小数组排序。
  • 子问题独立解决:这些小问题之间没有太多依赖,可以单独处理。比如在二分查找中,判断出目标值在哪一半后,可以忽略另一半。
  • 可以通过合并子问题的结果解决原问题:各个子问题的解可以组合起来得到整个问题的解。比如在求最大子数组和时,可以通过左半部分、右半部分和中间部分的最大值得出整体的最大值。

举几个例子:

  1. 归并排序
    归并排序就是一个典型的分治算法。它先把数组分成两半,分别对两部分排序,然后把它们合并在一起。每次的合并操作都是将两个已经排好序的子数组组合成一个有序的数组,最终得到完整的有序数组。

  2. 二分查找
    当你在一个排好序的数组中查找一个目标数时,可以通过将数组一分为二,检查中间的值。如果中间的值比目标值大,就在左半部分继续查找;如果比目标值小,就在右半部分查找。这个过程不断地将问题规模缩小,直到找到目标数。

  3. 快速排序
    快速排序也是一种分治算法。它首先选择一个基准数(通常是数组中的一个值),然后将数组划分为两部分:比基准数小的放一边,比基准数大的放另一边。接着,对左右两部分分别进行递归排序,最终合并成一个有序数组。

  4. 最大子数组问题
    这个问题是找出数组中具有最大和的连续子数组。可以将数组分成两半,分别求解左半部分、右半部分和跨越中间部分的最大子数组,然后取三者中的最大值。

分治法的核心就是将大问题“拆分”成可以“独立”解决的“小问题”,然后把各个小问题的解“合并”成最终结果。这种方法特别适合处理递归问题,或是那些在分解后可以并行处理的情况。

快速排序

快速排序(Quicksort)是一种高效的排序算法,它通过递归地分解问题来排序。其基本原理是分治思想,具体过程如下:

  1. 选择基准值(Pivot):从数组中选取一个元素作为基准值(通常可以选择第一个、最后一个、中间的元素,或者随机选择)。
  2. 分区(Partition):将数组中的其他元素与基准值进行比较,比基准值小的放到它的左边,比基准值大的放到它的右边。此时,基准值的位置就固定了。
  3. 递归排序:对基准值左右的两个子数组,分别递归执行上述步骤,直到子数组的长度为1或0,表示无需继续排序。

具体例子

我们用数组 [8, 3, 1, 7, 0, 10, 2] 来演示快速排序的过程。

步骤 1:选择基准值

假设选择数组的第一个元素 8 作为基准值。

步骤 2:分区

把剩下的元素与基准值 8 比较:

  • 小于 8 的放在左边:[3, 1, 7, 0, 2]
  • 大于 8 的放在右边:[10]

分区后,数组变为:[3, 1, 7, 0, 2] [8] [10]

步骤 3:递归排序左边部分 [3, 1, 7, 0, 2]

选取左边数组的第一个元素 3 作为基准值,进行分区:

  • 小于 3 的放左边:[1, 0, 2]
  • 大于 3 的放右边:[7]

分区后,左边数组变为:[1, 0, 2] [3] [7]

步骤 4:递归排序 [1, 0, 2]

选取 1 作为基准值,进行分区:

  • 小于 1 的放左边:[0]
  • 大于 1 的放右边:[2]

分区后:[0] [1] [2]

至此,左边部分已经排好序:[0, 1, 2]

步骤 5:合并左边部分

将排好序的左边部分与之前的基准值 3 和右边部分 [7] 合并:
[0, 1, 2, 3, 7]

步骤 6:合并整个数组

最后,将左边排序好的部分 [0, 1, 2, 3, 7] 与基准值 8 和右边部分 [10] 合并,得到最终结果:
[0, 1, 2, 3, 7, 8, 10]

快速排序的步骤总结:

  1. 选定基准值;
  2. 分区为两个子数组;
  3. 递归排序子数组;
  4. 合并排序结果。

这个过程展示了如何通过反复分解和排序来将数组有序化。

当右边部分有两个及以上的元素时,分区过程和排序步骤类似,只不过要处理更多的元素。让我们用一个例子详细解释一下:

假设我们有数组 [8, 3, 1, 7, 0, 10, 2, 12, 9],选择 8 作为基准值,进行分区和排序:

快速排序的第二个例子

初始状态

原始数组:[8, 3, 1, 7, 0, 10, 2, 12, 9]

第一步:分区

选择 8 作为基准值,将数组分为两部分:

  • 小于 8 的元素:[3, 1, 7, 0, 2]
  • 大于 8 的元素:[10, 12, 9]

分区后数组变为:[3, 1, 7, 0, 2] [8] [10, 12, 9]

第二步:递归排序右边部分 [10, 12, 9]

选择基准值

选择右边部分的第一个元素 10 作为基准值。

分区

将右边部分 [10, 12, 9] 与基准值 10 比较:

  • 小于 10 的放左边:[9]
  • 大于 10 的放右边:[12]

分区后数组变为:[9] [10] [12]

至此,右边部分已经排好序。

第三步:递归排序左边部分 [3, 1, 7, 0, 2]

选择基准值

选择左边部分的第一个元素 3 作为基准值。

分区

将左边部分 [3, 1, 7, 0, 2] 与基准值 3 比较:

  • 小于 3 的放左边:[1, 0, 2]
  • 大于 3 的放右边:[7]

分区后左边部分变为:[1, 0, 2] [3] [7]

递归排序 [1, 0, 2]
选择基准值

选择 1 作为基准值。

分区

[1, 0, 2] 与基准值 1 比较:

  • 小于 1 的放左边:[0]
  • 大于 1 的放右边:[2]

分区后:[0] [1] [2]

最终合并

将排好序的部分合并:

  • 左边部分:[0, 1, 2, 3, 7]
  • 中间部分:[8]
  • 右边部分:[9, 10, 12]

最终得到排序后的数组:[0, 1, 2, 3, 7, 8, 9, 10, 12]

总结

  1. 选择基准值:从数组中选择一个元素作为基准值。
  2. 分区:将数组分成两部分,一部分小于基准值,另一部分大于基准值。
  3. 递归排序:对分区后的每个子数组递归执行相同的步骤。
  4. 合并:将排序好的子数组合并成最终结果。

这种方法利用递归将问题分解成小问题,逐步解决,每次处理的子数组规模逐渐减小,直到每个子数组都只包含一个元素或为空,最终得到有序的数组。

时间与空间复杂度

快速排序(Quicksort)是一种高效的排序算法,其时间和空间复杂度如下:

时间复杂度

  1. 平均时间复杂度

    • O(n log n):这是快速排序在大多数情况下的时间复杂度。其原因是每次分区操作将问题规模减少一半,而分区操作需要遍历数组,因此在大多数情况下,快速排序的时间复杂度是 O(n log n)。
  2. 最坏时间复杂度

    • O(n^2):最坏情况下,快速排序的时间复杂度为 O(n^2)。最坏情况发生在每次选择的基准值都是当前数组的最小值或最大值,导致每次只能将一个元素固定到正确位置,这样分区操作不均匀,最终导致时间复杂度为平方级别。例如,当数组已经是排序好的或完全逆序时,选择的基准值可能会导致最坏情况。
  3. 最好时间复杂度

    • O(n log n):在最佳情况下,基准值总能将数组分成接近均等的两个部分,每次分区都能将问题规模减半,从而使时间复杂度达到 O(n log n)。

空间复杂度

  1. 空间复杂度
    • O(log n):快速排序的空间复杂度主要取决于递归调用的深度。在平均情况下,递归调用的深度是 O(log n),因为每次分区将问题规模减少一半。然而,由于递归的调用栈的深度可以达到 n(在最坏情况下),空间复杂度可能达到 O(n),但通常情况下是 O(log n)。

总结:

  • 时间复杂度

    • 最好情况:O(n log n)
    • 平均情况:O(n log n)
    • 最坏情况:O(n^2)
  • 空间复杂度

    • 平均情况:O(log n)
    • 最坏情况:O(n) (主要是递归调用栈的深度)

快速排序在实际应用中通常表现得非常高效,特别是在平均情况下,因为它能快速地将大部分元素定位到正确的位置。然而,选择适当的基准值(例如使用随机选择或“三数取中法”)可以有效减少最坏情况发生的可能性,提高算法的实际性能。

编程实现快速排序

#include <stdio.h>

// 函数声明
void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
void printArray(int arr[], int size);

int main() {
    int arr[] = { 8, 3, 1, 7, 0, 10, 2, 12, 9 };
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组:");
    printArray(arr, size);

    quickSort(arr, 0, size - 1);

    printf("排序后的数组:");
    printArray(arr, size);

    return 0;
}

/*
low:表示待排序子数组的起始索引。
high:表示待排序子数组的结束索引(包括该索引)。
*/
// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        //pi就是i+1:第一次分组的分界线
        int pi = partition(arr, low, high);

        printf("基准值的索引位置:%d\n", pi);
        printf("排序后数组的状态:");
        printArray(arr, high + 1);

        quickSort(arr, low, pi - 1);  // 对基准值左侧的子数组进行排序
        quickSort(arr, pi + 1, high); // 对基准值右侧的子数组进行排序
    }
}

// 分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准值
    int i = (low - 1);     // 小于基准值的元素的索引

    printf("基准值:%d\n", pivot);

    //与基准值比较并互换位置
    for (int j = low; j <= high - 1; j++) {
        printf("i:%d pivot:%d arr[j]:%d j:%d\n", i, pivot, arr[j],j);
        if (arr[j] < pivot) {
            i++;
            // 交换 arr[i] 和 arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;

            printf("交换元素:%d 和 %d\n", arr[i], arr[j]);
            printf("数组状态:");
            printArray(arr, high + 1);
        }
    }
    // 交换基准值与 arr[i + 1]
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    printf("将基准值 %d 移到索引 %d\n", arr[i + 1], i + 1);
    printf("数组状态:");
    printArray(arr, high + 1);

    return (i + 1);
}

// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}


总结

在实现快速排序时,关键步骤包括选择基准元素、分区操作和递归排序。通过不断选择基准元素并将数组分区,快速排序将问题规模逐步减小,最终实现排序。快速排序的效率受基准选择的影响较大,选择好的基准元素可以显著提高排序性能。尽管最坏情况下的时间复杂度为O(n²),适当的优化(如随机选择基准元素或使用“三数取中法”)可以有效避免这种情况,使其在实际应用中表现出色。通过这些优化,快速排序成为一种高效、实用的排序算法,广泛应用于各种计算机科学和工程领域。

标签:arr,基准值,int,分区,算法,数组,排序,CSP
From: https://blog.csdn.net/m0_62599305/article/details/142216643

相关文章

  • 南沙csp-j/s一对一家教陈老师解题:1317:【例5.2】组合的输出
    ​ 【题目描述】排列与组合是常用的数学方法,其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n),我们可以简单地将n个元素理解为自然数1,2,…,n,从中任取r个数。现要求你用递归的方法输出所有组合。例如n=5,r=3,所有组合为:123 124 125 134 135 14......
  • A*算法.
    A算法*保证一定有解,不然算法不如dfs;无解会很慢,只能先写写去试试179.八数码在一个3×3的网格中,1∼8这8个数字和一个x恰好不重不漏地分布在这3×3的网格中。例如:123x46758在游戏过程中,可以把x与其上、下、左、右四个方向之一的数字交换(如果存在)。我们......
  • 代码随想录算法 - 二叉树3
    题目1513.找树左下角的值给定一个二叉树的根节点root,请找出该二叉树的最底层最左边节点的值。假设二叉树中至少有一个节点。示例1:输入:root=[2,1,3]输出:1示例2:输入:[1,2,3,4,null,5,6,null,null,7]输出:7提示:二叉树的节点个数的范围是[1,104]-......
  • Python中如何实现列表的排序
    在Python中,实现列表(List)的排序是一项基础且常用的操作。Python提供了多种方式来对列表进行排序,包括使用内置函数、方法以及自定义排序逻辑。下面将详细探讨Python中实现列表排序的多种方法,包括sort()方法、sorted()函数、以及利用lambda函数和functools.cmp_to_key()函数来自定......
  • 信息学奥赛初赛天天练-88-CSP-S2023阅读程序1-数据类型、unsigned 关键字、二进制、位
    信息学奥赛初赛天天练-88-CSP-S2023阅读程序1-数据类型、unsigned关键字、二进制、位运算、左移、右移、异或运算PDF文档公众号回复关键字:202409132023CSP-S阅读程序1判断题正确填√,错误填⨉;除特殊说明外,判断题1.5分,选择题3分,共计40分)01#include<iostream>......
  • 国家标准 | CSPM-3中级项目管理专业人员认证
    10月底全国CSPM-3考试现场1CSPM介绍项目管理专业人员能力评价(ChinaStandardsProjectManagement,CSPM)是指依据中国标准开展的项目管理专业人员能力评价。它是由中国标准化协会(全国项目管理标准化技术委员会秘书处)设立,运用已发布的项目管理国家标准(国际标准、团体标准),针对项目管理......
  • 文心一言 VS 讯飞星火 VS chatgpt (346)-- 算法导论23.2 5题
    五、假定图中边的权重取值全部为整数,且在范围内。Prim算法最快能多快?如果边的权重取值范围在1到某个常数之间呢?如果要写代码,请用go语言。文心一言:Prim算法是一种用于寻找加权无向图的最小生成树的贪心算法。其时间复杂度主要取决于实现方式。在标准实现中,Prim算法通常使用优先队列(......
  • 行驶证识别算法以及在中科麒麟系统的离线部署
    行驶证作为车辆合法上路的证明文件,包含车辆的基本信息和车主的详细资料,是政府部门、保险公司、租赁公司以及交通管理系统中常用的文档。在日常业务操作中,快速、准确地录入行驶证信息对于提高工作效率、减少人工错误有着重要意义。然而,传统的手工输入过程不仅费时,还存在一定的错误......
  • 为什么国家大力推行cspm证书
    PMP备考资料免费领国家重视CSPM证书(项目管理专业人员能力评价等级证书)的原因有几个方面:国家标准背书:CSPM证书是根据中国国家标准《项目管理专业人员能力评价要求》(GB/T41831-2022)制定的。这意味着CSPM证书代表了中国项目管理领域的最高标准与权威认可。符合国情:CSPM认证更加符合中......
  • LRU算法原理及其实现
    一、LRU是什么        LRU算法的全称是“LeastRecentlyUsed”,即“最近最少使用”算法。LRU算法的基本思想是,当缓存空间已满时,优先淘汰最近最少使用的缓存数据,以腾出更多的缓存空间。因此,LRU算法需要维护一个缓存访问历史记录,以便确定哪些缓存数据是最近最少使用的。......