AcWing 785.快速排序（Java）

题目来源：AcWing 785.快速排序
题目描述

给定你一个长度为 n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式

输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。
输出格式

输出共一行，包含 n 个整数，表示排好序的数列。
数据范围

1≤n≤1000001≤n≤100000
输入样例：

1. 5
2. 3 1 2 4 5

复制代码

输出样例：

1. 1 2 3 4 5

复制代码

思路讲解

• 首先快速排序的话，我们应当先确定一个基准点x，这个基准点可以是左端点，可以是右端点，可以是中间值，也可以是数组中任意一值
  
• 确定了基准值x后，便是调整区间，将整个序列调整为小于等于x都在x左边, 大于等于x都在x右边
  
• 那么问题来了，如何确定呢？这里我们使用双指针的方法，i作为左指针，j作为右指针，分别向中间进行移动，移动条件便是q与q[j]分别于x进行对比，看是否满足左右两边的定义，当不满足时，停止移动，并交换双方的值，然后接着移动直到i=j
  
• 当i=j后，我们可以发现x左端皆小于x，右端皆大于x。但是并不是有序排序，那么我们采用递归的方法，再次对左右两边的两端进行上述操作，而在这两次循环中我们又可以再进行递归操作......直到递归到i==j，结束递归
  
• 这样我们就得到了一个有序数组
  

代码

1. import java.util.Scanner;
3. public class Main {
4.     public static void main(String[] args) {
5.         //输入数组大小与数组的值
6.         Scanner sc = new Scanner(System.in);
7.         int n = sc.nextInt();
8.         int []q = new int[n];
9.         for (int i = 0; i < n; i++) {
10.             q[i] = sc.nextInt();
11.         }
12.         //进行排序
13.         quick_sort(q,0,n-1);
14.         //输出结果
15.         for(int i=0; i<n; i++)  System.out.print(q[i] + " ");
16.     }
18.     public static void quick_sort(int q[],int left,int right){
19.         if(left >= right) return;//如果左端比右端大或者相等，无需排序直接结束
20.         int x= q[left + (right - left) / 2]; //基准为中间值
21.         //定义两个指针
22.         int i = left - 1;
23.         int j = right + 1;
24.         //
25.         while (i < j){
26.             do i ++ ; while (q[i] < x);
27.             do j -- ; while (q[j] > x);
28.             //手打一个swap交换i，j双指针
29.             if(i < j){
30.                 int t = q[i];
31.                 q[i] = q[j];
32.                 q[j] = t;
33.             }
34.         }
35.         //进行递归,各自对两边进行排序
36.         quick_sort(q,left,j);
37.         quick_sort(q,j+1,right);
38.     }
39. }

复制代码

通过截图



免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！