【数据结构】——快排详解
上一篇文章我们介绍了八大排序中的七种,今天这篇文章主要来详细介绍一种比较重要也是常用的一种排序算法——快速排序~
一、什么是快排?
快速排序是一种二叉树结构的交换排序方法。相当于是冒泡排序的一种升级,都是属于交换排序类,通过不断比较和移动交换来实现排序。
其基本思想是:任意取待排序元素序列中的某个元素作为基准值,按照这个排序码把待排序集合分割成两个子序列,左子序列中所有元素都小于该基准值,右子序列中所有元素都大于该基准值。然后左右两边子序列又重复该过程,直到所有元素都排列在相应的位置上为止。
二、快排的实现
1、对顺序表L作快速排序
void QuickSort(sqList *L)
{
QSort(L,1,L->length);
}
2、由于需要递归调用,因此我们外封装了一个函数,下面是Sort的实现
void QSort(sqList *L,int low,int high)
{
int pivot;
if(low<high)
{
//将待排序序列一分为二
pivot = Partition(L,low,high);
//对低子表递归排序
QSort(L,low,pivot-1);
//对高子表递归排序
QSort(L,pivot+1,high);
}
}
3、这段代码的核心部分是pivot = Partition(L,low,high);其要做的就是先选取当中的一个关键字,然后想尽办法把它放到第一个位置,使得他左边的值都比他小,右边的值都比他大。
比如说:数组值为[50,10,90,30,70,40,80,60,20]经过Partition(L,1,9)执行后,数组变成{20,10,40,30,50,70,80,60,90},并返回值5给pivot,然后递归调用QSort(L,1,5-1)QSort(L,5+1,9)语句,其实就是在对{20,10,40,30}{70,80,60,90}分别进行同样的Partition操作,知道顺序全部正确为止。
函数实现:
int Partition(SqList *L,int low,int high)
{
int pivotkey;
pivotkey = L->r[low];//用子表的第一个记录作为枢轴记录
while(low < high)
{
while(low < high && L->r[high] >= pivotkey)
high--;
swap(L,low,high);//将比枢轴记录小的记录交换到低端
while(low < high && L->r[high] <= pivotkey)
low++;
swap(L,low,high);//将比枢轴记录大的记录交换到高端
}
return low;//返回枢轴所在位置
}
代码讲解:
三、快排的时间复杂度分析
快排的时间性能取决于快排递归的深度。可以用递归树来描述递归算法的执行情况。如果排序n个关键字,其递归树的深度就是【log2n】+1,在最优的情况下,快速排序的**时间复杂度是O(nlogn)**空间复杂度是O(logn)
四、快排的优化
1、优化选取枢轴
如果我们选取的pivotkey是处在整个序列的中间位置,那么我们可以将整个序列分成小数集合和大数集合。但是,假如我们选取的pivotkey不是中间数又如何呢?——可能导致整个系列没有一个实质性的变化。所以pivotkey = L->r[low];变成了一个潜在的性能瓶颈。
于是,我们采取了三数取中的方法,即三个关键字进行排序,将中间数作为枢轴,一般取左端、右端和中间三个数。
代码实现:
nt pivotkey;
int m = low +(high-low)/2;//计算数组中间的元素的下标
if(L->r[low] > L->r[high])
swap(L,low,high);
if(L->r[m] > L->r[high])
swap(L,high,m);
if(L->r[m] > L->r[low])
swap(L,m,low);
2、优化不必要的交换
我们发现,50这个关键字,其位置变化是1->9->3->6->5,可其实他的最终目标是5,当中的交换其实是不需要的。
所以我们对此进行优化:
int Partition(SqList *L,int low,int high)
{
int pivotkey;
//这里省略三数取中代码
pivotkey = L->r[low];
L->r[0] = pivotkey;//将枢轴关键字备份到L->r[0]
while(low < high)
{
while(low < high && L->r[high] >= pivotkey)
high--;
L->r[low] = L->r[high];//采用替换而不是交换的方式进行操作
while(low < high && L->r[low] <= pivotkey)
low++;
L->r[high] = L->r[low];
}
L->r[low] = L->r[0];
return low;//返回枢轴所在位置
}
3、优化小数组时的排序方案
如果数组非常小的情况下,快速排序反而不如直接插入排序来得更好(直接插入排序是简单排序中性能最好的)。
因此改进QSort函数:
#define MAX_LENGTH_INSERT_SORT 7
void QSort(sqList *L,int low,int high)
{
int pivot;
//当high-low大于常数时用快排
if((high - low) > MAX_LENGTH_INSERT_SORT)
{
pivot = Partition(L,low,high);
QSort(L,low,pivot-1);
QSort(L,pivot+1,high);
}
else
InsertSort(L);
4、优化递归操作
递归对性能有一定影响,栈的大小是有限的,每一次递归调用都会耗费一定的栈空间,函数的参数越多,每次递归耗费的口空间也越多。
对QSort实施尾递归优化:
#define MAX_LENGTH_INSERT_SORT 7
void QSort(sqList *L,int low,int high)
{
int pivot;
//当high-low大于常数时用快排
if((high - low) > MAX_LENGTH_INSERT_SORT)
{
while(low<high)
{
pivot = Partition(L,low,high);
QSort(L,low,pivot-1);
low = pivot + 1;
}
}
else
InsertSort(L);
}
将if改成while后,因为第一次递归以后,变量low就没有用处了,所以可以将pivot + 1的值赋值给low,再循环后Partition(L,low,high)的效果等同于Partition(L,pivot + 1,high)。
因此采用迭代而不是递归的方法可以缩减堆栈深度,从而提高了整体性能。
智能推荐
Matplotlib:绘图结构详解,Artist、Figure、Axes和Axis的联系与区别
目录 0. 引言 1. API层次 2. 绘图结构:Figure,Axes,Axis,Artist - Figure: - Axes: - Axis: - Artist: - Figure中的artist元素 3. Coding Style 4. 参考文献 0. 引言 matplotlib是用Python语言实现的一个类似MATLAB的绘图工具,本文主要介绍matplotl...
IDEA+Log4j2 设置控制台打印彩色日志
在Log4j 2.10以前的版本,pattern中配置%highlight属性是可以正常打印彩色日志的 例如: 但是更新到2.10版本以后,控制台中就无法显示彩色日志了,各种级别的日志混杂在一起,难以阅读 通过查阅官方文档,发现在2.10版本以后,Log4j2默认关闭了Jansi(一个支持输出ANSI颜色的类库) 可见,配置 log4j.skipJansi 这个全局属性即可。 IDEA中,点击右上...
mysql的事务处理
&nbs...
TensorFlow全新的数据读取方式:Dataset API——tf.data.Dataset
转载博客地址: https://baijia.baidu.com/s?id=1583657817436843385&wfr=pc&fr=new_lst 一、Tensorflow读入数据的三种方式 1)Feeding:Python代码在运行每一步时提供数据 2)从文件中读取:输入管道从TensorFlow图形的开头读取文件中的数据。 3)预加载数据:TensorFlow图中的常量或变...
Spring boot + Spring Security 多种登录认证方式配置(一)
一、前言 最近项目上用到Spring Security作为权限认证,项目是Spring boot项目,刚开始只用到本地数据库账号密码登录一种认证方式,后来需求修改,客户有个第三方接口提供登录,为了方便用户,修改为同时支持两种登录方式,在网上多番查找资料,加上看了源码后终于弄出来了,也对Spring Security认证有了更深入的了解,鉴于网上对于多种登录认证方式的资料都不是太完整齐全,所以有了这...
猜你喜欢
【LeetCode】LCS最长公共子序列
最长公共子序列 题目描述 思路分析 递归结构 算法实现 输出最长子序列 算法实现 题目描述 思路分析 设A=“a0,a1,…,am”,B=“b0,b1,…,bn”,且Z=“z0,z1,…,zk”为它们的最长公共子序列。不难证明有以下性质: 如果am=bn,则zk=am=bn,且&ldq...
【Matlab 021期】【路径规划】基于人工蜂群的无人机三维路径规划
蜜蜂采蜜 自然界中的蜜蜂总能在任何环境下以极高的效率找到优质蜜源,且能适应环境的改变。蜜蜂群的采蜜系统由蜜源、雇佣蜂、非雇佣蜂三部分组成,其中一个蜜源的优劣有很多要素,如蜜源花蜜量的大小、离蜂巢距离的远近、提取的难易程度等;雇佣蜂和特定的蜜源联系并将蜜源信息以一定概率形式告诉同伴;非雇佣蜂的职责是寻找待开采的蜜源,分为跟随蜂和侦查蜂两类,跟随峰是在蜂巢等待而侦查蜂是探测蜂巢周围的新蜜源。蜜蜂采蜜时...
java中String的两种创建方式
在Java中有两种创建String类型的变量 第一种方式创建String变量时,首先查找JVM方法区的字符串常量池是否存在存放"abc"的地址,如果存在,则将该变量指向这个地址,不存在,则在方法区创建一个存放字面值"abc"的地址。 第二种方式创建String变量时,在堆中创建一个存放"abc"的对象,使变量str02指向堆中的对象。 根...
Glide安卓9.0加载不出图片解决方案
Glide是一个用于加载图片的框架,但这次却出了问题。。。加载不出图片了??? 首先并没有什么骚操作,正常加载,一开始以为是依赖出了问题啥,一顿好找,摸不着头脑,但改了之后还是无法加载出来,这时我很大程度上就觉得是Android系统的问题了。最终还是和我想的一样。 解决方案 在AndroidManifest.xml加入android:usesCleartextTraffic="true&...
GitHub上有个沙雕开发者,做了款斗图工具后火了...
点击上方“Python爬虫与数据挖掘”,进行关注 回复“书籍”即可获赠Python从入门到进阶共10本电子书 今 日 鸡 汤 未收天子河湟地,不拟回头望故乡。 作者 | Rocky0429 来源 | Python空间 大家好,我是 Rocky0429,一个最近老在聊天斗图的蒟蒻... 作为一个瞎扯淡重度患者,表情包是我保持长久...