三路快排
voidquickSort(int[] a, int left, int right) {
if (right <= left)
return;
/*
* 工作指针
* p指向序列左边等于pivot元素的位置
* q指向序列右边等于Pivot元素的位置
* i指向从左向右扫面时的元素
* j指向从右向左扫描时的元素
*/
int p, q, i, j;
int pivot;// 锚点
i = p = left;
j = q = right -1;
/*
* 每次总是取序列最右边的元素为锚点
*/
pivot =a[right];
while (true) {
/*
* 工作指针i从右向左不断扫描，找小于或者等于锚点元素的元素
*/
while (i < right && a[i] <=pivot) {
/*
* 找到与锚点元素相等的元素将其交换到p所指示的位置
*/
if (a[i] == pivot) {
swap(a, i, p);
p++;
}
i++;
}
/*
* 工作指针j从左向右不断扫描，找大于或者等于锚点元素的元素
*/
while (left <= j && a[j] >=pivot) {
/*
* 找到与锚点元素相等的元素将其交换到q所指示的位置
*/
if (a[j] == pivot) {
swap(a, j, q);
q--;
}
j--;
}
/*
* 如果两个工作指针i j相遇则一趟遍历结束
*/
if (i >= j)
break;
/*
* 将左边大于pivot的元素与右边小于pivot元素进行交换
*/
swap(a, i,j);
i++;
j--;
}
/*
* 因为工作指针i指向的是当前需要处理元素的下一个元素
* 故而需要退回到当前元素的实际位置，然后将等于pivot元素交换到序列中间
*/
i--;
p--;
while (p >= left) {
swap(a, i,p);
i--;
p--;
}
/*
* 因为工作指针j指向的是当前需要处理元素的上一个元素
* 故而需要退回到当前元素的实际位置，然后将等于pivot元素交换到序列中间
*/
j++;
q++;
while (q <= right) {
swap(a, j,q);
j++;
q++;
}
/*
* 递归遍历左右子序列
*/
quickSort(a,left, i);
quickSort(a, j,right);
}
privatevoidquick(int[] a) {
if (a.length > 0) {
quickSort(a, 0, a.length - 1);
}
}
privatevoidswap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] =arr[b];
arr[b] = temp;
}
双关键字快排
其实如果理解了快排的原理，双关键字快排其实是很简单的。
因为快排的思想是在待排序序列中选取一个记录，让它左边的都小于等于它，右边的都大于等于它，如此递归。
那么双关键字的思想就顺其自然：在待排序序列中选取一个记录，让它左边的第一关键字小于它，或者第一关键字等于它但是第二关键字小于它；右边的第一关键字大于它，或者第一关键字等于它但是第二关键字大于它，如此递归。（读起来有点绕，但是对照上一句仔细读读还是可以读懂的）
下面附上代码：
1 #include<stdio.h>
2 #include<stdlib.h>
3
4void myqsort(int *a,int *b,int left,int right)
5 {
6 inti=left;
7 intj=right;
8 intmid=a[(left+right)/2];
9 intmidb=b[(left+right)/2];
10 int temp;
11 while (i<j)
12 {
13 while(a[i]<mid||a[i]==mid&&b[i]<midb) i++;
14 while(a[j]>mid||a[j]==mid&&b[j]>midb) j--;
15 if (i<=j)
16 {
17 temp=a[i];
18 a[i]=a[j];
19 a[j]=temp;
20 temp=b[i];
21 b[i]=b[j];
22 b[j]=temp;
23 i++;
24 j--;
25 }
26 }27 if(i<right) myqsort(a,b,i,right);
28 if (left<j) myqsort(a,b,left,j);
29 }
30
31intmain()
32 {
33 int n;
34 scanf("%d",&n);
35 int i;
36 int *a=(int *)malloc(n*sizeof(int));
37 int *b=(int *)malloc(n*sizeof(int));
38 for (i=0;i<n;i++)
39 {
40 scanf("%d",a+i);
41 *(b+i)=i;
42 }
43 myqsort(a,b,0,n-1);
44 for(i=0;i<n;i++)
45 {
46 printf("%d ",*(a+i));
47 }
48 free(a);
49 free(b);
50 return0;
51 }
其实这个程序就把不稳定的快排变成了稳定的快排了！（因为添加了一个关键字，对于相等的就实现了本来在前面的还在前面）
时间复杂度推导
在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归树的深度就为.log2n.+1（.x.表示不大于x的最大整数），即仅需递归log2n次，需要时间为T（n）的话，第一次Partiation应该是需要对整个数组扫描一遍，做n次比较。然后，获得的枢轴将数组一分为二，那么各自还需要T（n/2）的时间（注意是最好情况，所以平分两半）。于是不断地划分下去，我们就有了下面的不等式推断。
1. T（n）≤2T（n/2） +n，T（1）=0
2. T（n）≤2（2T（n/4）+n/2） +n=4T（n/4）+2n
3. T（n）≤4（2T（n/8）+n/4） +2n=8T（n/8）+3n
4. ……
5. T（n）≤nT（1）+（log2n）×n= O(nlogn)
也就是说，在最优的情况下，快速排序算法的时间复杂度为O(nlogn)。
在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为 ，最终其时间复杂度为O(n2)。
快速排序平均需要大约2NlnN次比较，来对长度为n的排序关键字唯一的序列进行排序。 证明也比较简单：假设CN为快速排序平均花在比较上的时间，初始C0=C1=0，对于N>1的情况，有：其中N+1是分割时的比较次数， 表示将序列分割为0，和N-1左右两部分的概率为1/N, 划分为1，N-2左右两部分的概率也为1/N，都是等概率的。然后对上式左右两边同时乘以N，整理得到：
然后，对于N为N-1的情况：
两式相减，然后整理得到：
然后左右两边同时除以N(N+1)，得到:
可以看到，这是一个递归式，我们将 递归展开得到：
然后处理一下得到：
就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。
可惜的是，由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。
扫一扫
1万+
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
