【排序算法】java实现快排算法
2022-12-21 16:54:00 TwelveT 243
一、快速排序算法是一种基于交换的高效的排序算法,它采用了分治法的思想:1、从数列中取出一个数作为基准数(枢轴,pivot)。2、将数组进行划分(partition),将比基准数大的元素都移至枢轴右边,将小于等于基准数的元素都移至枢轴左边。3、再对左右的子区间重复第二步的划分操作,直至每个子区间只有一个元素。快排最重要的...

一、快速排序算法是一种基于交换的高效的排序算法,它采用了分治法的思想:
1、从数列中取出一个数作为基准数(枢轴,pivot)。2、将数组进行划分(partition),将比基准数大的元素都移至枢轴右边,将小于等于基准数的元素都移至枢轴左边。
3、再对左右的子区间重复第二步的划分操作,直至每个子区间只有一个元素。
快排最重要的一步就是划分了。划分的过程用通俗的语言讲就是“挖坑”和“填坑”。
快速排序时间复杂度
快速排序的时间复杂度在最坏情况下是O(N2),平均的时间复杂度是O(N*lgN)。
这句话很好理解:假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N),需要遍历多少次呢?至少lg(N+1)次,最多N次。
(01) 为什么最少是lg(N+1)次?快速排序是采用的分治法进行遍历的,我们将它看作一棵二叉树,它需要遍历的次数就是二叉树的深度,而根据完全二叉树的定义,它的深度至少是lg(N+1)。
因此,快速排序的遍历次数最少是lg(N+1)次。
(02) 为什么最多是N次?这个应该非常简单,还是将快速排序看作一棵二叉树,它的深度最大是N。因此,快读排序的遍历次数最多是N次。
快速排序稳定性
快速排序是不稳定的算法,它不满足稳定算法的定义。
算法稳定性 -- 假设在数列中存在a[i]=a[j],若在排序之前,a[i]在a[j]前面;并且排序之后,a[i]仍然在a[j]前面。则这个排序算法是稳定的!
二、快速排序算法流程如下:
(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。(2)将大于等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于等于分界值,而右边部分中各元素都大于等于分界值。
(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样将左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。
/**
* @author twelvet
* @WebSite www.twelvet.cn
* @Description: 、快速排序(取出中间值左右各自排序递归即可)
*/
public class QuickSort {
public static void main(String[] args) {
int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
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值小放到左边
while (l < r) {
// 在pivot的左边一直找,找到大于pivot值,才退出
while (arr[l] < pivot) {
l += 1;
}
// 在pivot的右边一直找,找到小于等于pivot值,才退出
while (arr[r] > pivot) {
r -= 1;
}
if (l >= r) {
break;
}
// 交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// 如果交换完后,发现这个arr[l] == pivot值 相等 --前移动
if (arr[l] == pivot) {
r -= 1;
}
// 如果交换完后,发现这个arr[r] == pivot值 相等 ++前移动
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);
}
}
}
免责声明
本站提供的一切软件、教程和内容信息仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络收集整理,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑或手机中彻底删除上述内容。如果您喜欢该程序和内容,请支持正版,购买注册,得到更好的正版服务。我们非常重视版权问题,如有侵权请邮件与我们联系处理。敬请谅解!
![]() |
相关文章
-
12-20Java 中是如何获取 IP 属地的,IP精准定位
-
12-20JVM 调优工具总结篇
-
12-19JVM 性能调优之 jstat
-
12-19JVM 性能调优之 jps
-
12-19JVM 性能调优之 jinfo
-
12-19JVM 性能调优之 jstack
-
12-19JVM 性能调优之 jmap
-
12-18Java 创建线程池的正确姿势: Executors 和 ThreadPoolExecutor 详解
-
12-18Spring Bean的生命周期(一图看懂bean生命周期)
-
12-18循环依赖之手写代码模拟spring循环依赖