上个厕所的功夫,就学会了“快速排序”算法
yuyutoo 2024-10-12 01:09 5 浏览 0 评论
快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像BAT、字节、美团等知名IT公司都喜欢考查快速排序原理和手写源码。
一、概念
快速排序,顾名思义就是一种以效率快为特色的排序算法,快速排序(Quicksort)是对冒泡排序的一种改进。由英国计算机专家:托尼·霍尔(Tony Hoare)在1960年提出。
二、基本思想
从排序数组中找出一个数,可以随机取,也可以取固定位置,一般是取第一个或最后一个,称为基准数。然后将比基准小的排在左边,比基准大的放到右边;
如何放置呢,就是和基准数进行交换,交换完左边都是比基准小的,右边都是比较基准大的,这样就将一个数组分成了两个子数组,然后再按照同样的方法把子数组再分成更小的子数组,直到不能分解(子数组只有一个值)为止。以此达到整个数据变成有序序列。
快速排序采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod),现在各种语言中自带的排序库很多使用的都是快速排序。
空间复杂度
快速排序是一种原地排序,只需要一个很小的栈作为辅助空间,空间复杂度为O(log2n),所以适合在数据集比较大的时候使用。
时间复杂度
时间复杂度比较复杂,最好的情况是O(n),最差的情况是O(n2),所以平时说的O(nlogn),为其平均时间复杂度。
- O(n):理想的情况,每次划分所选择的中间数恰好将当前序列几乎等分,经过log2n趟划分,便可得到长度为1的子表。这样,整个算法的时间复杂度为O(nlog2n)。
- O(n2):最坏的情况,每次所选的中间数是当前序列中的最大或最小元素,这使得每次划分所得的子表中一个为空表,另一子表的长度为原表的长度-1。这样,长度为n的数据表的快速排序需要经过n趟划分,使得整个排序算法的时间复杂度为O(n2)。
三、算法步骤
1.选定一个基准数(一般取第一位数字)作为中心点(Pivot);2.将大于Pivot的数字放到Pivot的左边;3.将小于Pivot的数字放到Pivot的右边;4.第一次排序结束后,分别对左右子序列继续递归重复前三步操作。
四、具体示例
实例数组:arr[] = {19,97,9,17,1,8};
1.取出基准数Pivot,以该值为中心轴。
快速排序中的规则:右边有坑,就从左边Arr[L + n]取值来填,反之左边有坑,则从右边Arr[R - n]取值来填;
2.从左边取的基准值,左边的Arr[L]就空出来了,则先从右侧取值来填,从最右侧下标开始,在Arr[R] 取到第一个值“8”;
3.将取到的Arr[R]与基准值比较,发现小于基准值,则插入到Arr[R],占到了基准值Pivot的位置上。
4.然后从Arr[L+1]的位置取出值,继续向右匹配并排序,将匹配到的值(匹配规则如下)插入到右侧Arr[R]的空位置上;
匹配规则:大于基准值的插入到Arr[R],如果小于,则直接忽略并跳过,继续向右取值,直到坐标L和坐标R重合。
5.发现取出的值大于Pivot(基准值),则将其插入到Arr[R]。
6.左边有坑,从右边Arr[R-1]继续匹配,Arr[R-1] = 1,小于基准值,则插入到Arr[L]的坑中;
7.右边有坑了,继续从左边取值继续匹配,则取到Arr[L+1] = 9,小于基准值,则忽略并跳过,继续找Arr[L + 1]继续匹配。
8.继续从左边坐标 + 1 取值继续匹配,则取到Arr[L] = 17,又小于基准值,则忽略并跳过,继续找Arr[L + 1]继续匹配。
9.最后L坐标和R坐标重合了,将Pivot基准值填入
10.至此,快速排序第一轮完整流程结束,分出了左右子序列,左边都是小于Pivot基准值的,右边都是大于Pivot基准值的。
11.继续对左、右子序列递归进行处理,一直缩小到左、右都是一个值,则快速排序结束,最终得出顺序数组{1,8,9,17,19,97};中间递归流程这里不再赘述。
五、快排代码
@java代码
package com.softsec.demo;
/**
* Created with IDEA
*
* @Author Chensj
* @Date 2020/5/17 19:04
* @Description
* @Version 1.0
*/
public class quickSortDemo {
public static void main(String[] args) {
// 创建测试数组
int[] arr = new int[]{19,97,9,17,1,8};
System.out.println("排序前:");
showArray(arr); // 打印数组
// 调用快排接口
quickSort(arr);
System.out.println("\n" + "排序后:");
showArray(arr);// 打印数组
}
/**
* 快速排序
* @param array
*/
public static void quickSort(int[] array) {
int len;
if(array == null
|| (len = array.length) == 0
|| len == 1) {
return ;
}
sort(array, 0, len - 1);
}
/**
* 快排核心算法,递归实现
* @param array
* @param left
* @param right
*/
public static void sort(int[] array, int left, int right) {
if(left > right) {
return;
}
// base中存放基准数
int base = array[left];
int i = left, j = right;
while(i != j) {
// 顺序很重要,先从右边开始往左找,直到找到比base值小的数
while(array[j] >= base && i < j) {
j--;
}
// 再从左往右边找,直到找到比base值大的数
while(array[i] <= base && i < j) {
i++;
}
// 上面的循环结束表示找到了位置或者(i>=j)了,交换两个数在数组中的位置
if(i < j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
// 将基准数放到中间的位置(基准数归位)
array[left] = array[i];
array[i] = base;
// 递归,继续向基准的左右两边执行和上面同样的操作
// i的索引处为上面已确定好的基准值的位置,无需再处理
sort(array, left, i - 1);
sort(array, i + 1, right);
}
/**
* 数组打印
* @param num
*/
private static void showArray(int[] num) {
for (int i = 0; i < num.length; i++) {
System.out.print(num[i] + " ");
}
}
}
返回结果:
排序前:
19 97 9 17 1 8
排序后:
1 8 9 17 19 97
Process finished with exit code 0
@python代码
#快速排序 传入列表、开始位置和结束位置
def quick_sort( li , start , end ):
# 如果start和end碰头了,说明要我排的这个子数列就剩下一个数了,就不用排序了
if not start < end :
return
mid = li[start] #拿出第一个数当作基准数mid
low = start #low来标记左侧从基准数始找比mid大的数的位置
high = end #high来标记右侧end向左找比mid小的数的位置
# 我们要进行循环,只要low和high没有碰头就一直进行,当low和high相等说明碰头了
while low < high :
#从high开始向左,找到第一个比mid小或者等于mid的数,标记位置,(如果high的数比mid大,我们就左移high)
# 并且我们要确定找到之前,如果low和high碰头了,也不找了
while low < high and li[high] > mid :
high -= 1
#跳出while后,high所在的下标就是找到的右侧比mid小的数
#把找到的数放到左侧的空位 low 标记了这个空位
li[low] = li[high]
# 从low开始向右,找到第一个比mid大的数,标记位置,(如果low的数小于等于mid,我们就右移low)
# 并且我们要确定找到之前,如果low和high碰头了,也不找了
while low < high and li[low] <= mid :
low += 1
#跳出while循环后low所在的下标就是左侧比mid大的数所在位置
# 我们把找到的数放在右侧空位上,high标记了这个空位
li[high] = li[low]
#以上我们完成了一次 从右侧找到一个小数移到左侧,从左侧找到一个大数移动到右侧
#当这个while跳出来之后相当于low和high碰头了,我们把mid所在位置放在这个空位
li[low] = mid
#这个时候mid左侧看的数都比mid小,mid右侧的数都比mid大
#然后我们对mid左侧所有数进行上述的排序
quick_sort( li , start, low-1 )
#我们mid右侧所有数进行上述排序
quick_sort( li , low +1 , end )
#入口函数
if __name__ == '__main__':
li = [19,97,9,17,1,8]
quick_sort(li , 0 , len(li) -1 )
print(li)
六、总结
快速排序是当前最为流行的排序算法之一,各大公司面试中频频出现,希望通过这篇文章,让你对快速排序知识点有一定的了解,在日后面试或各种考试中对你有所帮助!
目前在职Java开发,如果你现在也在学习Java,在入门学习Java的过程当中缺乏基础入门的视频教程, 可以关注并私信我:01。免费领取2020年最新Java基础精讲视频教程,学习手册,面试题,开发工具,PDF文档书籍教程,以下资料截图:
关注并私信我:01。即可领取以上学习资料。
相关推荐
- 国内外注塑机及电脑密码大全(常见注塑机通用密码)
-
一、国外注塑机(日本、德国等)东洋注塑机万能码:9422345日精注塑机密码:222|7777DAMEG注塑机密码:000000000新泻注塑机密码:241650|261450住友注塑机密码:...
- 并发编程实战来咯(并发编程的艺术和并发编程实战)
-
提到并发编程,就不得不提C++ConcurrencyinAction(SecondEdition)(《C++并发编程实战第2版》)啦!《C++并发编程实战第2版》英文原版&中文译版看到这个...
- 无锁队列Disruptor原理解析(无锁队列应用场景)
-
队列比较队列...
- 无锁CAS(附无锁队列的实现)(cas是一种无锁算法)
-
本文所有代码对应的Github链接为:https://github.com/dongyusheng/csdn-code/tree/master/cas_queue...
- Linux高性能服务器设计(linux 服务器性能)
-
C10K和C10M计算机领域的很多技术都是需求推动的,上世纪90年代,由于互联网的飞速发展,网络服务器无法支撑快速增长的用户规模。1999年,DanKegel提出了著名的C10问题:一台服务器上同时...
- 浅谈Go语言的并发控制(go语言 并发)
-
前言本文原创,著作权归...
- Datenlord |Etcd 客户端缓存实践(etcd 数据存储)
-
简介和背景...
- 无锁编程——从CPU缓存一致性讲到内存模型
-
缓存是一个非常常用的工程优化手段,其核心在于提升数据访问的效率。缓存思想基于局部性原理,这个原理包括时间局部性和空间局部性两部分:...
- 如何利用CAS技术实现无锁队列(cas会锁总线吗)
-
linux服务器开发相关视频解析:...
- Kotlin协程之一文看懂Channel管道
-
概述Channel类似于Java的BlockingQueue阻塞队列,不同之处在于Channel提供了挂起的send()和receive()方法。另外,通道Channel可以...
- 详解C++高性能无锁队列的原理与实现
-
1.无锁队列原理1.1.队列操作模型...
你 发表评论:
欢迎- 一周热门
-
-
前端面试:iframe 的优缺点? iframe有那些缺点
-
带斜线的表头制作好了,如何填充内容?这几种方法你更喜欢哪个?
-
漫学笔记之PHP.ini常用的配置信息
-
其实模版网站在开发工作中很重要,推荐几个参考站给大家
-
推荐7个模板代码和其他游戏源码下载的网址
-
[干货] JAVA - JVM - 2 内存两分 [干货]+java+-+jvm+-+2+内存两分吗
-
正在学习使用python搭建自动化测试框架?这个系统包你可能会用到
-
织梦(Dedecms)建站教程 织梦建站详细步骤
-
【开源分享】2024PHP在线客服系统源码(搭建教程+终身使用)
-
2024PHP在线客服系统源码+完全开源 带详细搭建教程
-
- 最近发表
- 标签列表
-
- mybatis plus (70)
- scheduledtask (71)
- css滚动条 (60)
- java学生成绩管理系统 (59)
- 结构体数组 (69)
- databasemetadata (64)
- javastatic (68)
- jsp实用教程 (53)
- fontawesome (57)
- widget开发 (57)
- vb net教程 (62)
- hibernate 教程 (63)
- case语句 (57)
- svn连接 (74)
- directoryindex (69)
- session timeout (58)
- textbox换行 (67)
- extension_dir (64)
- linearlayout (58)
- vba高级教程 (75)
- iframe用法 (58)
- sqlparameter (59)
- trim函数 (59)
- flex布局 (63)
- contextloaderlistener (56)