当前位置： 首页 > java >正文

【数据结构与算法】数据结构初阶：详解排序（二）——交换排序中的快速排序

java 2025/7/28 6:19:01

 

🔥个人主页：艾莉丝努力练剑

❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题

🍉学习方向：C/C++方向

⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

重要提醒：为什么我们要学那么多的数据结构？这是因为没有一种数据结构能够去应对所有场景。我们在不同的场景需要选择不同的数据结构，所以数据结构没有谁好谁坏之分，而评估数据结构的好坏要针对场景，如果在一种场景下我们需要频繁地对头部进行插入删除操作，那么这个时候我们用链表；但是如果对尾部进行插入删除操作比较频繁，那我们用顺序表比较好。

        因此，不同的场景我们选择不同的数据结构。

前言：本篇文章，我们继续来介绍排序相关的知识点，在初阶的数据结构与算法阶段，我们把知识点分成三部分，复杂度作为第一部分，顺序表和链表、栈和队列、二叉树为第二部分，排序为第二部分，我们之前已经介绍完了第一部分：算法复杂度和第二部分：顺序表和链表、栈和队列、二叉树。本文我们继续开始学习第三部分中的排序的内容啦。 

这个用来测试代码的对比排序性能的代码博主还是放在下面，大家可以对比一下各种排序算法的运行时间，从而对不同排序方法的时间复杂度有更加直观地认识：

代码演示： 

//测试排序的性能对比  
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}//begin和end的时间差就是int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}

大家可以用一用，如果是直接选择排序、冒泡排序这种大家耐心一点，可能要多等一会儿，毕竟时间复杂度O(n^2)这一块，哈哈。

目录

正文

一. 比较排序

三、交换排序

（二）快速排序

1、递归版本

（1）Hoare版本

1) 找基准值

2) 代码实现

3) 时间复杂度分析 

​编辑

（2）挖坑法

1) 找基准值

 2) 代码实现

（3）Lomuto双指针版本

1) 找基准值

2) 代码实现

（4）快速排序的时间复杂度分析

2、非递归版本——栈

1) 找基准值

2) 代码实现

3、快速排序的特性

结尾

正文

一. 比较排序

三、交换排序

交换排序的概念在上一篇文章，博主直接截图，大家看一看：

（二）快速排序

重头戏来了，前面的几种排序算法大家可能没什么感觉，但从这个开始，那真是一个赛一个带派。

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。 

这个就是我们会介绍的快排找基准值的第一种方法——Hoare版本的思路。

首先，我们实现一下快速排序的主体框架的代码—— 

代码实现： 

//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基准值keyiint keyi = _QuickSort(arr, left, right);//左序列[left,keyi-1]  右序列[keyi+1,right]QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);
}

我们根据是否递归，分为递归版本和非递归版本，递归版本又因为找基准值方法的不同，我们分成了Hoare版本、挖坑法以及Lomuto双指针法。

1、递归版本
（1）Hoare版本

Hoare版本算法思路：

1）创建左右指针，确定基准值；

2）从右向左找出比基准值小的数据，从左向右找出比基准值大的数据，左右指针数据交换，进入下一次循环。

1) 找基准值

如果基准值找的不好，时间复杂度就会出问题，变成O(N^2)：

我们观察一下找基准值时候会遇到的一些问题—— 

为什么跳出循环后right位置的值⼀定不大于key？ 

原因： 

为什么left和right指定的数据和key值相等时也要交换？ 

原因：  

相等的值参与交换确实有一些额外消耗。实际还有各种复杂的场景，假设数组中的数据大量重复时，无法进行有效的分割排序。  

在这里，我们能不能让left先走，right后走呢？ 不可以——

我们用一些用例测试的时候很多情况下能过，但我们不能这么做。 

2) 代码实现
//找基准值  hoare版本
int _QuickSort1(int* arr, int left,int right)
{int keyi = left;left++;while (left <= right){//right：从右往左找比基准值小的while (left <= right && arr[right] > arr[keyi]){--right;}//left：从右往左找比基准值大的while (left <= right && arr[left] < arr[keyi]){++left;}//left和right交换if (left <= right)Swap(&arr[left++], &arr[right--]);}//right的位置就是基准值的位置Swap(&arr[keyi], &arr[right]);return right;
}

时间复杂度：O(n*logn)。

3) 时间复杂度分析 

我们回忆一下，递归的时间复杂度是怎么求的：

如果基准值找的不好怎么办？ 

有友友可能会问：内层循环的while循环这里可不可以等于？不可以。

理由如下：

right位置一定会是基准值的位置吗？为什么？

（2）挖坑法

我们的思路：创建左右指针。⾸先从右向左找出比基准小的数据，找到后立即放入左边坑中，当前位置变为新的"坑"，然后从左向右找出比基准大的数据，找到后立即放入右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放入当前的"坑"中，返回当前"坑"下标（即分界值下标）。

1) 找基准值

我们的思路是：

我们在上图的基础上进一步分析——

 2) 代码实现
//找基准值  挖坑法
int _QuickSort2(int* arr, int left,int right)
{int hole = left;int key = arr[hole];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;
}

时间复杂度：O(n*logn)。 

（3）Lomuto双指针版本

这是博主觉得最带派的找基准值的方法。

思路：创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。

1) 找基准值

根据上图，我们进一步分析，详见下图——

2) 代码实现
//找基准值 lomuto双指针方法
int _QuickSort(int* arr, int left,int right)
{int prev = left, cur = prev + 1;int keyi = left;while (cur <= right){//cur数据和基准值比较if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], & arr[prev]);}++cur;}Swap(&arr[keyi], &arr[prev]);return prev;
}

时间复杂度：O(n*logn)。 

（4）快速排序的时间复杂度分析

快速排序特性总结：

1、时间复杂度：O(nlogn)；

2、空间复杂度：O(logn)。

2、非递归版本——栈

要用非递归版本的快速排序，我们需要借助之前学过的数据结构——栈。

要用栈，我们之前已经介绍堆排序的时候就已经介绍过了类似的处理方法，这里不再赘述，

1) 找基准值

2) 代码实现

要用栈，栈这种数据结构我们在之前就已经实现过了，这里可以直接调用——

Stack.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;//定义栈中有效的数据个数int capacity;//栈的空间大小
}ST;//初始化
void STInit(ST* ps);//销毁
void STDestory(ST* ps);//入栈——栈顶
void STPush(ST* ps, STDataType x);//出栈——栈顶
void STPop(ST* ps);//取栈顶元素
STDataType STTop(ST* ps);//栈是否为空
bool STEmpty(ST* ps);//获取栈中有效元素个数
int STSize(ST* ps);

Stack.c：

#define  _CRT_SECURE_NO_WARNINGS  1#include"Stack.h"//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//销毁
void STDestory(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}//入栈——栈顶
void STPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈——栈顶
void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--;
}//取栈顶元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

sort.c：

//非递归版本快速排序——栈：栈+lomuto双指针
void QuickSortNorR(int* arr, int left,int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){//取栈顶两次int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);//[begin,end]————找基准值int keyi = begin;int prev = begin, cur = prev + 1;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[prev], &arr[cur]);}++cur;}Swap(&arr[prev], &arr[keyi]);keyi = prev;//begin  keyi  end//左序列[begin,keyi-1]//右序列[keyi+1,end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestory(&st);
}

时间复杂度：O(n*logn)。 

3、快速排序的特性

1、快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序；

2、时间复杂度：O(N*logN)——

3、空间复杂度：O(logN)；

4、稳定性：不稳定。

结尾

快速排序还有一些内容难度是加深的，如三路划分、自省排序，博主都整理到另一篇文章作为加餐了。后面归并排序出了递归、非递归版本，也会有加餐内容，敬请期待！

往期回顾：

【数据结构与算法】数据结构初阶：详解排序（一）——插入排序、选择排序以及交换排序中的冒泡排序

本期内容需要回顾的C语言知识如下面的截图中所示（指针博主写了6篇，列出来有水字数嫌疑了，就只放指针第六篇的网址，博主在指针（六）把指针部分的前五篇的网址都放在【往期回顾】了，点击【传送门】就可以看了）。

大家如果对前面部分的知识点印象不深，可以去上一篇文章的结尾部分看看，博主把需要回顾的知识点相关的博客的链接都放在上一篇文章了，上一篇文章的链接博主放在下面了：

【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）

结语：本篇文章到这里就结束了，对数据结构的排序知识感兴趣的友友们可以在评论区留言，博主创作时可能存在笔误，或者知识点不严谨的地方，大家多担待，如果大家在阅读的时候发现了行文有什么错误欢迎在评论区斧正，再次感谢友友们的关注和支持！ 

http://www.xdnf.cn/news/16444.html

相关文章：

  • 算法竞赛阶段二-数据结构（36）数据结构双向链表模拟实现
  • bash的特性-bash中的引号
  • 力扣131:分割回文串
  • 智能化设备健康管理：中讯烛龙预测性维护系统引领行业变革
  • 零基础，如何入手学习SAP？
  • ASP.NET Core 高并发万字攻防战：架构设计、性能优化与生产实践
  • OpenLayers 综合案例-地图绘制
  • 使用低级上位画图法理解在对磁盘空间进行容量分配时【低级单位上位至高级单位的换算】
  • 【论文阅读】ON THE ROLE OF ATTENTION HEADS IN LARGE LANGUAGE MODEL SAFETY
  • Flutter开发实战之CI/CD与发布流程
  • Unity SMAA
  • 结合Golang语言说明对多线程编程以及 select/epoll等网络模型的使用
  • 携带参数的表单文件上传 axios, SpringBoot
  • 从零开始：Coze Studio开源版部署全记录(win11)
  • 设计模式（六）创建型：单例模式详解
  • C#中Visual Studio平台按照OfficeOpenXml步骤
  • HAProxy 实验指南：从零开始搭建高可用负载均衡系统
  • Reeden：跨平台 AI 电子书阅读器
  • C 与 C++ 的区别：发展、特性及优缺点详解
  • 使用Netty搭建一个网络聊天室
  • VS Code + LaTeX 绘制电气图完全指南（含 PlantUML 样式参考）
  • 2025年全国青少年信息素养大赛Scratch算法创意实践挑战赛 小低组 初赛 真题
  • Javaweb————HTTP消息体拆分讲解
  • 【嵌入式电机控制#20】无刷直流电机硬件案例
  • 【数据结构】栈和队列的实现
  • 单片机ADC机理层面详细分析（一）
  • Anaconda常用命令及环境管理指南
  • Redis的下载和安装(Linux)
  • 无源域自适应综合研究【3】
  • Java模块化编程深度指南：从过程式到面向对象的进化之路