1.Java代码实现
public class QuickSort {
/**
* 选择一个哨兵节点，将所有小于哨兵节点的元素放到左边，大于哨兵节点的元素放到右边
* 最后将哨兵节点和小部分中的最右边那个值交换（j），i就处于大部分的最左边
* @param array 数组元素
* @param low
* @param high
*/
public static void quickSort(Integer[] array,int low,int high){
if(low>=high){
return;
}
int index = divide(array,low,high);
quickSort(array,low,index-1);
quickSort(array,index+1,high);
}
private static int divide(Integer[] array,int low,int high){
int i = low+1, j = high;
while(i<=j){
while(i<=j&&array[i]<=array[low]){
i++;
}
while(i<=j&&array[j]>array[low]){
j--;
}
if(i<=j) {
int k = array[j];
array[j] = array[i];
array[i] = k;
}
}
int t = array[low];
array[low] = array[j];
array[j] = t;
return j;
}
}
2.优化策略（三数选中+插入+聚集）
由于一般哨兵节点都选取最左边或最右边的元素，容易造成时间复杂度为O(N*N)的情况（原数组有序），通过选取三个数（一般可以是最左元素，中间元素，最右元素）中的中间那个数来作为哨兵节点可以减少发生最坏的情况。
在元素个数比较少的情况下，插入排序要由于快排，所以在划分元素足够少的情况下，可以通过插入排序来进行排序。
同时在第一次遍历时，将重复元素聚集在一起，可以减少迭代次数。
public class QuickSort {
/**
* @param array 数组元素
* @param low
* @param high
*/
public static void quickSort(Integer[] array,int low,int high){
if(low>=high){
return;
}
selectPivotMedianOfThree(array,low,high);
int index = divide(array,low,high);
int i = index-1,j = index+1;
//聚集
int ii = i,jj = j;
while(ii>=low){
if(array[index].equals(array[ii])){
swap(array[ii],array[i]);
i--;
}
ii--;
}
while(jj<=high){
if(array[index].equals(array[jj])){
swap(array[jj],array[j]);
j++;
}
jj++;
}
if(i-low < 10){
insertSort(array,low,i);
}else {
quickSort(array, low, i);
}
if(high-j < 10){
insertSort(array,j,high);
}else {
quickSort(array, j, high);
}
}
private static int divide(Integer[] array,int low,int high){
int i = low+1, j = high;
while(i<=j){
while(i<=j&&array[i]<=array[low]){
i++;
}
while(i<=j&&array[j]>=array[low]){
j--;
}
if(i<=j) {
swap(array[i],array[j]);
}
}
swap(array[low],array[j]);
return j;
}
//三数选中
private static void selectPivotMedianOfThree(Integer[] array,int low,int high){
int m = (low+high)/2;
//实现 array[mid] <= array[low] <= array[high]
if(array[high] < array[low]){
swap(array[high],array[low]);
}
if(array[high] < array[m]){
swap(array[high],array[m]);
}
if(array[m] > array[low]){
swap(array[m],array[low]);
}
}
//插入排序
private static void insertSort(Integer[] array,int low,int high){
for(int i = low+1; i < high; i++){
Integer da = array[i];
int j = i - 1;
for(; j >= low; j--){
if(array[j] <= da){
break;
}
array[j+1] = array[j];
}
array[j+1] = da;
}
}
private static void swap(Integer a, Integer b){
int tem= a;
Field field= null;
try {
field = Integer.class.getDeclaredField("value");
field.setAccessible(true);
field.setInt(a, b);
field.setInt(b, tem);
} catch (Exception e) {
e.printStackTrace();
}
}
}
