基本思想
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述
快速排序使用分治法来把一个串（名单）分为两个子串（子列表）具体算法描述如下：
- 会把数组当中的一个数当成基准数
- 一般会把数组中最左边的数当成基准数，然后丛两边进行检索。丛右边检索比基准数小的，
然后左边检索比基准数大的。如果检索到了，就停下，然后交换这两个元素，然后继续检索。
过程
实例数组为
第一步
一：找到一个基准数temp = 4，定义两个指针 i ，j。分别指向左边和右边
二：先移动右边的指针找到一个小于 5 的数就是 1
在移动左边的指针找到一个大于 5 的数就是 6
将这两个数交换
三：i 和 j 一旦相遇就会停止，将相遇位置的数与基准数temp = 5 进行互换
第一次排序完毕，排序完成以后我们会发现排序的左边比基准数小，右边比基准数大
第二步递归
把基准数左右两边的数据看成两个新的数组
再次排序左边成功右边j和i相遇交换位置
得出结果
代码
public class QuickSort {public static void main(String[] args) {int[] arr = new int[]{587,956,12,47,30,20,15,11,21,31,57,91,35,120};sort(arr,0,arr.length -1);System.out.println("排序后结果为："+Arrays.toString(arr));}public static void sort(int[] arr, int left, int right) {if(left >= right) {return;}//定义第一个数为基准数int base = arr[left];//定义变量i只指向左边int i = left;//定义j指向最右边int j = right;//i j 不相遇while(i != j) {while(arr[j] >= base && i < j) {j--;}while(arr[i] <= base && i < j) {i++;}//交换int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// i 和 j相遇 , 第一个位置和相遇位置进行交换arr[left] = arr[i];arr[i] = base;sort(arr,left,i-1);sort(arr,i+1,right);}
}
