这篇文章将为大家详细讲解有关如何使用java实现快速排序，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
1) 快速排序算法介绍
快速排序(quicksort)是对冒泡排序的一种改进。基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按照此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
2) 快速排序法示意图:
3) 快速排序算法应用实列:
要求: 对[-9,78,0,23,-567,70] 进行从小到大的排序,要求使用快速排序法。
a. 如果取消左右递归,结果是 -9 -567 0 23 78 70
b. 如果取消左右递归,结果是 -567 -9 0 23 78 70
c. 如果取消左递归,结果是 -9 -567 0 23 70 78
d. 代码实现
计算
安全
数据库
网络和加速
企业服务
import java.util.Arrays;
//快速排序
public class QuickSort {
public static void main(String[] args) {
int[] arr= {-9,78,0,23,-567,70, -1,900, 4561};
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
QuickSort.quickSort(arr, 0, arr.length-1);
System.out.println("排序后");
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr,int left,int right) {
int l = left;//左下标
int r = right;//右下标
//中轴值,中间值
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[l]==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);
}
}
}关于“如何使用java实现快速排序”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/yuchener/blog/4548440
