C++算法:一次快速排序错误引发的思考

作者 : 开心源码 本文共4955个字,预计阅读时间需要13分钟 发布时间: 2022-05-12 共189人阅读

快速排序是目前基于关键字的内部排序算法中平均性能最好的,它采用了分治策略,这既是快速排序的优点也是它的缺点。从快速排序的算法形容上我们可以发现它具备递归的结构:

(1)确定一个分界,将待排序的数组分为左、右两个部分;

(2)使所有小(大)于临界值的数据移到左部分,大(小)于临界值的数据移到右部分;

(3)这时左、右两个部分成为了两个独立的数组,分别对它们执行(1)(2)(3)的操作,直到所有数据都是有序的状态为止。

照这样的形容我们不难写出快排的代码,我平常遇到排序的问题,只需数据量上了100,想都不想就用快排来处理,但是当我用下面这个程序测试时却出现了问题,大家有想要一起交流的小伙伴可以加群:466572167,下面我们来看看代码:

#include <stdio.h>

#include <time.h>

#include <stdlib.h>

#define NUM 10000000????/*待排序的数据量*/

void quick_sort(double a[], long left, long right);

int main(void)

{

????clock_t t_s, t_e;

????long i;

????double a[NUM];

????srand(time(NULL));

????for (i = 0; i < NUM; ++i) {

????????a[i] = rand();

????}

????t_s = clock();

????quick_sort(a, 0, NUM-1);

????t_e = clock();

????double t = (t_e – t_s) / (double)CLOCKS_PER_SEC;??/*计算排序用时*/

????printf(“Quick sort %d items used time:%f s\n”, NUM, t);

????return 0;

}

void quick_sort(double a[], long left, long right)

{

????long i = left;

????long j = right;

????double mid = a[(i + j) / 2]; /*以中间元素作为比较的基准*/

????while (i <= j) {

????????while (a[i] < mid)

????????????++i;

????????while (mid < a[j])

????????????–j;

????????if (i <= j) {

????????????double t = a[i];

????????????a[i] = a[j];

????????????a[j] =t;

????????????++i;

????????????–j;

????????}

????}

????if (i < right) quick_sort(a, i, right);

????if (left < j) quick_sort(a, left, j);

}

我在Linux上运行这个程序出现了”Segmentation fault “错误,而当NUM==1000000时却没有这个错误。查阅相关资料得知这是因为程序递归次数太多,大量的压栈使程序占用的栈空间超过了操作系统所规定的大小,从而出现的内存错误。

我用ulimit -s指令的得到的结果是8192,也就是说我的系统默认给每个程序分配的大概是8M的栈空间。用指令ulimit -s unlimited使栈空间变成实际内存大小后,上面的程序即可以顺利运行而不出错误了(由于Linux上不像Windows可以把栈的大小写入可执行文件中,所以只能用ulimit -s更改的方法了)。

难道由于栈的限制,快速排序能够解决的数据量就有上限了吗?那还不如用选择排序——尽管慢,但至少不会出错。其实说是“非递归”,只不过是用自己管理的栈来消除递归,算法本质上没有区别,而且从这篇文章作者的测试来看,用栈的方法比用递归的方法反而更慢(作者将其解释为:“用栈的效率比递归高,但是在这个程序中局部变量也就是要每次压栈的数据很少,栈的优势表现不出来,反而更慢……”,我认为这种观点是不对的,因为递归可以了解为有了一个“系统帮你自动管理的栈”,它的效率一定是要比你自己管理的栈要高的,况且你在进行弹栈和压栈操作时又调用了新函数,算上调用的开支,用栈的方法一定比递归慢),不过栈在这里的优势是可以不用考虑操作系统的问题,而且能够解决的数据量只和内存大小有关,不必受到操作系统对栈空间大小的限制(即便用栈,快排也比很多排序算法要快得多)。

以前在学排序算法的时候,专门有讲怎么根据实际问题来选择合适的排序算法,但是我图“省事”,就只用快排和简单选择排序。遇到了这个问题也让我对算法的选择和实现上有了更多认识,同时也理解到用栈消除递归在有些场合(比方系统栈空间受限)的重要意义。

前面我说到所谓的“非递归”快速排序算法,不过是用栈来消除了递归,它的运行时间一定比递归算法长,我们不妨来实际实现一下。代码如下:

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define MAX_TOP 10000 /*一个很大的栈*/

#define NUM 500L

/*有关栈的数据结构*/

struct Region {

????long left;

????long right;

};

struct Stack {

????struct Region reg[MAX_TOP+1];

????long top;

};

/*对栈进行操作的函数*/

void init_stack(struct Stack *s);

void push_stack(struct Stack *s, struct Region r);

struct Region pop_stack(struct Stack *s);

int is_stack_empty(struct Stack *s);

/*与排序有关的函数*/

long partition(double a[], long left, long right);????/*划分区间*/

void nr_qsort(double a[], long left, long right);

int main(void)

{

????double a[NUM];????/*待排序数据*/

????clock_t t_s, t_e;

????long i;

????srand(time(NULL));

????for (i = 0; i < NUM; ++i)

????????a[i] = rand() % 1000000;

????/*统计运行时间*/

????t_s = clock();

????nr_qsort(a, 0, NUM-1);

????t_e = clock();

????double t = (t_e – t_s) / (double) CLOCKS_PER_SEC;

????printf(“Non Recursive quick sort %ld items used time: %f s\n”, NUM, t);

????return 0;

}

/*implementation*/

void init_stack(struct Stack *s)

{

????s->top = -1;

}

void push_stack(struct Stack *s, struct Region r)

{

????if (s->top == MAX_TOP) {

????????fprintf(stderr, “Stack overflow!\n”);

????????exit(0);

????}

????s->reg[++s->top] = r;

}

struct Region pop_stack(struct Stack *s)

{

????if (s->top == -1) {

????????fprintf(stderr, “Stack underflow!\n”);

????????exit(0);

????}

????return (s->reg[s->top–]);

}

int is_stack_empty(struct Stack *s)

{

????return (s->top == -1);

}

/*返回划分的区间*/

long partition(double a[], long left, long right)

{

????double base = a[left];????/*以最左边的元素作为比较基准*/

????while (left < right) {

????????while (left < right && a[right] > base)

????????????–right;

????????a[left] = a[right];

????????while (left <right && a[left] < base)

????????????++left;

????????a[right] = a[left];

????}

????a[left] = base;

????return????left;

}

void nr_qsort(double a[], long left, long right)

{

????struct Stack s;

????struct Region region, regionlow, regionhi;

????long p; /*记录划分出的分界点*/

????init_stack(&s);

????region.left = left;

????region.right = right;

????push_stack(&s, region);

????while (!is_stack_empty(&s)) {

????????region = pop_stack(&s);

????????p = partition(a, region.left, region.right);

????????if (p-1 > region.left) {

????????????regionlow.left = region.left;

????????????regionlow.right = p – 1;

????????????push_stack(&s, regionlow);

????????}

????????if (region.right > p + 1) {

????????????regionhi.left = p + 1;

????????????regionhi.right = region.right;

????????????push_stack(&s, regionhi);

????????}

????}

}

在代码的第110行至第122行的while循环中,做的正是用栈消除递归的工作。想想递归的算法中,把划分好的左右区间界限(即left,right)保存到了系统管理的栈中,这里手动把每次划分出来的区间分界保存至栈中,当第113和118行的两个条件不满足时,所在区间的元素都是有序的状态,此时不进行压栈操作而向前返回(即递归的回调)。关于用栈消除递归的算法可以参考关于数据结构的书籍,比方陈锐的《零基础学数据结构》有关栈的那一章就有详情。实际运行两个程序的结果如下:

$ ./nr_qsort??#非递归算法的快排

Non Recursive quick sort 500 items used time: 0.000261 s

$ ./qsort #递归算法的快排

Quick sort 500 items used time:0.000104 s

之所以只用了500个数据,是由于超过1000个数据后,非递归快排的速度就慢的令人难以忍受。下面是另外两次关于递归算法快排的测试:

$ time ./qsort

Quick sort 1000000 items used time:0.289171 s

real????0m0.372s

user????0m0.332s

sys???? 0m0.012s

#下面更改NUM即数据的个数为10000000

$ ./qsort

Segmentation fault #超出栈的大小

$ ulimit -s unlimited #更改栈的大小为不受限

$ time ./qsort

Quick sort 10000000 items used time:3.259025 s #成功进行了排序

real????0m4.044s

user????0m3.740s

sys???? 0m0.172s

这也印证了之前谈到的系统默认限制带来的问题。大家有什么其余问题的小伙伴可以加群:466572167,群内有C语言、算法的资料在研究算法的大佬。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » C++算法:一次快速排序错误引发的思考

发表回复