思想： 任取待排序序列中一个数据元素为基准值，按此基准值将此待排序序列分为两部分，小于此基准值划为左待排序序列，大于此基准值的值划为右待排序序列，然后重复此步骤于左右序列，直至所有的数据均变为有序为止。
快速排序有数种实现方法：
我们先介绍挖坑法（必须掌握）：
挖坑法的思想：即在待排序序列中选出了一个基准值以后，将此基准值从所在的数组位置中移到临时变量中，此数组位置便成为一个空位，然后创建两个标记，左标记与右标记，右标记先走，遇到小于基准值的数据则将此值放入当前的空位中，然后左标记再走，直到两者相遇，两者相遇时，此时正指向空位，将临时变量的值赋给此空位，然后将左区间与右区间递归上述操作。
我们取第一个下标的元素为基准值。
//我选取待排序序列的第一个下标的值作为基准值，所以应先移动右标记。
public void quicksort(int []array){
quickwakeng(array,0,array.length-1);
//quickhore(array,0,array.length-1);
}
private void quickwakeng(int []array,int start,int end) {
if (start >= end) {
return;
}
int starttmp = start;
int tmp = array[start];
while (start < end) {
while (array[end] >= tmp && start < end) {
end--;
}
//可以用当前start与end标记当前停止指向的位置，来表示空位置
array[start] = array[end];
//此时end所指向的空间为空，
while (array[start] <= tmp && start < end) {
start++;
}
array[end] = array[start];
}
array[start] = tmp ;
quickwakeng(array,starttmp,start-1); //start的值一定为0吗？不一定
quickwakeng(array,start+1,array.length-1); //end的值不一定为array.length-1,但是递归时，end不会局限array.lenth-1
}
hoare法的思想：
hoare法也是快速排序的一种实现方法。
其实现思想是，用两个标记分别指向待排序区间的两端，移动left至大于基准值的数据下标，移动right至小于基准值的数据下标，当left遇到大于基准值的数据并且right遇到小于基准值的数据，则两者进行交换，直到left==right,即而在左区间与右区间进行相同递归操作。
private void quickhore(int []array,int start,int end){
if(start>=end){
return;
}
//确定基准值
int tmpleft = start;
while (start<end){
//先走右边的指标
while (array[end]>=array[tmpleft]&&start<end){
end--;
}
//此时找到end指向小于基准值的值
while (array[start]<=array[tmpleft]&&start<end){
start++;
}
//此时找到start标记指向的大于基准值的值
swap(array,start,end);
//如果start等于end时，此时交换不会出现错误。
}
//当start等于end时：交换当前值与基准值
swap(array,tmpleft,start);
quickhore(array,tmpleft,start-1);
quickhore(array,start+1,array.length-1);
}
快速排序的优化：
当快速排序遇到有序数据或逆序数据时，其时间复杂度会达到O(N^2), 空间复杂度会达到O(N),如果数据过多，会导致内存崩溃，举例：
所以需要优化算法思想，优化思想：
private void quickwakeng(int []array,int start,int end) {
if (start >= end) {
return;
}
int midIndex = getMiddle(array,start,end);
swap(array,start,midIndex);
//我们需要对下面这段代码逻辑进行封装一下
int pivot = partition(array,start,end);
quickwakeng(array,start,pivot-1); //start的值一定为0吗？不一定
quickwakeng(array,pivot+1,end); //end的值不一定为array.length-1,但是递归时，end不会局限array.lenth-1
}
private int getMiddle(int[] array, int left, int right) {
int mid = (left+right)/2;
if(array[left] < array[right]) {
if(array[mid] < array[left]) {
return left;
}else if(array[mid] > array[right]) {
return right;
}else {
return mid;
}
}else {
if(array[mid] > array[left]) {
return left;
}else if(array[mid] < array[right]) {
return right;
}else {
return mid;
}
}
}