C语言实现快速排序算法

1. 什么是快速排序算法

快速排序的核心思想是通过分治法(Divide and Conquer)来实现排序。

算法的基本步骤是:

1. 选择一个基准值(通常是数组中的某个元素),将数组分成两部分,使得左边的部分所有元素都小于基准值,右边的部分所有元素都大于基准值。

2. 对这两部分分别进行递归排序,直到整个数组有序。

那么,该算法为什么叫做快速排序算法呢?

快速排序算法之所以被称为“快速”,是因为它在大多数情况下都能够快速地完成排序。在平均情况下,其时间复杂度为O(nlogn),其中n为数组的大小。

此外,快速排序还具有原地排序的特点,即不需要额外的辅助空间,只需对原始数组进行原地操作。这些优点使得快速排序成为了排序问题中的一种首选算法。


2. 单趟排序

单趟排序指的就是将数组分为两部分的算法。

对于实现这一步,我们有三种思路。

2.1 霍尔法

霍尔并无什么特殊含义,只是因为最早发现快速排序算法的人叫霍尔,这是他的实现方法。

思路:

1. 先选定一个基准值key(一般选择首元素)。

2. 定义两个指针left和right,分别指向数组的左右两端。

3. left从左往右遍历,寻找大于基准值的元素,right从右往左遍历,寻找小于基准值的元素。

4. 如果left与right未相遇,那么就交换两指针指向的元素。

5. 如果left与right相遇,那么就让key指向的元素与right指向的元素交换。

代码

//霍尔法
int ParSort_1(int* arr, int left, int right)
{
    int key = left;
    while (left < right)
    {
        while (left < right && arr[right] >= arr[key]) { right--; }
        while (left < right && arr[left] <= arr[key]) { left++; }
        if (left < right)
            swap(&arr[left], &arr[right]);
    }

    swap(&arr[key], &arr[left]);
    return left;
}

注意事项(如何保证right和left共同指向的元素与key指向的元素交换是合理的)

1. 如果选取的基准值为首元素,那么在外层循环的一次循环中,一定要让right先进行移动,这样可以确保共同指向的元素是小于或等于基准值的。

2. 如果选取的基准值为最后一个元素,则与上面相反。

2.2 挖坑法

核心思想与霍尔法相同,但是表现形式有所差异。

思路

顾名思义,我们将基准值单独用变量进行存放,而将基准值原本所在的位置空出来成为一个坑(我们将其称作hole)。

1. right先进行遍历,如果发现有小于基准值的元素,则将该元素填入hole中,然后right指向的位置成为新的hole。(假设F小于key)

2. 然后left再进行遍历,如果发现有大于基准值的元素,则将该元素填入hole中,然后left指向的位置成为新的hole。(假设B大于key)

 3. 以此类推,当left与right相遇时,将key填入hole中即可。

代码

//挖坑法
int ParSort_2(int* arr, int left, int right)
{
    int key = arr[left];
    int hole = left;

    while (left < right)
    {
        while (left < right && arr[right] >= key) { right--; }
        arr[hole] = arr[right];
        hole = right;

        while (left < right && arr[left] <= key) { left++; }
        arr[hole] = arr[left];
        hole = left;
    }

    arr[hole] = key;
    return hole;
}

注意事项

对于这个方法来说,洞在谁那边,谁就先开始遍历。

2.3 前后指针法

思路

1. 定义两个指针,prev和cur,prev所指向的以及之前的元素就是小于基准值的元素,cur用于遍历数组。

2. 如果cur找到小于基准值的元素,让prev++,然后交换prev指向的元素和cur指向的元素。

3. 让基准值与prev指向的元素进行交换。

代码

//前后指针
int ParSort_3(int* arr, int left, int right)
{
    int key = left;
    int prev = left;
    int cur = left + 1;
    while (cur <= right)
    {
        //arr[cur]小于基准值就交换
        if (arr[cur] <= arr[key] && ++prev != cur)
        {
            swap(&arr[prev], &arr[cur]);
        }
        cur++;
    }

    swap(&arr[key], &arr[prev]);
    return prev;
}

注意事项

如果选取的基准值为首元素,则在最后让prev指向的元素与基准值交换;如果选区的基准值为最后一个元素,则在最后让prev指向的下一个元素与基准值交换。

3. 快速排序算法的递归实现

按照第一部分的介绍,我们很容易的到下面的代码。

void QuickSort(int* arr, int begin, int end)
{
    if (begin >= end)
        return;

    int key = ParSort_3(arr, begin, end);
    QuickSort(arr, key + 1, end);//排右边
    QuickSort(arr, begin, key - 1);//排左边
}

4. 快速排序算法的优化

当数据量十分巨大时,使用递归实现的快速排序算法会由于调用函数次数过多而导致程序效率下降。

由于递归的逻辑结构像是一个树状图,所以在递归的层次较深时,每次进到下一层都会调用上一层两倍数量的函数。

众所周知,2^{n}是一个极其可怕的东西,那么我们能不能在层次较深,所需排序的数组长度较短时,转而使用其他经典的排序算法呢?

于是我们做出了如下的优化:

void QuickSort(int* arr, int begin, int end)
{
    if (begin >= end)
        return;

    if (end - begin <= 8)
    {
        InsertSort(arr + begin, end - begin + 1);
        return;
    }

    int key = ParSort_3(arr, begin, end);
    QuickSort(arr, key + 1, end);//排右边
    QuickSort(arr, begin, key - 1);//排左边
}

当数组长度小于等于9时,我们采用插入排序来进行排序(不止插入排序,其他排序也可)。

//插入排序
void InsertSort(int* arr, int len)
{
	for (int i = 1; i < len; i++)
	{
		int j = i;
		while (j > 0 && arr[j] < arr[j - 1])
		{
			swap(&arr[j], &arr[j - 1]);
			j--;
		}
	}
}

5. 结语

快速排序的非递归算法是用栈模拟递归实现的,由于太麻烦我就没写,感兴趣可以自己尝试写写。

单趟排序算法用哪个,快速排序递归还是非递归,层次较深时换用什么排序算法,这些都是可以自由组合的。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2024.4.1-[作业记录]-day06-认识 CSS(三大特性、引入方式)

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; day06-认识 CSS(三大特性、引入方式) 文章目录 day06-认识 CSS(三大特性、引入方式)作业…

xss.pwnfunction-Ma Spaghet!

根据代码得知 这个是根据get传参的并且是由someboby来接收参数的 所以 <script>alert(1137)</script> js并没有执行因为 HTML5中指定不执行由innerHTML插入的<script>标签 所以 ?somebody<img%20src1%20onerror"alert(1337)"> 这样就成…

Java栈和队列的实现

目录 一.栈(Stack) 1.1栈的概念 1.2栈的实现及模拟 二.队列(Queue) 2.1队列的概念 2.2队列的实现及模拟 2.3循环队列 2.4双端队列&#xff08;Deque&#xff09; 一.栈(Stack) 1.1栈的概念 栈:一种特殊的线性表&#xff0c;其 只允许在固定的一端进行插入和删除元素操作…

JavaWeb--JavaScript Part 01

1. JavaScript概述 JavaScript&#xff08;简称JS&#xff09;是一种轻量级的、解释执行的客户端脚本语言&#xff0c;主要用于增强网页的交互性和动态性。它起源于Netscape的LiveScript&#xff0c;并在1995年发布时更名为JavaScript。尽管名称中包含"Java"&#xf…

JS 利用 webcam访问摄像头 上传到服务器

webcam JS 较为详细的指南 定义标题 <!doctype html> <html> <head><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>How to capture picture from webcam with Webcam.js</title></…

FreeMarker系列--指令的用法(全面,有示例)

原文网址&#xff1a;FreeMarker系列--指令的用法(全面&#xff0c;有示例)_IT利刃出鞘的博客-CSDN博客 简介 说明 本文介绍FreeMark指令的用法。 相关网址 中文官方参考手册 assign 描述 使用该指令你可以创建一个新的变量&#xff0c; 或者替换一个已经存在的变量。注…

Redis实现高可用持久化与性能管理

前言 在生产环境中&#xff0c;为了实现Redis的高可用性&#xff0c;可以采用持久化、主从复制、哨兵模式和 Cluster集群的方法确保数据的持久性和可靠性。这里首先介绍一下使用持久化实现服务器的高可用。 目录 一、Redis 高可用方法 1. 持久化 2. 主从复制 3. 哨兵 4.…

2024.4.5-[作业记录]-day10-CSS 布局模型(层模型)

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 作业 2024.4.5-学习笔记1 CSS定位1.1 相对定位 relative1.2 绝对定位 absolut…

【C++】map set 底层刨析

文章目录 1. 红黑树的迭代器2. 改造红黑树3. map 的模拟实现4. set 的模拟实现 在 C STL 库中&#xff0c;map 与 set 的底层为红黑树&#xff0c;那么在不写冗余代码的情况下使用红黑树同时实现 map 与 set 便是本文的重点。 1. 红黑树的迭代器 迭代器的好处是可以方便遍历&…

Day84:服务攻防-端口协议桌面应用QQWPS等RCEhydra口令猜解未授权检测

目录 端口协议-口令爆破&未授权 弱口令爆破 FTP&#xff1a;文件传输协议 RDP&#xff1a;Windows远程桌面协议 SSH&#xff1a;Linux安全外壳协议 未授权案例(rsync) 桌面应用-QQ&WPS&Clash QQ RCE 漏洞复现 WPS RCE 漏洞复现 Clas* RCE 漏洞复现 知识点…

90天玩转Python—04—基础知识篇:Python编程基础:标识符、保留字、注释、多行语句、print输出以及模块导入详解

90天玩转Python系列文章目录 90天玩转Python—01—基础知识篇:C站最全Python标准库总结 90天玩转Python--02--基础知识篇:初识Python与PyCharm 90天玩转Python—03—基础知识篇:Python和PyCharm(语言特点、学习方法、工具安装) 90天玩转Python—04—基础知识篇:Pytho…

淘宝里的优惠券在哪里查看_淘宝优惠券怎么找到领取

淘宝里的优惠券在哪里查看&#xff1f; 1、打开手机淘宝APP&#xff0c;点击右下角我的淘宝&#xff1b; 2、在我的淘宝里找到我的权益&#xff0c;看到优惠券后点击进入&#xff1b; 3、我淘宝我的权益券里可以看到已领取到的淘宝天猫优惠券&#xff1b; 淘宝优惠券怎么找到领…

开源代码分享(17)-基于足球队训练算法(Football Team Training Algorithm,FTTA)的组合风速预测

参考文献&#xff1a; [1]Tian Z, Gai M. Football team training algorithm: A novel sport-inspired meta-heuristic optimization algorithm for global optimization[J]. Expert Systems with Applications, 2024, 245: 123088. 1.算法基本原理 足球队训练算法&#xff0…

(学习日记)2024.04.01:UCOSIII第二十九节:消息队列实验(待续)

写在前面&#xff1a; 由于时间的不足与学习的碎片化&#xff0c;写博客变得有些奢侈。 但是对于记录学习&#xff08;忘了以后能快速复习&#xff09;的渴望一天天变得强烈。 既然如此 不如以天为单位&#xff0c;以时间为顺序&#xff0c;仅仅将博客当做一个知识学习的目录&a…

独角数卡对接码支付收款教程

1、到码支付后台找到支付配置。2、将上面的复制依次填入&#xff0c;具体看下图&#xff0c;随后点立即添加 商户ID商户PID 商户KEY异步不能为空 商户密钥商户密钥

jenkins_Pipeline使用测试

jenkins—Pipeline使用测试 安装jenkins # jar包启动 https://sg.mirror.servanamanaged.com/jenkins/war-stable/2.346.1/jenkins.war https://download.oracle.com/java/17/latest/jdk-17_linux-x64_bin.tar.gz [rootvm ~]# tail /etc/profile ... export JAVA_HOME/opt…

51单片机入门:LED点阵屏

LED点阵屏介绍 LED点阵屏由若干个独立的LED组成&#xff0c;LED以矩阵的形式排列&#xff0c;以灯珠亮灭来显示文字、图片、视频等。LED点阵屏广泛应用于各种场合&#xff0c;如&#xff1a;广告屏、公告牌等。 分类&#xff1a; 按颜色&#xff1a;单色、双色、全彩&#x…

GPT4解除限制使用次数了!GPT5预计要推出了!

今天登录GPT Plus的时候&#xff0c;出现了如下提示&#xff1a; With DALLE,browing and analysis Usage limits may apply GPT4已经没有了数量和时间限制的提示。 更改前&#xff1a;每 3 小时限制 40 次&#xff08;团队计划为 100 次&#xff09;&#xff1b;更改后&#…

尚硅谷html5+css3(1)

1.基本标签&#xff1a; <h1>最大的标题字号 <h2>二号标题字号 <p>换行 2.根标签<html> 包括<head>和<body> <html><head><title>title</title><body>body</body></head> </html> 3…

C语言-预定义符号

编译和链接&#xff08;基础速通版&#xff09;-CSDN博客https://blog.csdn.net/Jason_from_China/article/details/137182220 预定义符号 包含 C语⾔设置了⼀些预定义符号&#xff0c;可以直接使⽤&#xff0c;预定义符号也是在预处理期间处理的。 __FILE__ //进⾏编译的…