快速排序
思想
一趟排序将数据分割成两个部分，一部分都比pivot小，一部分都比pivot大。
确定好pivot的位置。然后分别递归这两部分。步骤
1.选pivot
2.分割
3.递归最基本方法
public class QuickSort {
public void quictSort(int[] nums,int low ,int high){
int pivot;
if (low<high){
pivot = partition(nums,low,high);//分成两段
quictSort(nums,low,pivot-1);//递归排序
quictSort(nums,pivot+1,high);
}
}
private int partition(int[] nums, int low, int high) {
int pivot;
pivot = nums[low];//划分点，基准点
while (low<high){
while (low<high&&nums[high]>pivot){
high--;
}
swap(nums,low,high);//比pivot小的调换过去
while (low<high&&nums[low]<pivot){
low++;
}
swap(nums,low,high);//比pivot大的调换过去
}
return low;//重合的地方就是pivot的位置
}
private void swap(int[] nums, int low, int high) {
int temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
}优化
为什么可以优化？
二分法最好的就是都是截取的正好都是差不多的两个部分。当有部分是排好序的时候，快排的效率会急速下降，
所以优化的点就在于如何如何选取最合适的基准点也就是pivot。随机取pivot算法
/*随机选择枢轴的位置，区间在low和high之间*/
int SelectPivotRandom(int arr[],int low,int high)
{
//产生枢轴的位置
srand((unsigned)time(NULL));
int pivotPos = rand()%(high - low) + low;
//把枢轴位置的元素和low位置元素互换，此时可以和普通的快排一样调用划分函数
swap(arr[pivotPos],arr[low]);
return arr[low];
} 三值取中的算法
待排序序列的前(第一个位置)、中(中间位置)、后(最后一个位置)三个记录中的中间值(按大小排序)
作为枢轴。
9 1 7 5 2 8 6 3 4
↑ ↑ ↑
low mid high
前 中 后 9>4>2
随机数的话是需要有随机种子的。小数组的优化
当数组的长度够小的时候，采用插入排序，不再使用快速排序。
因为长度分割到够小后，继续分割的效率要低于直接插入排序。 优化后的代码
public class OptimizedQuickSorter extends QuickSort {
/**
* 插入排序的最大数组长度
*/
private static final int MAX_LENGTH_INSERT_SORT = 7;
/**
* 对数组arr[low...high]的子序列作快速排序，使之有序
*/
@Override
public void quickSort(int[] arr, int low, int high) {
int pivotLoc; // 记录枢轴(pivot)所在位置
if ((high - low + 1) > MAX_LENGTH_INSERT_SORT) {
// 待排序数组长度大于临界值，则进行快速排序
pivotLoc = partition(arr, low, high); // 将arr[low...high]一分为二,并返回枢轴位置
quickSort(arr, low, pivotLoc - 1);// 递归遍历arr[low...pivotLoc-1]
quickSort(arr, pivotLoc + 1, high); // 递归遍历arr[pivotLoc+1...high]
} else {
// 2. 优化小数组时的排序方案，将快速排序改为插入排序
insertSort(arr, low, high); // 对arr[low...high]子序列进行插入排序
}
}
/**
* 在arr[low...high]中利用三值取中选取枢轴(pivot)，将arr[low...high]分成两部分，
* 前半部分的子序列的记录均小于pivot，后半部分的记录均大于pivot;最后返回pivot的位置
*/
protected int partition(int[] arr, int low, int high) {
int pivot;
pivot = medianOfThree(arr, low, high); // 1. 优化排序基准，使用三值取中获取中值
while (low < high) { // 从数组的两端向中间扫描 // A
while (low < high && arr[high] >= pivot) { // B
high--;
}
// swap(arr, low, high); // 将比枢轴pivot小的元素交换到低位
arr[low] = arr[high]; // 3. 优化不必要的交换，使用替换而不是交换 // C
while (low < high && arr[low] <= pivot) { // D
low++;
}
// swap(arr, low, high); // 将比枢轴pivot大的元素交换到高位
arr[high] = arr[low]; // 3. 优化不必要的交换，使用替换而不是交换 // E
}
arr[low] = pivot; // F
return low; // 返回一趟下来后枢轴pivot所在的位置
}
/**
* 通过三值取中(从arr[low...high]子序列中)获取枢轴pivot的值，让arr[low]变成中值;并返回计算的枢轴(pivot)
*/
private int medianOfThree(int[] arr, int low, int high) {
int mid = low + ((high - low) >> 1); // mid = low + (high-low)/2, 中间元素下标
// 使用三值取中得到枢轴
if (arr[low] > arr[high]) { // 目的：让arr[low] <= arr[high]
swap(arr, low, high);
}
if (arr[mid] > arr[high]) { // 目的：让arr[mid] <= arr[high]
swap(arr, mid, high);
}
if (arr[mid] > arr[low]) { // 目的： 让arr[low] >= arr[mid]
swap(arr, low, mid);
}
// 经过上述变化，最终 arr[mid]<=arr[low]<=arr[high]，则arr[low]为中间值
return arr[low];
}
/**
* 对子序列arr[low...high]进行插入排序
*/
private void insertSort(int[] arr, int low, int high) {
int i, j;
int tmp;
for (i = low + 1; i <= high; i++) { // 从下标low+1开始遍历,因为下标为low的已经排好序
if (arr[i] < arr[i - 1]) {
// 如果当前下标对应的记录小于前一位记录,则需要插入,否则不需要插入，直接将记录数增加1
tmp = arr[i]; // 记录下标i对应的元素
for (j = i - 1; j >= low && arr[j] > tmp; j--) {
arr[j + 1] = arr[j]; // 记录后移
}
arr[j + 1] = tmp; // 插入正确位置
}
}
}
}