基础算法之交换排序（二）-快速排序算法
快速排序思想：
快速排序是一种基于交换的排序算法，是对冒泡排序的一种改进算法。快速排序的算法思想是基于分治策略的，从原始待排序数据集合中选择一个数据作为基准（pivot)元素，经过一趟排序后使得数列满足以下三个条件：
- 基准元素位定位到排序后队列中的最终位置；
- 不大于基准元素的数据都位于基准元素的左侧；
- 不小于基准元素的数据都位于基准元素的右侧。
快速排序的实现：
public class Main{
public static void swap(int[] data,int random,int left){
//交互两个位置的数据
int temp = data[left];
data[left] = data[random];
data[random]=temp;
}
/**
* 对数据进行一次快速排序，划分为左子序列+基数+右序列
* 采用：挖坑法+填坑法实现
* 基准选择：左边第一个
**/
public static int partition(int[] data,int left,int right){
int pivotPosition,index =left; //选择第一个元素作为基准元素、初始坑位(index表示坑位置)
int pivot = data[index]; //基准值
while(left<right){
while(left<right&&data[right]>=pivot){
//从右端开始寻找比pivot更具有资格占据当前坑位的元素
right--;
}
if(left<right){
//当前right下标指示的元素更具有资格占据当前的坑位（因为data[right]<pivot）
data[index] = data[right]; //将right位置的值填充到坑位中
index = right; //right位置成为新的坑
left++; //占坑完毕 left左边的元素本轮排序中不再调整
}
while(left<right&&data[left]<=pivot){
//从左侧未确定位置的元素中寻找比基准元素更具备资格占用当前坑位（在右侧）
left++;
}
if(left<right){
//left位置的元素---> index位置
data[index] = data[left];
//left位置成为新的坑
index = left;
right++;
}
}
data[index] = pivot;
return index;
}
public static void quickSort(int[] data,int left,int right){
if(left>=right){return;}
int partition = partition(data,left,right);
quickSort(data,left,partition-1);
quickSort(data,partition+1,right);
}
public static void main(String[] args){
int[] data = {8,12,3,9,10,21,7,28,5};
}
}
划分方式的改进
每次划分基准元素选择第一个可能会造成每次划分的左右子序列的长度差别比较大（例如数据基本呈现逆序状态时，快速排序的性能退化至O(n2））。因此通过随机选择基数（pivot)的方式规避该情形，使得算法性能接近平均情况。实现如下：
public static int partitionRandomPivot(int[] data,int left,int right){
int random = new Random().nextInt(right-left+1)+left;
swap(data,random,left); //将pivot交换到数列的最左端
int pivot = data[left];
int pivotPosition,index = left;
//同上
}
基于指针交换的划分方式
以上两种划分实现中都是基于填坑的方式。还有基于指针交换的方式，实现划分的过程。实现如下：
public static int partitionPointerSwap(int[] data,int left,int right){
int random = new Random().nextInt(right-left+1)+left;
swap(data,random,left);
int pivotpostion = left;
int pivot = data[left];
while(left<right){
while(left<right&&data[right]>=pivot){
right--;
}
while(left<right&&data[left]<=pivot){
left++;
}
swap(data,left,right);
}
/*
上面的循环执行完时，left==right;且data[left]<=pivot.最后data[left]与基准元素交换，定位基准元素的位置。
*/
swap(data,left,pivotposition);
}
