1.选取枢纽元：三数中值分割法，得到的中间值即作为mid，将数组分为arrays[mid]左边的比它小，右边的比它大
2.进行划分partition：首先将arrays[mid]放在arrays[high]处，然后对数组范围内的数值进行比较，
（左右两边分别有一个指针来进行寻找，arrays[left] <= arrays[high]，arrays[right] >= arrays[high]）找到不符合要求的值，在左右交换位置。
在left>=right时，终止查找，然后将swap(arrays, left, high);即可将枢纽元放入合适的位置
3.循环进行左右两侧的选择枢纽元，划分
注意：在partition之后，传回来的是划分好之后arrays[mid]应该在的位置，而不再是mid处了
package sort;
import static sort.PrintRes.swap;
/**
* Created by Skye on 2018/3/27.
*/
public class QuickSort {
public void quickSort(Integer[] arrays){
if(arrays.length == 0) return;
quickSort( arrays, 0, arrays.length - 1 );
}
public void quickSort(Integer[] arrays, int low, int high){
if(low >= high) return;
int mid = threeMid(arrays, low, high);
swap(arrays, mid, high);
int num = partition(arrays, low, high);
quickSort( arrays, low, num - 1 );
quickSort(arrays, num + 1, high);
}
public int threeMid(Integer[] arrays, int low, int high){
int mid = (low + high) / 2;
if(arrays[low] > arrays[mid]) swap(arrays, low, mid);
if(arrays[low] > arrays[high]) swap( arrays, low, high );
if(arrays[mid] > arrays[high]) swap( arrays, mid, high );
return mid;
}
public int partition(Integer[] arrays, int low, int high){
int left = low;
int right = high - 1;
//把arrays[mid]放到合适的位置
while(left < right){
while(left < right && arrays[left] <= arrays[high]) {
left++;
}
while(right > left && arrays[right] >= arrays[high]) {
right--;
}
swap(arrays, left, right);
}
swap(arrays, left, high);
return left;
}
}
注意：可以将交换改成覆盖，来减少交换次数
将partition方法修改：
public int partition(Integer[] arrays, int low, int high){
int left = low;
int right = high;
//把arrays[mid]放到合适的位置
//枢纽元放在最右边，记录枢纽元的值
int temp = arrays[high];
while(left < right){
while(left < right && arrays[left] <= temp) {
left++;
}
//相当于交换arrays[left] arrays[right]，交换后，right-1（开始时，right处放置的是枢纽元的值，就是将枢纽元覆盖掉）
arrays[right--] = arrays[left];
while(right > left && arrays[right] >= temp) {
right--;
}
//相当于交换arrays[left] arrays[right]，交换后，left+1（此时，arrays[left]的值已经存放在arrays[right]中了）
arrays[left++] = arrays[right];
}
//最后再将枢纽元放回到数组中
arrays[left] = temp;
return left;
}
对于小数组，可以将排序改为插入排序
将quickSort(Integer[] arrays, int low, int high)修改如下：
public void quickSort(Integer[] arrays, int low, int high){
if(low >= high) return;
if(high - low > 10){
int mid = threeMid(arrays, low, high);
swap(arrays, mid, high);
int num = partition(arrays, low, high);
quickSort( arrays, low, num - 1 );
quickSort(arrays, num + 1, high);
} else{
for(int i = low + 1; i <= high; i++){
int j = i - 1;
int temp = arrays[i];
for(; j >= low; j--){
if(arrays[j] < temp) break;
arrays[j + 1] = arrays[j];
}
arrays[j + 1] = temp;
}
}
}
还可以将递归改成尾迭代：
（不太懂）
最终版
package sort;
import static sort.PrintRes.swap;
/**
* Created by Skye on 2018/3/27.
*/
public class QuickSort {
public void quickSort(Integer[] arrays){
if(arrays.length == 0) return;
quickSort( arrays, 0, arrays.length - 1 );
}
public void quickSort(Integer[] arrays, int low, int high){
if(low >= high) return;
if(high - low > 10){
int mid = threeMid(arrays, low, high);
swap(arrays, mid, high);
int num = partition(arrays, low, high);
quickSort( arrays, low, num - 1 );
quickSort(arrays, num + 1, high);
} else{
for(int i = low + 1; i <= high; i++){
int j = i - 1;
int temp = arrays[i];
for(; j >= low; j--){
if(arrays[j] < temp) break;
arrays[j + 1] = arrays[j];
}
arrays[j + 1] = temp;
}
}
}
public int threeMid(Integer[] arrays, int low, int high){
int mid = (low + high) / 2;
if(arrays[low] > arrays[mid]) swap(arrays, low, mid);
if(arrays[low] > arrays[high]) swap( arrays, low, high );
if(arrays[mid] > arrays[high]) swap( arrays, mid, high );
return mid;
}
public int partition(Integer[] arrays, int low, int high){
int left = low;
int right = high;
//把arrays[mid]放到合适的位置
//枢纽元放在最右边，记录枢纽元的值
int temp = arrays[high];
while(left < right){
while(left < right && arrays[left] <= temp) {
left++;
}
//相当于交换arrays[left] arrays[right]，交换后，right-1（开始时，right处放置的是枢纽元的值，就是将枢纽元覆盖掉）
arrays[right--] = arrays[left];
while(right > left && arrays[right] >= temp) {
right--;
}
//相当于交换arrays[left] arrays[right]，交换后，left+1（此时，arrays[left]的值已经存放在arrays[right]中了）
arrays[left++] = arrays[right];
}
//最后再将枢纽元放回到数组中
arrays[left] = temp;
return left;
}
}