快速排序算法
快速排序算法的核心思想是分治法（Divide and Conquer）。
快速排序算法通过以下步骤实现排序：
1. 选择基准值 : 从数列中选择一个元素作为基准值（pivot），通常选择第一个元素。
2. 分区操作 : 重新排列数列，使得所有小于基准值的元素都移到基准的前面，而所有大于基准值的元素都移到基准的后面。这一步完成后，基准值就处于其最终位置。
3. 递归排序 : 递归地将小于和大于基准值的子数列进行快速排序。
在每次分区过程中，至少有一个元素被放置在其最终位置，这保证了算法的收敛性。快速排序的平均时间复杂度为O(n log n)，但在最坏情况下可以退化到O(n^2)。尽管如此，由于其高效、就地排序（不需要额外存储空间）的特点，快速排序通常被认为是实践中最有效的通用排序算法之一。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void quickSort(int[] arr, int l, int r){
if(l >= r){
return;
}
//必须固定值,不可固定位置，毕竟这个位置的值会发生变化
int mid = arr[l + r >> 1];
int i = l -1, j = r + 1;
// 左右区间交换位置，让左边区间的值都小于mid，右边区间的值都大于mid
while (i < j){
while (arr[++i] < mid){};
while (arr[--j] > mid){};
if (i < j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
// 递归排序左右两个区间，最后的结果就是无论多大的区间都是左边小右边大，自然就排序好了
quickSort(arr, l, j);
quickSort(arr, j+1, r);
}
public static void main(String[] args) throws IOException {
// 输入要读入的数据个数
int n;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
// 输入要读取的数组，空格隔开
String[] strings = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(strings[i]);
}
// 快速排序算法
quickSort(arr,0,n-1);
for (int i = 0; i < n; i++) {
System.out.print(arr[i]+" ");
}
}
}