目录
分析
一.快速排序的思想
- 取数组中的第一个元素作为标准值，把小于标准值的元素放在其左侧smaller区域，把大于标准值的元素放在其右侧larger区域。那么标准值的位置就移动到了排序完成以后他应该在的位置。
- 把smaller,larger两部分分别通过这种方式进行排序。
数组5 4 2 7 3 6 为例,[ ]括起来的是此次比较的标准值：
第一轮后：4 2 3 [5] 7 6
第二轮后：2 3 [4] 5 6 [7]
第三轮后：2 [3] 4 5 [6] 7
第四轮后：[2] 3 4 5 6 7
第五轮后：2 3 4 5 6 7
二.partition函数如何实现
partition函数的功能：实现将数组的值分为<v和>v区域
我们从数组的中间状态开始讨论。
如图L指向标准值v，J指向<v区的最后一个元素，i指向待分类元素。那么arr[L+1…J]是<v区，arr[J+1…i-1]是>v区。
- 若e>v，将i向右移动一位，那么e就被归入了>v的区域。i也指向了下一个待分类数据的位置。
- 若e<=v
1.将e与>v区域的第一个值交换
2.J++将元素e归入<v的部分，i++进行对下个数据的分类。
递归实现
public static void quickSort(int[] arr){
quickSort(arr,0,arr.length-1);
}
public static void quickSort(int[] arr,int l,int r){
if(l>=r){
return;
}
int p=partition(arr,l,r);
quickSort(arr,l,p-1);
quickSort(arr,p+1,r);
}
//返回的p使得arr[l..p-1]<arr[p],arr[p+1...r]>arr[p]
public static int partition(int[] arr,int left,int right){
//数组结构：|v|smallerPart|largerPart|unPaitition
//arr[left+1...j]<v arr[j+1...i)>v
int j=left;//smaller部分的最后一个数据的下标
int i=left+1;//待分类的数值的下标
//依次把每个值分类
while(i<=right){
if(arr[i]<=arr[left]){
//若当前数据小于等于判别值，当前值与larger区域的最小值交换
//最终smaller部分扩大1，待判别指针向前移动
int temp=arr[i];
arr[i]=arr[j+1];
arr[j+1]=temp;
j++;
}
i++;
//若当前数据大于判别值，将待判别数据向前移动一个即可，当前数据将自动归入larger区域
}
//分类完成，交换v和smaller区的最后一个值
int temp=arr[left];
arr[left]=arr[j];
arr[j]=temp;
//最后返回判别值的位置
return j;
}