快速排序模板

例题：

给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。

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

数据范围
1≤n≤100000
输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5

思想：

1.找分界点：如x=f[l]，f[(l+r)/2]，f[r]；
2.调整，使i的左边的值都<=x,j的右边的值都>=x，直到i，j相遇；
3.递归的处理两段数组；

模板：

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] f=new int[n];//存放待排序数据
        for(int i=0;i<n;i++){
            f[i]=sc.nextInt();
        }
        quick_sort(f,0,n-1);
        for(int num:f){
            System.out.print(num+" ");
        }
    }
    static void quick_sort(int[] f,int l,int r){
        if(l>=r)return;
        int x=f[(l+r)/2];//分界点
        int i=l-1,j=r+1;//初始化i,j;因为下面操作过程中是先++i/--j,故令i=l-1,j=r+1;
        while(i<j){
            while(f[++i]<x);//找到第一个>=x的值;
            while(f[--j]>x);//找到第一个<=x的值;
            if(i<j){//如果i
                int t=f[j];
                f[j]=f[i];
                f[i]=t;
            }
        }
        quick_sort(f,l,j);//因为>=x的值都在j的右边，故j和j的左边都小于x;
        quick_sort(f,j+1,r);
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

对边界的处理有下面两种方法：
quick_sort(f, l, j);
quick_sort(f, j + 1, r);
或
quick_sort(f, l, i - 1); //i的左边的小于等于x；
quick_sort(f, i, r); //i和i的右边都大于等于x；

对于两种不同的边界，需要对应各自不同的分界点：
如果区间取[l,j]和[j+1,r]这种，那么x不应该取右边界(如r、(l+r+1)/2)。
应取 x = f[l]; x = f[(l+r)/2]。为啥不能取x=f[r]，举个例子：[1,2]，自行模拟一下就知道了，会进入死递归;
如果区间取[l,i-1]和[i,r]这种，那么x不应该取左边界(l、(l+r)/2)。
应取 x = f[r]; x = f[(l+r+1)/2];
两种边界及其边界值只需要记住其中一种即可。

时间复杂度和稳定性

时间复杂度：最好为O(n*logn),最坏为O(n^2);
（一）快速排序的最好情况O（nlogn）

快速排序的实现方式，就是在当前区间中选择一个x，区间中所有比x小的数都需要放到x的左边，而比x大的数则放到右边。在理想的情况下，我们选取的分界点刚好就是这个区间的中位数。也就是说，在操作之后，正好将区间分成了满足数字个数相等的左右两个子区间（快排是按照值的大小划分，个数可能相等，可能不等）。

递归的第一层，n个数被划分为2个子区间，每个子区间的数字个数为n/2；
递归的第二层，n个数被划分为4个子区间，每个子区间的数字个数为n/4；
递归的第三层，n个数被划分为8个子区间，每个子区间的数字个数为n/8;
  …

递归的第logn层，n个数被划分为n个子区间，每个子区间的数字个数为1；

（二）快速排序的最坏情况O（n^2）

对于每一个区间，我们在处理的时候，选取的轴刚好就是这个区间的最大值或者最小值。比如我们需要对n个数排序，而每一次进行处理的时候，选取的轴刚好都是区间的最小值。于是第一次操作，在经过调换元素顺序的操作后，最小值被放在了第一个位置，剩余n-1个数占据了2~n个位置；第二次操作，处理剩下的n-1个元素，又将这个子区间的最小值放在了当前区间的第1个位置，以此类推…每次操作，都只能将最小值放到第一个位置，而剩下的元素，则没有任何变化。所以对于n个数来说，需要操作n次即n层，才能为n个数排好序。而每一次操作都需要遍历一次剩下的所有元素，这个操作的时间复杂度是O（n），所以总时间复杂度为O（n^2）。

稳定性：为不稳定排序