|
目录
算法思想
三指针分区法
代码实现（Java）
时间复杂度
算法思想
当所有数的左边的数据都小于等于这个数，右边的数据都大于这个数时，数组就有序了。
三指针分区法
- 先初始化主元为首元，然后初始化三个指针：smaller和equal都初始化为下标为数组第二个、bigger初始化为尾元。smaller为扫描指针，每次移动smaller
- 当smaller扫描到的数字小于主元，则下标为smaller和equal的需要交换数据，这样就又将小于主元的放在一起了，然后smaller和equal都要自增
当smaller扫描到的数字等于主元，直接将smaller自增
当smaller扫描到的数字大于主元，就将小标为smaller和bigger上的数据交换，bigger再自减(和单向扫描分区法处理一样）
- 直到smaller已经超过了bigger,这时候（equal-1）指向的是最后一个小于等于主元的数，交换首元与（equal-1）上的数据
- 将小于主元和大于主元的两个数组进行快速排序
- 32分16，16分8，8分4，4分2，2分1，当左右两边数组的长度为0时，这个数组就已经排好序了
代码实现（Java）
private static void sort(int[] array, int start, int end) {
//初始化三指针
//小于主元的指针和等于主元的指针都初始化为下标为数组第二个
//大于主元的指针初始化为尾元
int smaller = start+1;
int equal = smaller;
int bigger = end;
//设置退出条件
if(smaller > bigger) return ;
//选择主元，一般为首元
int num = array[start];
/*
* 当smaller扫描到的数字小于主元，则下标为smaller和equal的需要交换数据，这样就又将小于主元的放在一起了，然后smaller和equal都要自增
* 当smaller扫描到的数字等于主元，直接将smaller自增
* 当smaller扫描到的数字大于主元，就将小标为smaller和bigger上的数据交换，bigger再自减(和单向扫描分区法处理一样）
*/
while(smaller <= bigger) {
if(array[smaller] < num) {
swap(array, equal, smaller);
equal++;
smaller++;
}
else if(array[smaller] == num) {
smaller++;
}
else if(array[smaller] > num) {
swap(array, smaller, bigger);
bigger--;
}
}
//交换首元与right上的数
swap(array, start, equal-1);
//继续将right两边的数组进行快速排序
sort(array, start, equal-2);
sort(array, bigger+1, end);
}
private static void swap(int[] array, int sc, int r) {
int num = array[sc];
array[sc] = array[r];
array[r] = num;
}
时间复杂度
每次处理数组的一半，一共要处理 次，每次处理要扫描 个数据，所以时间复杂度为 | 
转播
