快速排序
此文章python写法 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。步骤如下
针对具体的基数的选择方式和区别方式的不同,主要有四种方式:
思考:
对于普通快排,我们将等于的数一并放到左边后者右边,在一般情况下,排序效率都很快,能达到O(nlogn),
但是当序列含有大量相等数字时,普通快排会使得大量等于的数集中位于某一边,造成分区不平衡的问题,使得普通快排退化成O(n^2),
这时对于等于的数的处理就显得很重要了,针对普通快速排序的改进版本——双路排序和三路排序,就应运而生了。
不一定:双路三路快排,只有再序列含有大量相等元素事性能才能比普通的好,负责性能会比普通快排稍差,因为,双/三路快排比普通快排稍复杂,会维护多些指针,就会对对出一些额外的赋值和比较开销
普通快速排序:从左到右或从右到左的单向扫描。设立两个区:小于区,大于等于区
对于含有大量重复元素的序列,即使是随机化快排效率也很差 于是再次改进,
1.双路快排: 从两端向中间挺近,设立两个区:小于等于区,大于等于区 2.三路快排: 从两端向中间挺近,设立三个区:小与区,等于区,大于区
由左到右扫描,设立两个区,小于区,大于等于区
public class QuickSortOne {
public static void main(String[] args) {
int[] arr=new int[]{
4,1,7,6,9,2,8,0,3,5,44,32,53,76,86,9,12,32,14,13,12};
int l=0;
int r=arr.length-1;
quickSort(arr,l,r);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int p = partition(arr, l, r);//分割,返回分割点p
quickSort(arr,l,p-1);//递归地对左部分快排
quickSort(arr,p+1,r);//递归地对右部分快排
}
/*_partition()对arr[l...r]部分进行partition操作 返回p,使得arr[l...p-1] < arr[p] ; arr[p+1...r] >= arr[p] */
public static int partition(int[] arr, int l, int r) {
int v = arr[l];
int j = l;
for (int i = l + 1; i < r + 1; i++) {
if (arr[i] < v) {
j += 1;
swap(arr, i, j);
}else {
continue;
}
}
swap(arr, j, l);
return j;
}
/* 交换 */
public static void swap(int[] arry, int i, int j) {
int temp = arry[i];
arry[i] = arry[j];
arry[j] = temp;
}
}
我们知道,归并排序复杂度O(nlogn)中logn的原因是每次归并都是高度平衡的,即左右两支长度相等。平衡度越好,性能越接近logn。快排每次都从左边第一个数作为比较数,而对于渐进有序的数组来说,每次区分其实都是极其不平衡的(如下图),甚至会退化成O(n^2).
平均意义上,对于任何数组(包括渐进有序数组),快排遇到最差情况的概率将大大降低。代码如下
public class QuickSortTwo {
public static void main(String[] args) {
int[] arr=new int[]{
4,1,7,6,9,2,8,0,3,5,44,32,53,76,86,9,12,32,14,13,12};
int l = 0;
int r = arr.length - 1;
quickSort(arr, l, r);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int p = partition(arr, l, r);//分割,返回分割点p
quickSort(arr, l, p-1);//递归地对左部分快排
quickSort(arr, p + 1, r);//递归地对右部分快排
}
/*_partition()对arr[l...r]部分进行partition操作 返回p,使得arr[l...p-1] < arr[p] ; arr[p+1...r] >= arr[p] */
/* 单路改进版: 随机选取分割值,避免分出来的两块大小不均匀问题带来的性能下降 */
public static int partition(int[] arr, int l, int r) {
// 改进点:随机选取一个元素开始分割,而不是第一个元素
int piovt = (int) (l + Math.random() * (r - l));
swap(arr,l,piovt);
int v = arr[l];//# 将第一个元素(已随机化了)作为分割值
int j = l;
for (int i = l + 1; i < r + 1; i++) {
if (arr[i] < v) {
j += 1;
swap(arr, i, j);
} else {
continue;
}
}
swap(arr, j, l);
return j;
}
/* 交换 */
public static void swap(int[] arry, int i, int j) {
int temp = arry[i];
arry[i] = arry[j];
arry[j] = temp;
}
}
对于含有大量重复元素的数组,则对于与基准数相同的数,(根据所写代码不同)要么都分到了左边,要么都分到了右边。同样会造成分治不平衡的问题,造成性能退化。如下图所示:
1.双路快排: 从两端向中间挺近,设立两个区:小于等于区,大于等于区 2.三路快排: 从两端向中间挺近,设立三个区:小与区,等于区,大于区
从两端向中间挺近,设立两个区:小于等于区,大于等于区
如何克服含大量重复元素的数组导致不平衡问题: 等于基准的数在两边均有分布,避免集中在一边,从而克服了不平衡问题
/* 从两端向中间挺近,设立两个区:小于等于区,大于等于区 如何克服含大量重复元素的数组导致不平衡问题: 等于基准的数在两边均有分布,避免集中在一边,从而克服了不平衡问题。 */
public class QuickSortThree002 {
public static void main(String[] args) {
int[] arr=new int[]{
4,1,7,6,9,2,8,0,4};
int l = 0;
int r = arr.length - 1;
quickSort(arr, l, r);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int p = partition(arr, l, r);//分割,返回分割点p
quickSort(arr, l, p-1);//递归地对左部分快排
quickSort(arr, p + 1, r);//递归地对右部分快排
}
public static int partition(int[] arr, int l, int r) {
int piovt = (int) (l + Math.random() * (r - l));
swap(arr, piovt, l);
int v = arr[l];
int i = l +1;//i: <=区的右标记点
int j = r;// # j: >=区的左标记点
while (true) {
// # i,j相遇时停止
while (i <= j && arr[i] <= v) {
i++;// # i一直右移到大于v的值处
}
while (i <= j && arr[j] >= v) {
j--;// # j一直左移到小于v的值处
}
if (i > j) break;
swap(arr, j, i);
i++;
j--;
}
swap(arr, j, l);
return j;
}
/* 交换 */
public static void swap(int[] arry, int i, int j) {
int temp = arry[i];
arry[i] = arry[j];
arry[j] = temp;
}
}
从两端向中间挺近,设立三个区:小与区,等于区,大于区
如何克服含大量重复元素的数组导致不平衡问题: 等于基准的数在正好集中在了中间,而不是任意一边,从而克服了不平衡问题。
三路快排的额外的好处: 在继续递归时,中间的arr[lt+1,gt-1]是等号区,不用管了,这样在含有大量相同元素的时候就可以避免大量的运算 这也是3路快排在含有大量相同元素的状况下,保持优势的地方.
/* 从两端向中间挺近,设立三个区:小与区,等于区,大于区 如何克服含大量重复元素的数组导致不平衡问题: 等于基准的数在正好集中在了中间,而不是任意一边,从而克服了不平衡问题。 三路快排的额外的好处: 在继续递归时,中间的arr[lt+1,gt-1]是等号区,不用管了,这样在含有大量相同元素的时候就可以避免大量的运算 这也是3路快排在含有大量相同元素的状况下,保持优势的地方.。 */
public class QuickSortThreeLu {
public static void main(String[] args) {
int[] arr = new int[]{
4, 1, 7, 6, 7, 7, 9, 2, 8, 0};
int l = 0;
int r = arr.length - 1;
quickSort(arr, l, r);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int l, int r) {
if (l >= r) {
return;
}
int piovt = (int) (l + Math.random() * (r - l));
swap(arr, piovt, l);
int v = arr[l];
int lt = l; // # arr[l+1...lt] < v
int gt = r + 1;// # arr[gt...r] > v
int i = l + 1; //# arr[lt+1...i) == v
while (i < gt) {
if (arr[i] < v) {
swap(arr, i, lt + 1);
lt++;// [l+1,Lt Lt+1 i gt,r]
i++;//交换后,i右移,因为i指向了一个已处理的数(从等号区换来的)
} else if (arr[i] > v) {
swap(arr, i, gt - 1);
gt--;//交换后,i不需要动,因为i仍指向一个未处理的数(从乱序区换来的)
} else {
i++;
}
}
swap(arr, lt, l);
lt--;
quickSort(arr, l, lt);//继续对arr[l..lt]部分快排
quickSort(arr, gt, r);//继续对arr[gt,r]部分快排
/* # 而中间的arr[lt+1,gt-1]是等号区,不用管了。 # 这样在含有大量相同元素的时候就可以避免大量的运算 # 这也是3路快排在含有大量相同元素的状况下,保持优势的地方 */
}
/* 交换 */
public static void swap(int[] arry, int i, int j) {
int temp = arry[i];
arry[i] = arry[j];
arry[j] = temp;
}
}