AcWing 785.快速排序

一、 题目描述

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

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

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

1≤n≤100000
输入样例

1. 5
2. 3 1 2 4 5

复制代码

输出样例

1. 1 2 3 4 5

复制代码

二、思路分析 （排序再递归)

• 确定分界点
  - 定义left,right作为双指针，一个从头遍历，一个从尾遍历。选择数据中一个数为参考值（默认第一个数的值），这里记作target。
  
• 调整区间
  - 让left,right对应数据的值分别与之进行比较若left对应的值小于target就向后遍历，直到大于等于target时停下；若right对应的值大于target就向前遍历，直到小于等于target时停下。当left与right都停下时，交换left与right对应的数据的值。
  
• 递归处理左右两段
  - 重复以上操作，直到两者相遇。两者会相遇到此时的right处，以right为界，同样对其左右序列进行相同排序操作。
  

三、代码实现

1. import java.util.Scanner;
3. public class Main {
4.     static int N = 100010;
5.     static int[] a = new int[N];
7.     public static void main(String[] args) {
8.         Scanner scanner = new Scanner(System.in);
9.         int n = scanner.nextInt();
10.         for (int i = 0; i < n; i++) {
11.             a[i] = scanner.nextInt();
12.         }
13.         quick_sort(0, n - 1);
14.         for (int i = 0; i < n; i++) {
15.             System.out.println(a[i]);
16.         }
17.     }
19.     private static void quick_sort(int l, int r) {
20.         if (l >= r) return;
21.         int x = a[l + r >> 1];
22.         int i = l - 1, j = r + 1;
23.         while (i < j) {
24.             do {
25.                 i++;
26.             } while (a[i] < x);
28.             do {
29.                 j--;
30.             } while (a[j] > x);
32.             if (i < j) {
33.                 int t = a[i];
34.                 a[i] = a[j];
35.                 a[j] = t;
36.             }
37.         }
38.         quick_sort(l, j); // 递归调用时，确保 j 在合法范围内
39.         quick_sort(j + 1, r);
40.     }
41. }

复制代码

四、快速排序代码模板

• 用j划分
  

1. void quick_sort(int[] a, int l, int r) {
2.         if (l >= r) return;
3.         int x = a[l + r >> 1];
4.         int i = l - 1, j = r + 1;
5.         while (i < j) {
6.             do {
7.                 i++;
8.             } while (a[i] < x);
10.             do {
11.                 j--;
12.             } while (a[j] > x);
14.             if (i < j) {
15.                 int t = a[i];
16.                 a[i] = a[j];
17.                 a[j] = t;
18.             }
19.         }
20.         quick_sort(a,l, j); // 递归调用时，确保 j 在合法范围内
21.         quick_sort(a,j + 1, r);
22.     }

复制代码

• 用i做划分
  

1.     void quick_sort(int[] a, int l, int r) {
2.         if (l >= r) return;
3.         int x = a[l + r + 1 >> 1];
4.         int i = l - 1, j = r + 1;
5.         while (i < j) {
6.             do {
7.                 i++;
8.             } while (a[i] < x);
10.             do {
11.                 j--;
12.             } while (a[j] > x);
14.             if (i < j) {
15.                 int t = a[i];
16.                 a[i] = a[j];
17.                 a[j] = t;
18.             }
19.         }
20.         quick_sort(a, l, i - 1); // 递归调用时，确保 j 在合法范围内
21.         quick_sort(a, i, r);
22.     }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！