当前位置:网站首页>排序--快排(图解)
排序--快排(图解)
2022-08-09 11:08:00 【追梦杰尼龟】
快速排序
一:快排的简单介绍
快速排序之所以快,是相对于冒泡排序,不再是只有相邻的数之间交换,它是可以
跳跃式
的交换,交换的距离会变得大的多,所以速度就提高了,当然也会存在最坏的结果,仍然是跟冒泡一样是相邻的两数之间进行了交换,所以它最差的时间复杂度和冒泡排序是一样的,都是O(N²),它的平均复杂度是O(NlogN)
。
二:快排的实现逻辑(图解)
画图举例来解释把:
随意列出10个无序的数字,需要用到i,j两个变量,i在这列数的最左边,j在这列数的最右边,在这列数中随意找到一个数设置基准值(这里为了方便将第一个数设置为基准),首先让j向左移动,让i向右移动。
j找到一个比基准值小的数2停下来,然后i向右移动找到比基准值大的数6停下来,然后将i,j所指向的数进行交换。
交换后,j继续向左移动找到比基准值小的数4停下来,然后i向右移动找到比基准值大的数7停下来,然后将i,j所指向的数进行交换。
接下来j继续向左移动找到比基准值小的数3,i向右移动和j碰面,此时i和j在同一个位置上停下来,此时将i和j所指向的数和基准值进行交换,即将3和5进行交换。
即基准值归位后,基准值左边的都是小于基准值5的数,在基准值右边的都是大于基准值5的数。
这里需要提一点的是,为什么每次都需要j先移动,因为当最后i和j相碰时,此时所指向的是j寻找到比基准值小的数字,然后和基准值交换能确保基准值左边的都是小于基准值的数字,但是如果i先右边移动的话,最后i和j相碰时,i和j所指向的是i寻找得比基准值大的数,此时和基准值相交换,基准值左边是有一个比基准值大的数,没有达到我们需要的排序效果。
之后我们将5左边的拉出来再进行排序,此时选的基准值是3,根据原先的流程再来一遍。
这就是快速排序的逻辑。
最后总结下快排的步骤
和注意点
:
1.选取基准点
2.永远是j先向左移动
,i再向右移动
3.当i,j碰面时候,将i和j所指向的数和基准值交换
4.然后处理左半边和右半边(递归)
三:代码实现快排(递归)
代码实现:
#include<stdio.h>
int n,i,j,a[100]; //定义全局变量
void quicksort(int left, int right)
{
int temp,t; //temp变量是基准,t变量是用来交换的第三变量
if(left > right) //跳出循环的第一个条件
{
return;
}
temp = a[left]; //此时选用的是第一个数当做基准
i = left; //i是1
j = right; //j是n
while(i != j) //当i,j没有走到一块的时候
{
while(a[j] >= temp && i<j) //j一步一步左移,查找比基准值小的数
{
j--;
}
while(a[i] <= temp && i<j) //i一步一步右移,查找比基准值大的数
{
i++;
}
if(i < j)
{
t = a[i]; //将j查到的比基准值的数与i查到的比基准值小的数交换
a[i] = a[j]; //即将小的数放在基准值左边
a[j] = t; //将大的数放在基准值右边
}
}
//将基准值归位
a[left] = a[i]; //当循环结束时,i=j,在中间某一位置
a[i] = temp; //将那一位置的数与基准值交换
//递归 ,将基准值左边分为一部分
//将基准值右边分为一部分
quicksort(left,i-1); //继续处理左半部分的数
quicksort(i+1,right); //继续处理右半部分的数
return ;
}
int main() //主函数
{
scanf("%d",&n); //用来限制输入的个数
for(i=1; i<=n; i++)
{
scanf("%d",&a[i]); //读入数据
}
quicksort(1,n); //调用快排函数
for(i=1; i<=n; i++)
{
printf("%d\t",a[i]); //循环输出
}
}
边栏推荐
- Qt读写.ini配置文件
- 全网最简单解决OneNote中英字体不统一
- 论文分享 | ACL2022 | 基于迁移学习的论元关系提取
- 备战金三银四:如何成功拿到阿里offer(经历+面试题+如何准备)
- 程序员的专属浪漫——用3D Engine 5分钟实现烟花绽放效果
- MATLAB中如何把cftool拟合的函数输出到命令行(解决如何导出拟合后的曲线数据)
- 依赖注入(Dependency Injection)框架是如何实现的
- Tensorflow realize parameter adjustment of linear equations
- 性能测试(06)-逻辑控制器
- Cluster understanding
猜你喜欢
随机推荐
verbose np.matmul/np.dot/np.multiply/tf.matmul/tf.multiply/*
golang runtime Caller、Callers、CallersFrames、FuncForPC、Stack作用
PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization Paper Reading
Since I use the HiFlow scene connector, I don't have to worry about becoming a "dropper" anymore
MATLAB代码实现三次样条插值
性能测试(04)-表达式和业务关联-JDBC关联
1006 Sign In and Sign Out (25分)
Quartz的理解
PTA习题 三角形判断
b站up主:空狐公子 --矩阵求导(分母布局)课程笔记
程序员的专属浪漫——用3D Engine 5分钟实现烟花绽放效果
golang源代码阅读,sync系列-Pool
Preparation for gold three silver four: how to successfully get an Ali offer (experience + interview questions + how to prepare)
双向链表的各种操作
Jmeter BeanShell post processor
综述文章的写法
无刷无霍尔BLCD电机控制
prometheus接入mysqld_exporter
x86异常处理与中断机制(1)概述中断的来源和处理方式
关于anaconda中conda下载包或者pip下载包很慢的原因,加速下载包的方法(无视anaconda版本和环境)