排序--快速排序分析

快速排序实现代码:快速排序

可以看到我的代码有一个错误版,我在这里给大家分析一下为什么会出现错误,并且将之记录以便今后进行查阅。


快速排序(错误版分析)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Quick :: process(int array[], int l, int r) {
int temp = array[l];

while(l != r) {
while(array[r] >= temp) r--;
array[l] = array[r];
l++;

while(array[l] <= temp) l++;
array[r] = array[l];
r--;
}
array[l] = temp;

return l;
}

如上是我自己实现的单趟快速排序。


快排的算法思想

从待排序列中任意选择一个记录,以该记录为关键字,凡数组中元素小于该关键字的都移动至该关键字前面,反之移动到后面。致使一趟快速排序之后,以关键字为中点将数组分割成左右两个序列。然后分别对两个子序列递归进行快速排序,直至每个子序列中只含有一个元素为止。

为什么上面这个代码会出现段错误,首先我们来看:

1
while(array[r] >= temp) r--;

我在上面的while循环里面设定了l != r,也就是说一趟快速排序结束的标志就是当l == r的时候,然后在进行元素和关键字记录比较的时候,并没有重新写上l < r,考虑这种情况:

0 9 8 7 6 5 4 3 2 1

当我以0为关键字的时候,r再一直减小,然后r会越界,直到拿到一个垃圾数据比关键字0还要小的时候第一个循环才会停下来,这是一个错误。

第二个错误就是我多余的进行了l++,r–操作:

1
2
3
4
5
6
7
while(array[r] >= temp) r--;
array[l] = array[r];
l++;

while(array[l] <= temp) l++;
array[r] = array[l];
r--;

依旧是上面的序列,当前三句运行完之后,l的值会变为1,此时l与r已经相等,然而我又在后三句的最后进行了r–操作,此时会让l > r,最外层的while循环:

1
while(l != r)

就会失效,然后也就发生了段错误,改正之后,运行正确。


效率分析

快速排序的时间代价取决与关键字的选择,最简单的方法就是选择第一个记录或最后一个记录,但这样的弊端已然很明显,在每次进行递归分割的时候,如果是正序,那么就会将剩余记录全部分到一个序列当中而另一个序列为空。假如有10个数,第一趟经过9次比较,左半序列为空,第二趟经过8次比较,左半序列为空… …以次类推共需要n-1趟排序,比较次数为O(n2),等同于冒泡排序。

为避免这种情况,我们可以选取中间位置对应记录的关键字。

最好的情况下,每次分割都将序列分为两个长度相等的子序列,则总共就需要分割log2N次,因此算法的时间代价在最好情况下就是O(N*log2N),比较幸运的是,快速排序的平均时间复杂度就是这个值,所以快速排序仍然是一种非常高效的排序方法。

空间复杂度:快排需要分割log2N次,每次都需要一个辅助空间,因此快速排序的空间复杂度为O(log2N)。

最后,快速排序并不稳定。

坚持原创技术分享,您的支持将鼓励我继续创作!
0%