快速排序是运用了分治思想的排序方式,具有O(NlogN)的平均时间复杂度,极端情况下时间复杂度为O(N^2),跟冒泡排序一样,但是快排的实际效率远比最坏情况好很多。它的关键部分是一轮划分(由Partition()函数完成),每一轮划分会导致序列中的元素分成两部分,一部分比参照数小,一部分比参照数大。函数QSort()通过不断调用Partition()完成给定序列的排序,当排序序列细化为1个元素时,排序也就完成了,因为单个元素是有序的。
算法描述如下:
void QSort(int *a, int f, int r)
{
if(f < r)
{
int i = Partition(a, f, r);
QSort(a, f, i - 1);
QSort(a, i + 1, r);
}
}
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
int Partition(int *a, int f, int r)
{
int i = f;
int j = r + 1;
int t = a[f];
while(1)
{
while(a[++i] < t && i < r);//从前向后找>= t 的元素
//因为要保证结束时左边的元素都比t小,右边的都比t大,
//所以,while中a[++i] < t不能有"=",下面的while同
while(a[--j] > t);//从后往前<= t的元素
if(i >= j)
break;
swap(&a[i], &a[j]);
}
a[f] = a[j];//循环结束后为什么是a[f] = a[j],而不是a[f] = a[i] ?
//原因是,++i在++j前面,导致最后一个j一定指向最后一个 <= t
//的元素(要么是t自己,要么是从前往后数,最后各个 <= t 的元素),
//而i却不是
a[j] = t;
return j;
}上面的Partition()存在很有必要优化的地方
我们先来看几个例子:
如果执行Partition()前的序列是:
10 5 6 3 2 7
用第一个元素做参照(上面说的t),我们发现后面所有的元素都小于t,因此i后一直向后找,直到找到最后一个元素;而j一次就找到了<= t 的元素,也就是最后一个元素。这样,while(1)结束了,Partition()执行之后,原序列变成:
5 6 3 2 7 10
如果执行Partition()前的序列是:
10 14 15 16 20
用第一个元素做参照(上面说的t),我们发现后面所有的元素都大于t,因此i一次就找到了 >= t的元素;而j一直向前找,直到找到第一个元素;这样,while(1)结束了,Partition()执行之后,原序列不变,仍然是:
10 14 15 16 20
上面这两种情况都是我们不愿看到的,因为它导致Partition()执行后,两边的元素很不平均,极端情况下(比如,原序列是已排好序的),快排的时间复杂度是O(N^2),跟冒泡排序一样。为了避免这种情况出现,我们可以采用随机化的策略,即不老是选择第一个元素做参照,为达到这一目的,可以提前将后面的任意一个元素与第一个元素交换。
优化后的算法为:
int Partition(int *a, int f, int r)
{
int i = f;
int j = r + 1;
int k = rand() % (r - f + 1) + f + 1;//随机化
swap(&a[k], &a[f]);
int t = a[f];
while(1)
{
while(a[++i] < t && i < r);
while(a[--j] > t);
if(i >= j)
break;
swap(&a[i], &a[j]);
}
a[f] = a[j];
a[j] = t;
return j;
}接下来我们在快速排序中划分函数Partition()的基础上讲解一下
线性时间选择问题。所谓线性时间就是在平均O(N)的时间内找出无序序列中第k大的元素。先排序再找出该元素是比较容易想到的方法,但排序所花的时间很可能超过O(N)(比如,快排、堆排的时间复杂度都是O(NlogN),选择排序、插入排序以及冒泡排序时间复杂度是O(N^2))。
其实结合Partition()函数完成的一次划分我们很容易想到,选择第k大的元素不一定要排序原序列,因为经过一次划分,原序列以参照数t为基准被分成了两部分,
我们要找的第k大的数要么就是t,要么在t左边,要么在t右边,因此每次迭代我们只需要考虑原序列接近1/2的数字就行了。显然,Select()函数的效率跟Partition()的好坏有直接关系,最坏情况下,Select()函数的时间复杂度仍为O(N^2)。
算法描述如下:
int Select(int *a, int f, int r, int k)
{
//if(r - f + 1 < k)
// return -1;
int j = Partition(a, f, r);
if(j == k + f - 1)
return a[j];
else if(j > k + f - 1)
return Select(a, f, j - 1, k);
else
return Select(a, j + 1, r, k + f - j - 1);
}
int Select2(int *a, int f, int r, int k)
{
if(f == r)
return a[f];
int i = Partition(a, f, r);
int j = i - f + 1;
if(k <= j)
return Select(a, f, i, k);
else
return Select(a, i + 1, r, k - j);
}上面两种描述略有不同,前面是我写的,后面一个是书上的。这两种算法都忽略了一个问题,那就是没有考虑非法情况,即要选择的数超出了原有序列,比如原序列只有n个数,而却让找出第n+1大的数。
posted on 2012-07-17 16:46
小鼠标 阅读(3615)
评论(1) 编辑 收藏 引用 所属分类:
排序