快速排序法及优化
快速排序
快排是目前平均时间复杂度最小的排序法。体现了分治的思想。算法比较经典，因此在这里记录一下，加深印象。
快速排序中比较核心的是要寻找一个pivot值。即枢轴值。
核心思想就是，将需要排序的数列，以pivot值为中心，以大小左右分开。然后对左右两段数组再重新选取pivot值。以此递归。
下面我们来看一看代码。
public class QuickSortManager {
int pivotloc;
public void quickSort(int[] arr , int low , int high){
if(low < high){
pivotloc = partition(arr, low, high);
quickSort(arr , low , pivotloc-1);
quickSort(arr, pivotloc+1, high);
}
}
int partition(int[] arr , int low , int high){
int pivot = arr[low];
while(low < high){
while(low < high && arr[high] > pivot){
high--;
}
swap(arr, low, high);
while(low < high && arr[low] <= pivot){
low++;
}
swap(arr, low, high);
}
return low;
}
void swap(int[] arr , int a , int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}代码总共30行左右，非常简单。在这个方法中，我们将数组arr的第一个值作为pivot。然后以low,high作为数组开头和结尾的索引。一旦发现arr[high]<pivot或是arr[low]>pivot，即交换它与pivot的值，然后更换遍历方向。最后当low>=high时即完成一次分治。并返回此时pivot的索引值。
然后通过递归，我们再对pivot左边和右边分别进行分治，即可完成排序。
举个小例子
3 5 4 1 2 6 // pivot = 3
2 5 4 1 3 6
2 3 4 1 5 6
2 1 4 3 5 6
2 1 3 4 5 6 // low = 2
第一次排序结束
确定了 pivot 左边的一定比 3 小 ，右边的一定比 3 大
2 1 // pivot = 2
1 2 // low = 0
4 5 6 // pivot = 4 low = 0
排序完成 优化
简化swap
我们在分治的时候发现，其实pivot的值每次交换并没有太大的意义。每次我们只是需要当前pivot的索引值和大小，pivot本身在一次分治时不会变化。所以我们考虑将其取出。每次交换时，直接覆盖掉，需要交换的值，最后再将pivot值赋进数组。
进入之后的代码入下：
int partition(int[] arr , int low , int high){
int pivot = arr[low];
while(low < high){
while(low < high && arr[high] > pivot){
high--;
calculationCount++;
}
arr[low] = arr[high];
//swap(arr, low, high);
while(low < high && arr[low] <= pivot){
low++;
calculationCount++;
}
arr[high] = arr[low];
//swap(arr, low, high);
}
arr[low] = pivot;
return low;
}3 5 4 1 2 6 // pivot = 3
2 5 4 1 2 6
2 5 4 1 5 6
2 1 4 1 5 6
2 1 4 4 5 6
2 1 3 4 5 6 // low = 2
第一次排序结束
确定了 pivot 左边的一定比 3 小 ，右边的一定比 3 大
2 1 // pivot = 2
1 2 // low = 0
4 5 6 // pivot = 4 low = 0
排序完成 经过这样的简化，我们可以减少大量的赋值操作。
优选pivot值
原先的算法中，我们pivot值在每次分治时，都取的是arr[low]。我们知道，快速排序法中，任意选取pivot值，都能完成排序，但这有可能导致最坏情况。即，选到最大值或最小值，将其余的数据全部分治到了一边。这相当于浪费了一次分治。只是确定了一个值的位置。
所以我们考虑选一个更好的pivot。
为了避免最坏情况的出现。我们每次分治时，不再选择arr[low]作为pivot。而是采用arr[low]、arr[high]、arr[middle]的中位值来作为pivot。这样就避免了会选择最大值或最小值作为pivot的情况。程序比较简单，就不赘述了。
多种排序
并不是所有情况下，快速排序法都是最优选择。由于分治的思想，我们可以在分治后，所需处理的数据较少时。采用插值排序进行排序。 插入排序代码如下：
void insertSort(int arr[] , int low , int high){
int i, j;
int tmp;
for (i = low + 1; i <= high; i++) {
if (arr[i] < arr[i - 1]) {
tmp = arr[i];
for (j = i - 1 ; j >= low && arr[j] > tmp ; j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = tmp;
}
}
}在quickSort中进行判断和调用：
private static final int INSERT_SORT_LENGTH = 7;
int pivotloc;
public void quickSort(int[] arr , int low , int high){
if(low < high){
if(high - low + 1 > INSERT_SORT_LENGTH){
pivotloc = partition(arr, low, high);
quickSort(arr , low , pivotloc-1);
quickSort(arr, pivotloc+1, high);
}else{
insertSort(arr, low, high);
}
}
}以上。 笔者初学，如有谬误，不吝赐教。