1. 原理以及实现说明

快速排序的原理其实很简单。

• 首先有一串数组
  

• 然后我们在数组内选一个数记为x，可以是第一个，最后一个，哪个都行，然后记录下来，就以取到最后一个元素为例吧。

• （em，本来应该是随机取的，但是随机取的话，代码设计就有点麻烦，会碰到诸如角标越界，死循环之类的问题，这里就不做过多分析，有兴趣的小伙伴可以试试。）
  

• 然后呢，这个数组以x为界限分为前后两部分
  

• 然后对这前后两个部分的元素分别给指针进行遍历，注意一下遍历的方向，两个指针都往中间（也就是x）那边靠。
  

• 然后给个循环，让这两个部分每个元素同时与x进行大小比较，以从小到大排序为例的话，就是：

如果前面部分的遍历到的元素比x大，指针i就暂时停下来
后面部分如果遍历到比x小的，指针j也暂时停下来
然后比较两个指针的位置，
如果指针i在指针j的前面的话就交换两个指针指向的元素，然后两个指针继续刚才的比较操作
如果指针i在指针j的后面的话就停止整个遍历。

如此，就能保证在x左边的元素都比x小，在x的右边的元素都比x大。
然后不断递归上面的操作就行了。
附上代码如下：

package com.zero.workTest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.System.exit;

public class HomeWork {
    public static void main(String[] args) throws IOException {
    	//这边使用的是流的形式输入，要是觉得麻烦的小伙伴可以选择用Scanner，这里就不展示了
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        //这边比较懒，没有管非法输入的，毕竟只是为了实现算法，就直接转换过来了，下面也是，不在重复说明
        int n = Integer.valueOf(bufferedReader.readLine());
        String[] arr = bufferedReader.readLine().split(" ");
        if (n!=arr.length){
            System.out.println("输入错误");
            exit(0);
        }
        int[] arr2 = new int[n];
        for (int i = 0;i<n;i++){
            arr2[i] = Integer.valueOf(arr[i]);
        }

        fast_sort(arr2, 0, n-1);

        for (int i = 0;i<n;i++){
            System.out.print(arr2[i]+" ");
        }
    }

	//快排实现
    private static void fast_sort(int[] arr2, int l, int r) {
        if (l>=r) return;           //注意这里要取等，如果不去等下面会死循环
        int x = arr2[r];
        int i = l-1;
        int j = r+1;
        while(i<j) {
            do { i++; } while (arr2[i] < x);//注意这里不能取到等，如果去等会越界
            do {
                j--;
            } while (arr2[j] > x);//注意这里不能取到等，如果去等会越界
            if (i<j)
                swap(arr2,i,j);
        }
        fast_sort(arr2,l,i-1);
        fast_sort(arr2,i,r);
    }

    private static void swap(int[] arr2, int i, int j) {
        int emp = arr2[i];
        arr2[i] = arr2[j];
        arr2[j] = emp;
    }

}