基本思想
本文以从小到大排序的方式进行讲解。
快速排序的基本思想是任取待排序序列的一个元素作为中心元素（可以用第一个，最后一个，中间的任意一个），称之为枢轴元素，pivot。
1）将数组中所有比pivot小的放左边；
2）将数组中所有比pivot大的放右边；
3）形成左右两个子表
4）然后对左右两个子表再按照前面的算法进行排序，直到每个子表的元素只剩下一个。
快速排序是用到了分而治之的思想，将一个数组分成两个数组的方法为：
1）先从数组右边找到一个比pivot小的元素，将数组的第一个位置赋值给该元素。
2）再从数组的左边找到一个比pivot大的元素，将从上面取元素的位置赋值为该值。
3）依次进行，直到左右相遇，把pivot赋值到相遇位置。
示例
输入数组
array为 [ 30，20，50，80，60，3，10，40]
将30定义为pivot，查询左边的元素为left，初始值为第一个元素的索引【0】；查询右边的元素为right，初始值为最后一个元素的索引【7】。
首轮排序：
从右边开始，找到第一个比pivot小的元素，如果没找到对right一直自减1；
找到则将该值赋值给pivot位置；并且空余该位置。
然后从左边开始找一个比pivot大的元素；如果没有则left一直自增1；
找到后，将该值赋值给上一步中空余的位置。
重复上述操作，直至left光标与right光标相遇，并将pivot的值，赋值给光标位置。
然后将数组分成俩部分：[10，20，3]，[60，80，50，40]
再进行上述流程，反复直至最后一个元素。
代码
对每一个数组进行分化的代码如下：
初始化pivot为数组的第一个元素；
只要left还小于right就进行循环；
外层循环内部如下：
先从右边找一个比pivot小的元素；
将当前left所指元素赋值为找到的元素；
再从左边找一个比pivot大的元素；
将当前right所指元素赋值为找到的元素；
当left与right相等，将pivot赋值在此；
最后返回中间元素的索引。
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
while(left < right) {
while(left < right && arr[right] >= pivot) right--;
arr[left] = arr[right];
while(left < right && arr[left] <= pivot) left++;
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
快排代码：
第一个是快排的重载，直接传数组；
然后调用另一个重载函数，传数组，left为第一个元素索引0，right为最后一个元素索引数组长度减去1；
主要介绍传三个参数的快排函数：
定义一个将来划分为两个数组的中间元素的索引；
如果left比right小，进行一次划分，将返回来的值赋值给middle；
对left到middle - 1的部分进行一次快排（递归进行）；
对middle + 1到right的部分进行一次快排（递归进行）。
middle + 1到right的部分进行一次快排（递归进行）。
public static void quickSort(int[] arr){
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr,int left,int right){
int middle;
if(left < right){
middle = partition(arr,left,right);
quickSort(arr,left,middle-1);
quickSort(arr,middle+1,right);
}
}
完整代码：
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
quickSort(new int[]{39,28,55,87,66,3,17,39});
}
public static void quickSort(int[] arr){
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr,int left,int right){
int middle;
if(left < right){
middle = partition(arr,left,right);
quickSort(arr,left,middle-1);
quickSort(arr,middle+1,right);
}
}
public static int partition(int[] arr,int left,int right){
int pivot = arr[left];
while(left < right){
while(left<right && arr[right] >= pivot)
right--;
arr[left] = arr[right];
while(left < right && arr[left]<= pivot)
left++;
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
}