# Java中快速排序的优化技巧：随机取样、三数取中和插入排序

### 快速排序基础

``````public static void quickSort(int[] arr){
quick(arr,0,arr.length-1);
}

private static void quick(int[] arr,int start,int end){
if (start>=end){
return;
}

int pivot=partition(arr,start,end);
quick(arr,start,pivot-1);
quick(arr,pivot+1,end);
}

private static int partition(int[] arr,int left,int right ){
int tmp=arr[left];
while (left<right){
while (left<right&&arr[right]>=tmp){
right--;
}
arr[left]=arr[right];
while (left<right&&arr[left]<=tmp){
left++;
}
arr[right]=arr[left];
}

arr[left]=tmp;

return left;
}``````

### 优化1：随机取样

``````private static void quick(int[] arr,int start,int end){
if (start>=end){
return;
}
int randomIndex = getRandomIndex(start, end);
swap(arr, start, randomIndex);
int pivot=partition(arr,start,end);
quick(arr,start,pivot-1);
quick(arr,pivot+1,end);
}
public int getRandomIndex(int low, int high) {
Random rand = new Random();
return rand.nextInt(high - low + 1) + low;
}``````

### 优化2：三数取中

``````private static void quick(int[] arr,int start,int end){
if (start>=end){
return;
}
//三数取中法
int index=midThree(arr,start,end);
int tmp=arr[start];
arr[start]=arr[index];
arr[index]=tmp;
int pivot=partition1(arr,start,end);
quick(arr,start,pivot-1);
quick(arr,pivot+1,end);
}
private static int midThree(int[] arr,int left,int right){
int mid=(left+right)/2;
if (arr[left]<right){
if (arr[mid]<arr[left]){
return left;
}else if (arr[mid]>arr[right]){
return right;
}else {
return mid;
}
}else {
//arr[left]>right
if (arr[mid]<arr[right]){
return right;
}else if (arr[mid]>arr[left]){
return left;
}else {
return mid;
}
}
}``````

### 优化3：插入排序

``````private static void quick(int[] arr,int start,int end){
if (start>=end){
return;
}
if(end-start+1<=14){
//插入排序
insertSort2(arr, start, end);
return;
}
//三数取中法
int index=midThree(arr,start,end);
int tmp=arr[start];
arr[start]=arr[index];
arr[index]=tmp;
int pivot=partition(arr,start,end);
quick(arr,start,pivot-1);
quick(arr,pivot+1,end);
}

public static void insertSort2(int[] arr,int start,int end){
for (int i = start; i <= end; i++) {
int temp=arr[i];
int j=i-1;
while (j>=0&&arr[j]>temp){
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;
}
}
private static int midThree(int[] arr,int left,int right){
int mid=(left+right)/2;
if (arr[left]<right){
if (arr[mid]<arr[left]){
return left;
}else if (arr[mid]>arr[right]){
return right;
}else {
return mid;
}
}else {
//arr[left]>right
if (arr[mid]<arr[right]){
return right;
}else if (arr[mid]>arr[left]){
return left;
}else {
return mid;
}
}
}

private static int partition(int[] arr,int left,int right ){
int tmp=arr[left];
while (left<right){
while (left<right&&arr[right]>=tmp){
right--;
}
arr[left]=arr[right];
while (left<right&&arr[left]<=tmp){
left++;
}
arr[right]=arr[left];
}

arr[left]=tmp;

return left;
}``````

THE END