江苏龙网

  1. 首页 > 生活 > >

数据结构与算法分析（C语言描述）中快排的实现是不是有问题啊为啥vs2013编译没报错，但是却没输出呢

楼上说的对啊，你stdafx和tmain什么鬼？怀疑你是怎么学的C语言。。。重学吧骚年。发现写个给新人的vs2013怎么用的教程很是有必要，等我洗澡吃饭回来就发！Visual Studio2013适合新手练习C语言吗？ - 用户的回答
■网友
题主你省略了 Weiss 代码中对数组元素个数小于 `CUTOFF` 时的处理, Weiss 代码逻辑非常缜密, Median3 的作用不光是找出 pivot, 同时还设立了两个哨兵, 然而当数组元素少于 3 的时候 Median3 的机制就不适用了, 结果就是分区过程从右向左搜索元素时会越界.所以 Weiss 用 `CUTOFF` 区分处理了这两种情况, 当然另一个原因是当数组元素个数较少时, 快排的优势反而成了劣势
■网友
首先去掉stdafx.h，入口函数名字改回main，g++ Quick_Sort.cpp -o sort编译能过。./sort提示 Segmentation fault (core dumped) ，数组越界。把维斯的原书下载下来看了快排那一节，书上提供的代码没错，而且对于边缘条件的处理相当精细，在作者的代码中，Median3不但找出当前数组的枢轴，而且使得a \u0026lt;= pivot == a \u0026lt;= a。这样a和a就已经落在了合适的地方，无需参与下面的循环，且可以对i和j起界限作用，避免越界。然而数组只有1个或2个元素时，上述机制就会出问题。作者的意图是如果数组S中元素个数少于cutoff + 1，则使用插入排序，这样可以提高性能并且避开Median3的边缘条件。而你的代码试图对数组递归地进行快排，导致对长度为1和2的数组进行快排时索引越界。解决办法有两个：可以取消Median3函数，改成把当前数组S第一个元素当做pivot，这样就可以纯用快排对数组排序，不过作者不推荐这么做；加上一个CUTOFF，对于小于CUTOFF的数组，用插入排序进行处理，同时避免Median3的副作用，这是作者的做法；基于第2种办法可以对程序做如下补充：#define CUTOFF 3void insert_sort(int* a, int len){ int j; for (j=1; j\u0026lt;len; j++) { int i = j - 1; int key = a; while (a \u0026gt; key \u0026amp;\u0026amp; i \u0026gt;= 0) { a = a; i--; } a = key; }}void QuickSort(int A, int left, int right){ //如果数组中元素个数少于CUTOFF + 1，则使用插排 if (left + CUTOFF \u0026lt;= right) { int pivot = Median3(A, left, right); //现在a\u0026lt;=pivot, a\u0026gt;=pivot, a=pivot int i = left; int j = right - 1; while (1) { while (A \u0026lt; pivot){} while (A \u0026gt; pivot){} if (i \u0026lt; j) swap(A, A); else break; } //现在把pivot放在A上，a将数组分成符合需要的前后两块 swap(A, A); QuickSort(A, left, i - 1); QuickSort(A, i + 1, right); } else insert_sort(A + left, right - left + 1);}基于第一种办法，你可能需要在Quicksort函数里判断待排数组是否只有1或2个元素，比较麻烦；或者放弃Median3取中值函数，直接把a当pivot，这样可以递归到底。
■网友
tmain 我觉得很好啊, 你在vs项目里就改个unicode设置,分分钟切换工程的unicode属性.还让你顺便学学wchar_t 这种非主流的知识.可见微软真是我们程序员的贴心小棉袄. 他预见了很多很好的东西.虽然不标准.但 标准这东西不也是由一帮老古董程序员开会弄出来的吗?举个例子.比如说Opengl 和 directx , gl么就是典型的开放标准.结果每次开会尽是扯皮.进步缓慢.而dx 就是微软一人主导. 后来成了超越gl的标准.所以微软就是先进生产力的代表. 尽管我周围很多gl粉 见了微软就骂.但没用,再眼红你们也是乌龟.总也会被微软兔子甩远!


推荐阅读


上一篇：小型城商银行，面试进去大概有三个职位可以去，分别是软开研发，项目管理，电子银行产品经理。求介绍帮选。

下一篇：网吧有啥好赚钱的附带产业?