算法实现 - 快速排序(Quick Sort) - 理解版

文章目录

  • 算法介绍
  • 算法分析
    • 核心思想
    • 三个版本运行过程
      • 挖坑法
      • Hoare 原版
      • 前后指针法
  • 算法稳定性和复杂度

算法介绍

快速排序是一种高效的排序算法,由英国计算机科学家C. A. R. Hoare在1960年提出,是对冒泡排序算法的一种改进。

该算法采用 分治策略,其基本思想:
选择一个基准元素(pivot),通过基准元素将待排序的序列分成两部分,一部分包含所有小于基准元素的元素,另一部分包含所有大于基准元素的元素,然后递归地对这两部分进行快速排序,最终使整个数组成为一个有序的序列。

算法分析

核心思想

  1. 选择基准:从数组中选择一个元素作为基准(pivot)。通常可以选择第一个元素、最后一个元素、随机元素或中间元素。
  2. 分区操作
    • 遍历数组,将小于基准的元素移动到基准左侧,大于基准的元素移动到右侧。这样基准元素就会被放置到其正确的排序位置。
    • 此步骤会让数组分成了两部分:左侧(小于基准)和右侧(大于基准)。
  3. 递归排序
    • 对于基准位置左侧和右侧的两个子数组,分别递归地运用快速排序。
    • 递归结束的条件是子数组的长度小于或等于 1,此时它们已经有序。
  4. 合并结果:合并已经排序好的子数组与基准,得到一个完整的有序数组。

三个版本运行过程

以数列 a[] = {40, 20, 30, 60, 10, 50} 作为分析案例;

挖坑法

在这里插入图片描述

分析:

x 取索引为0 的最左值 为 40,即x = 40。

  • 从"右 --> 左"查找小于x的数: 找到满足条件的数a[j]=10,此时 j=4,i=0;然后将a[j]赋值a[i],即将 a[4] 赋值给 a[0];接着从左往右遍历。
  • 从"左 --> 右"查找大于x的数: 找到满足条件的数a[i]=60,此时 i=3,j=4;然后将a[i]赋值a[j],即将 a[3] 赋值给 a[4];接着从右往左遍历。
  • 从"右 --> 左"查找小于x的数: 没有找到满足条件的数。当i>=j时,停止查找;然后将x赋值给a[i],即将 40 赋值给 a[3]。此趟遍历结束!

代码:

#include <stdio.h>/*** Quick sort by C Lang.** params:*   arr -- the data array*   left -- the first index of arr*   right -- the last index of arr**/
void quickSort(int arr[], int left, int right)
{// the arr is empty or left one elementif (left >= right){return;}// init dataint pivot = arr[left];int i = left, j = right;while (i < j){// right -> left: find the first element less than pivot// notice: when arr[j] meet the condition `arr[j] < pivot`, it will break the while loop, indicate that current element is less than pivot.while (i < j && arr[j] > pivot)j--;if (i < j){arr[i++] = arr[j];}// left -> right: find the first element great than pivotwhile (i < j && arr[i] < pivot)i++;if (i < j){arr[j--] = arr[i];}arr[i] = pivot; // The element has benn correctly placed in its corresponding positionquickSort(arr, left, i - 1);  // Recursive invoke in the left sub arrayquickSort(arr, i + 1, right); // Recursive invoke in the right sub array}
}/*** show array*/
void printArray(int array[], int n)
{for (size_t i = 0; i < n; i++){printf("%d ", array[i]);}printf("\n\n");
}int main()
{int arr[] = {40, 20, 30, 60, 10, 50};// calculate the length of a arrayint n = sizeof(arr) / sizeof(arr[0]);printf("before sort: \n");printArray(arr, n);// The third param must be `n -1`quickSort(arr, 0, n - 1);printf("after sort: \n");printArray(arr, n);return 0;
}

代码详见:GitHub 快速排序法 挖坑版

Hoare 原版

分析:

  • 选择基准值:快速排序的第一步是选择一个基准值(pivot)。通常可以选择数组的第一个元素,但为了提高排序效率,有时也会选择随机元素或使用其他策略。
  • 划分过程:使用两个指针,左指针和右指针,分别从数组的两端开始向中间移动。
  • 具体步骤:
    1. 左指针移动:左指针从左向右移动,直到找到一个大于或等于基准值的元素。
    2. 右指针移动:右指针从右向左移动,直到找到一个小于或等于基准值的元素。
    3. 交换元素:如果左指针指向的元素大于基准值,且右指针指向的元素小于基准值,则交换这两个元素。
    4. 继续移动指针:继续移动左右指针,直到它们相遇。
    5. 交换基准值:最后,将基准值与右指针指向的元素交换,确保基准值左侧的所有元素都不大于基准值,右侧的所有元素都不小于基准值。

代码:

#include <stdio.h>/*** swap two number*/
void swap(int *a, int *b)
{int temp = *a;*a = *b;*b = temp;
}/*** Quick sort by C Lang.** params:*   arr -- the data array*   left -- the first index of arr*   right -- the last index of arr**/
int partition(int arr[], int left, int right)
{// init dataint pivotIndex = left;int i = left, j = right;while (i < j){// right -> left: find the first element less than pivotwhile (i < j && arr[j] > arr[pivotIndex]){j--;}// left -> right: find the first element great than pivotwhile (i < j && arr[i] < arr[pivotIndex]){i++;}// after upper two loop, indicate that it is able to swapif (i < j)swap(&arr[i], &arr[j]);}// Swap the pivot with the element pointed by the right pointerswap(&arr[pivotIndex], &arr[j]);return j;
}void quickSort(int arr[], int left, int right)
{if (left < right){int pivotIndex = partition(arr, left, right);quickSort(arr, left, pivotIndex - 1);quickSort(arr, pivotIndex + 1, right);}
}/*** show array*/
void printArray(int array[], int n)
{for (size_t i = 0; i < n; i++){printf("%d ", array[i]);}printf("\n\n");
}int main()
{int arr[] = {40, 20, 30, 60, 10, 50};// calculate the length of a arrayint n = sizeof(arr) / sizeof(arr[0]);printf("before sort: \n");printArray(arr, n);// The third param must be `n -1`quickSort(arr, 0, n - 1);printf("after sort: \n");printArray(arr, n);return 0;
}

代码详见:GitHub 快速排序法 hoare版

前后指针法

前后指针法(也称为荷兰国旗问题解法)是快速排序中的一种高效实现方式。在这个方法中,通常将数组划分为三个部分:

  • 小于基准值的元素
  • 等于基准值的元素
  • 大于基准值的元素。

分析:

  • 变量初始化:

    • key 是基准元素的索引,初始为 left。
    • prev 是逻辑分区点之前的最后一个小于基准的元素的索引,开始等于 left。
    • cur 是当前遍历的元素索引,从 left + 1 开始。
  • 分区逻辑:

    • 使用 while 循环遍历数组,从 cur = left + 1 到 right。
    • 如果 a[cur] < a[key],则 prev 增加(指向下一个元素),并交换 a[prev] 和 a[cur],确保小于基准的元素移动到前面。
    • 即使 prev 和 cur 相等,也进行交换,这一步是为了简化逻辑,即不需要特判 prev 和 cur 相等的情况。实际上在交换时什么也不会变。
  • 基准交换:
    循环结束后,将基准值与 a[prev] 交换,把基准放置在正确的位置。

代码

#include <stdio.h>/*** swap two number*/
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}/*** Quick sort by C Lang.** params:*   arr -- the data array*   left -- the first index of arr*   right -- the last index of arr**/
int partition(int arr[], int left, int right) {int pivotIndex = left;int prev = left;int cur = left + 1;while (cur <= right) {if (arr[cur] < arr[pivotIndex] && ++prev != cur) {swap(&arr[prev], &arr[cur]);}cur++;}swap(&arr[prev], &arr[pivotIndex]);return prev;
}void quickSort(int arr[], int left, int right) {if (left < right) {int pivot_index = partition(arr, left, right);quickSort(arr, left, pivot_index - 1);quickSort(arr, pivot_index + 1, right);}
}void print_array(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {30, 40, 60, 10, 20, 50};int n = sizeof(arr) / sizeof(arr[0]);printf("Before sorting:\n");print_array(arr, n);quickSort(arr, 0, n - 1);printf("After sorting:\n");print_array(arr, n);return 0;
}

代码详见:GitHub 快速排序法 前后指针版

算法稳定性和复杂度

稳定性

这一点是因为在分区过程中,元素的相对顺序可能会改变。

具体来说,当我们交换元素以确保小于基准的元素在前,大于基准的在后时,相同元素的相对位置可能改变。

例如,如果两个相等的元素分别在基准的两侧,交换后它们的位置关系就被打破了。

举个例子:

示例数组:[ 3 a 3_a 3a, 1, 2, 3 b 3_b 3b]
这里的 3 a 3_a 3a, 3 b 3_b 3b 是两个不同位置的相同元素(相同的值但用下标区分,用于说明其在数组中的初始位置)。
根据实现可能不交换,但假设实现中等于基准的情况下它也移动,这里交换 3 b 3_b 3b 3 a 3_a 3a得到数组 [ 3 b 3_b 3b, 1, 2, 3 a 3_a 3a],顺序已经发生了变更。

时间复杂度

平均情况O(nlogn)

基本操作
快速排序的基本操作是划分和递归调用。

操作次数

  • 划分操作:每次划分操作将数组分为两部分。在平均情况下,我们假设每次划分都能将数组大致分为两个相等的部分。这意味着每次划分操作都会遍历整个数组一次,操作次数为 n。
  • 递归操作:由于每次划分都将数组分为两个大致相等的部分,所以每次递归调用处理的数组大小大约是前一次的一半。这个过程会一直持续到子数组的大小为1,此时不需要再进行划分。

对于大小为 n 的数组,快速排序的递归关系可以表示为:
T ( n ) = 2 T ( n 2 ) + n T(n) = 2T\left(\frac{n}{2}\right) + n T(n)=2T(2n)+n

  • T(n)是对大小为 n 的数组进行排序所需的总操作次数。
  • T( n 2 \frac{n}{2} 2n)表示对两个大小为 n 2 \frac{n}{2} 2n的子数组进行排序所需的操作次数。
  • n 是当前划分操作所需的总比较次数。

大O表示法
这种形式可以用主定理求解,符合主定理的标准形式,所以复杂度为:O(n log n)

分治算法主定理,点击看我的另外一篇文章

最差情况O( n 2 n^2 n2)

基本操作
快速排序的基本操作是划分和递归调用。

操作次数

在最坏情况下,每次划分操作只能将数组分成一个大小为 n−1 的部分和一个大小为 0 的部分(例如,当数组已经有序或每次都选择最大或最小元素作为基准时)。在这种情况下,递归关系式变为:

T ( n ) = T ( n − 1 ) + n T(n) = T(n - 1) + n T(n)=T(n1)+n

  • T(n - 1)是对大小为 n−1 的子数组进行排序所需的操作次数。
  • n 是当前划分操作所需的总比较次数。

上述等价于
T ( n ) = n + ( n − 1 ) + ( n − 2 ) + ( n − 3 ) + . . . + 2 + 1 = ( n + 1 ) n 2 = n 2 2 + n 2 T(n)= n + (n-1) + (n-2) + (n-3) + ... + 2 + 1 = \frac{(n + 1)n}{2} = \frac{n^2}{2} + \frac{n}{2} T(n)=n+(n1)+(n2)+(n3)+...+2+1=2(n+1)n=2n2+2n

大O表示法
上述用大O表示法为:O( n 2 n^2 n2)

空间复杂度

快速排序是一种递归算法。每次递归调用时,程序会在栈上保存当前调用的状态信息:

  • 平均情况下:
    • 快速排序以较好的概率实现了平均分区,递归调用的深度大约是树的高度,即 O(logn)。
    • 每次递归在栈上保存的信息量是常数级别的,例如数组的起始和结束索引、基准元素信息等。
  • 最坏情况下:
    • 如果每次选择的基准是最小或最大元素,导致极端不平衡的分区,递归深度达到 O(n)。
    • 这种情况会在已经排序的数组或逆序数组上发生。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/463996.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

设备搜索相关协议使用

一、实现原理 首先&#xff0c;Client -> Gateway : 发送 UDP 广播包&#xff08;含厂商自定义协议)这一步表示客户端开始向网络中发送一个包含厂商自定义协议的 UDP 广播包&#xff0c;目的是寻找本厂商的设备&#xff08;网关&#xff09;。客户端此时处于活动状态activa…

视频去水印怎么办?两种方法教会你

视频有水印的话确实很恼火&#xff0c;想要干净的去除视频水印&#xff0c;这里分享两种简单又实用的方法。 方法一&#xff1a;美图秀秀 大家都熟悉的修图神器&#xff0c;功能超全。不仅能把照片P得美美哒&#xff0c;还能去掉照片和视频上的水印呢&#xff01;用起来挺顺手…

【案例】旗帜飘动

开发平台&#xff1a;Unity 6.0 开发工具&#xff1a;Shader Graph 参考视频&#xff1a;Unity Shader Graph 旗帜飘动特效   一、效果图 二、Shader Graph 路线图 三、案例分析 核心思路&#xff1a;顶点偏移计算 与 顶点偏移忽略 3.1 纹理偏移 视觉上让旗帜保持动态飘动&a…

PHP合成图片,生成海报图,poster-editor使用说明

之前写过一篇使用Grafika插件生成海报图的文章&#xff0c;但是当我再次使用时&#xff0c;却发生了错误&#xff0c;回看Grafika文档&#xff0c;发现很久没更新了&#xff0c;不兼容新版的GD&#xff0c;所以改用了intervention/image插件来生成海报图。 但是后来需要对海报…

智慧汇聚:十款企业培训工具打造学习型企业

在当今快速变化的商业环境中&#xff0c;企业要想保持竞争力&#xff0c;就必须不断适应新技术、新市场和新的工作方式。构建一个学习型企业&#xff0c;不仅能够促进员工的个人成长&#xff0c;还能增强团队的整体能力和企业的创新能力。为了实现这一目标&#xff0c;借助先进…

「C/C++」C/C++标准库 之 #include<cstdlib> 通用工具函数库

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「C/C」C/C程序设计&#x1f4da;全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasoli…

pycharm调用方法时显示为灰色

不用担心&#xff0c;亮的证明是被用过得&#xff0c;灰色的没有被用&#xff0c;引用一下就会变正常了

机器学习:我们能用机器学习来建立投资模型吗

机器学习模型能解决什么投资问题&#xff1f; 利用机器学习解决投资问题的思路&#xff0c;其实和在互联网领域解决推荐、广告问题的思路是一样的&#xff0c;只不过利用的特征完全变了。推荐、广告模型利用的是用户的年龄、性别&#xff0c;物品的类别、价格等特征&#xff0c…

ClkLog企业版(CDP)预售开启,更有鸿蒙SDK前来助力

新版本发布 ClkLog在上线近1年后&#xff0c;获得了客户的一致肯定与好评&#xff0c;并收到了不少客户对功能需求的反馈。根据客户的反馈&#xff0c;我们在今年三季度对ClkLog的版本进行了重新的规划与调整&#xff0c;简化了原有的版本类型&#xff0c;方便客户进行选择。 与…

【Java设计模式】16-26章

行为型模式&#xff1a; 第16章 12模板方法模式(Template) 16.1 豆浆制作问题 16.2 模板方法模式基本介绍 16.3 模板方法模式原理类图 16.4 模板方法模式解决豆浆制作问题 package com.atguigu.template;//抽象类&#xff0c;表示豆浆 public abstract class SoyaMilk {//模板…

上市公司环境信息披露质量评分数据王婉菁版(2008-2023年)噪声光污染辐射废水减排等治理

数据来源基础数据来源于上市公司年报、社会责任报告、环境报告以及证监会和统计局。时间跨度2008-2023区域跨度企业及行业层面 核心解释变量&#xff1a;环境信息披露质量&#xff0c;是由上市公司环境管理、负债、业绩于治理、披露载体等各项信息披露质量评分加总。 被解释变…

Llama 3.2 Vision Molmo:多模态开源生态系统基础

编者按&#xff1a; 视觉功能的融入对模型能力和推理方式的影响如何&#xff1f;当我们需要一个既能看懂图像、又能生成文本的 AI 助手时&#xff0c;是否只能依赖于 GPT-4V 这样的闭源解决方案&#xff1f; 我们今天为大家分享的这篇文章&#xff0c;作者的核心观点是&#xf…

el-table 滚动条重置 手动控制滚动条

最近在使用 el-table 的时候&#xff0c;出现一个问题&#xff1a; 表头过长的时候&#xff0c;会有左右滑动的操作&#xff0c;当我们把表格拉到最右侧&#xff0c;这个时候重新请求数据的话&#xff0c;表格位置还是在最右侧&#xff0c;不会恢复原位。 那我们想恢复原位&a…

Windows的MySQL开机自动启动问题

标题 问题描述 问题描述 在Windows系统中&#xff0c;我设置好了MySQL服务为自动启动&#xff0c;但在开机后发现MySQL服务任没有自动运行。我有点苦恼&#xff0c;每次连接MySQL&#xff0c;都要进入计算机管理&#xff0c;手动打开。 解决方法&#xff1a; 1.前提安装好MySQ…

私有化视频平台EasyCVR视频汇聚平台接入RTMP协议推流为何无法播放?

私有化视频平台EasyCVR视频汇聚平台兼容性强、支持灵活拓展&#xff0c;平台可提供视频远程监控、录像、存储与回放、视频转码、视频快照、告警、云台控制、语音对讲、平台级联等视频能力。 有用户反馈&#xff0c;项目现场使用RTMP协议接入EasyCVR平台&#xff0c;但是视频却不…

Python小白学习教程从入门到入坑------第二十三课 封装(语法进阶)

面向对象的三大特征&#xff1a;封装、继承、多态 一、封装 1.1 何为封装 封装&#xff1a;在Python中指的是隐藏对象中一些不希望被外部所访问到的属性或者方法。将复杂的信息、流程给包起来&#xff0c;内部处理&#xff0c;让使用者只需要通过简单的操作步骤&#xff0c;…

Rust 力扣 - 643. 子数组最大平均数 I

文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 我们遍历长度为k的窗口&#xff0c;我们只需要记录窗口内的最大和即可&#xff0c;遍历过程中刷新最大值 结果为窗口长度为k的最大和 除以 k 题解代码 impl Solution {pub fn find_max_average(nums: Vec<…

Vscode使用launch.json进行传参调试代码

目录 1 操作2 后记 1 操作 {// Use IntelliSense to learn about possible attributes.// Hover to view descriptions of existing attributes.// For more information, visit: https://go.microsoft.com/fwlink/?linkid830387"version": "0.2.0","…

Fooocus图像生成软件本地部署教程:在Windows上快速上手AI创作

文章目录 前言1. 本地部署Fooocus图像生成软件1.1 安装方式1.2 功能介绍 2. 公网远程访问Fooocus3. 固定Fooocus公网地址 前言 本篇文章将介绍如何在本地Windows11电脑部署开源AI生图软件Fooocus&#xff0c;并结合Cpolar内网穿透工具轻松实现公网环境远程访问与使用。 Foooc…

#渗透测试#SRC漏洞挖掘#自动化脚本的编写01

免责声明 本教程仅为合法的教学目的而准备&#xff0c;严禁用于任何形式的违法犯罪活动及其他商业行为&#xff0c;在使用本教程前&#xff0c;您应确保该行为符合当地的法律法规&#xff0c;继续阅读即表示您需自行承担所有操作的后果&#xff0c;如有异议&#xff0c;请立即停…