本篇文章为你整理了AcWing 785.快速排序(Java)()的详细内容,包含有 AcWing 785.快速排序(Java),希望能帮助你了解 AcWing 785.快速排序(Java)。
题目来源:AcWing 785.快速排序
给定你一个长度为 n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入共两行,第一行包含整数 n。
第二行包含 n 个整数(所有整数均在 1∼109 范围内),表示整个数列。
输出共一行,包含 n 个整数,表示排好序的数列。
1≤n≤1000001
输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5
首先快速排序的话,我们应当先确定一个基准点x,这个基准点可以是左端点,可以是右端点,可以是中间值,也可以是数组中任意一值
确定了基准值x后,便是调整区间,将整个序列调整为小于等于x都在x左边, 大于等于x都在x右边
那么问题来了,如何确定呢?这里我们使用双指针的方法,i作为左指针,j作为右指针,分别向中间进行移动,移动条件便是q[i]与q[j]分别于x进行对比,看是否满足左右两边的定义,当不满足时,停止移动,并交换双方的值,然后接着移动直到i=j
当i=j后,我们可以发现x左端皆小于x,右端皆大于x。但是并不是有序排序,那么我们采用递归的方法,再次对左右两边的两端进行上述操作,而在这两次循环中我们又可以再进行递归操作......直到递归到i==j,结束递归
这样我们就得到了一个有序数组
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
//输入数组大小与数组的值
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int []q = new int[n];
for (int i = 0; i i++) {
q[i] = sc.nextInt();
//进行排序
quick_sort(q,0,n-1);
//输出结果
for(int i=0; i i++) System.out.print(q[i] + " ");
public static void quick_sort(int q[],int left,int right){
if(left = right) return;//如果左端比右端大或者相等,无需排序直接结束
int x= q[left + (right - left) / 2]; //基准为中间值
//定义两个指针
int i = left - 1;
int j = right + 1;
while (i j){
do i ++ ; while (q[i]
do j -- ; while (q[j]
//while循环进行到此时时,i,j皆是处于不满足do-while循环的状态
//手打一个swap交换i,j双指针
if(i j){
int t = q[i];
q[i] = q[j];
q[j] = t;
//进行递归,各自对两边进行排序
quick_sort(q,left,j);
quick_sort(q,j+1,right);
以上就是AcWing 785.快速排序(Java)()的详细内容,想要了解更多 AcWing 785.快速排序(Java)的内容,请持续关注盛行IT软件开发工作室。
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。