李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构和算法学习--快速排序
Leefs
2020-02-04 PM
1595℃
0条
# 数据结构和算法学习--快速排序 ### 一、快速排序法介绍 快速排序(Quicksort)是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 ### 二、快速排序法示意图 ![18.快速排序算法01.png][1] ![18.快速排序算法02.png][2] ### 三、快速排序法应用实例 要求:对[-9,78,0,23,-567,70]进行从小到大的排序,要求使用快速排序法。【测试8w和800w】 说明[验证分析]: (1)如果取消左右递归,结果是-9 -567 0 23 78 70 (2)如果取消右递归,结果是 -567 -9 0 23 78 70 (3)如果取消左递归,结果是 -9 -567 0 23 70 78 **代码实现** ```java public class QuickSort { public static void main(String[] args) { int[] arr={-9,78,0,23,-567,70,-1,900,4561}; quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static void quickSort(int[] arr,int left,int right){ int L = left; int R =right; //pivot中轴值 int pivot=arr[(left+right)/2]; int temp=0;//临时变量,作为 交换时使用 //while循环的目的是让比pivot值小放到左边 //比pivot值大放到右边 while(L
pivot){ R-=1; } //如果l>=r说明pivot的左右两的值,已经按照左边全部是 //小于等于pivot值,右边全部是大于等于pivot值 if(L>=R){ break; } //交换 temp=arr[L]; arr[L]=arr[R]; arr[R]=temp; //如果交换完后,发现这个arr[l]=pivot值 相等 r--, 前移 if(arr[L]==pivot){ R-=1; } //如果交换完后,发现这个arr[r]==pivot值 相等 l++, 后移 if(arr[R]==pivot){ L+=1; } } //如果 l==r,必须l++,r--, 否则为出现溢出 if(L==R){ L+=1; R-=1; } //向左递归 if(left
L){ quickSort(arr,L,right); } } } ``` **运行结果** ``` [-567, -9, -1, 0, 23, 70, 78, 900, 4561] ``` **完整代码** ```java public class QuickSort2 { public static void main(String[] args) { //int[] arr = {-9,78,0,23,-567,70, -1,900, 4561}; //测试快排的执行速度 // 创建要给80000个的随机的数组 int[] arr = new int[8000000]; for (int i = 0; i < 8000000; i++) { arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数 } System.out.println("排序前"); Date data1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(data1); System.out.println("排序前的时间是=" + date1Str); quickSort(arr, 0, arr.length-1); Date data2 = new Date(); String date2Str = simpleDateFormat.format(data2); System.out.println("排序前的时间是=" + date2Str); //System.out.println("arr=" + Arrays.toString(arr)); } public static void quickSort(int[] arr,int left, int right) { int l = left; //左下标 int r = right; //右下标 //pivot 中轴值 int pivot = arr[(left + right) / 2]; int temp = 0; //临时变量,作为交换时使用 //while循环的目的是让比pivot 值小放到左边 //比pivot 值大放到右边 while( l < r) { //在pivot的左边一直找,找到大于等于pivot值,才退出 while( arr[l] < pivot) { l += 1; } //在pivot的右边一直找,找到小于等于pivot值,才退出 while(arr[r] > pivot) { r -= 1; } //如果l >= r说明pivot 的左右两的值,已经按照左边全部是 //小于等于pivot值,右边全部是大于等于pivot值 if( l >= r) { break; } //交换 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; //如果交换完后,发现这个arr[l] == pivot值 相等 r--, 前移 if(arr[l] == pivot) { r -= 1; } //如果交换完后,发现这个arr[r] == pivot值 相等 l++, 后移 if(arr[r] == pivot) { l += 1; } } // 如果 l == r, 必须l++, r--, 否则为出现栈溢出 if (l == r) { l += 1; r -= 1; } //向左递归 if(left < r) { quickSort(arr, left, r); } //向右递归 if(right > l) { quickSort(arr, l, right); } } } ``` **运行结果** ``` 排序前 排序前的时间是=2020-02-04 22:19:26 排序前的时间是=2020-02-04 22:19:28 ``` [1]: https://lilinchao.com/usr/uploads/2020/02/1032271459.png [2]: https://lilinchao.com/usr/uploads/2020/02/781627042.png
标签:
数据结构和算法
,
排序
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://lilinchao.com/archives/541.html
上一篇
数据结构和算法学习--归并排序
下一篇
数据结构和算法学习--基数排序
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
43
标签云
Map
Jenkins
正则表达式
GET和POST
随笔
Java工具类
JavaWEB项目搭建
Kibana
队列
Java编程思想
Golang
链表
Spark
Netty
FileBeat
Hadoop
Nacos
Http
JavaWeb
Python
Spark RDD
Spark Core
Scala
Filter
Jquery
CentOS
SpringBoot
DataX
Beego
VUE
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞