最近重读CLRS，除了完成各章后面的思考题外(练习题其实早就做了)，打算把书中的各种算法实现一遍。 在写各种排序算法(heap_sort, quick_sort, merge_sort, insert_sort, counting_sort, radix_sort, bucket_sort, shell_sort)过程中，比较郁闷的一点我写的程序不够通用，我把数据类型都默认为int了(C++模板的好处在这时体现出来了)。而C语言库函数qsort是可以支持各种数据类型的。我想知道它是怎么实现的，花了大半天时间把相关代码翻了一遍，写写看法吧。
qsort定义在stdlib/stdlib.h文件中，在stdlib/msort.c，stdlib/qsort.c两个文件中实现。从msort.c中可以看出qsort的实现并不是直接使用quick_sort，在内存比较充足的情况下使用的是merge_sort(应当如此，内存充足就不必在乎非原地排序带来的空间开销了)，内存不足的情况下才调用qsort.c中实现的_qsort()。对msort.c文件的分析可以看这里，由于这篇文章写的很清楚了，我就不多写了，唯一要注意的是msort_with_tmp()使用的是merge sort不是quick sort。
qsort实现中比较好玩的几点：
1. 字节操作和寄存器变量。由于不确定数据的类型，所有的数据都是基于字节+数据的节数处理的。如：交换两个元素的大小(do ... while())这个trick很有意思……)
30 #define SWAP(a, b, size)
31 do
32 {
33 register size_t __size = (size);
34 register char *__a = (a), *__b = (b);
35 do
36 {
37 char __tmp = *__a;
38 *__a++ = *__b;
39 *__b++ = __tmp;
40 } while (--__size > 0);
41 } while (0)
42
2. 宏，为了性能把常用、比较简单的函数都写成宏了。譬如栈操作：
59 #define STACK_SIZE (CHAR_BIT * sizeof(size_t))
60 #define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
61 #define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi)))
62 #define STACK_NOT_EMPTY (stack < top)
3. 当数组元素不多于4个时，直接使用插入排序。 主元素的选择使用median-three的方法，在选取最低位，中间位，最高位三个元素，将它们的中位数作为主元素放在数组中间，较小元素放在数组最低位，较大元素放在数组最高位，这样这两个元素就不需要参与划分了。这段代码在行121-131。
4. 数组划分使用的是双向扫描，简单来说是：用两个指针，一个从数组开始扫描，指向不小于主元的元素；另一个指针从数组末开始扫描，只想不大于主元的元素，然后交换两个元素。当第一个指针大于等于第一个指针时，划分完毕。 这段代码在行139-164
5. _qsort()的实现是非递归的，用循环+栈代替递归。可能会怀疑用栈是否会带来较大的空间开销，但注意栈中只需要记录需要进一步处理的元素的在原数组中的上下界即可。另一方面，在快排
每次划分后，较小那部分数据继续循环处理，把较大部分数据的上下界压入栈中等待后续处理；这样栈的大小是lg(n)，n是待排序的元素的数目，可以看出栈的空间消耗是很小的。
View Code
110: while (STACK_NOT_EMPTY)
111: {
112: char *left_ptr;
113: char *right_ptr;
114:
115: /* Select median value from among LO, MID, and HI. Rearrange
116: LO and HI so the three values are sorted. This lowers the
117: probability of picking a pathological pivot value and
118: skips a comparison for both the LEFT_PTR and RIGHT_PTR in
119: the while loops. */
120:
121: char *mid = lo + size * ((hi - lo) / size >> 1);
122:
123: if ((*cmp) ((void *) mid, (void *) lo) < 0)
124: SWAP (mid, lo, size);
125: if ((*cmp) ((void *) hi, (void *) mid) < 0)
126: SWAP (mid, hi, size);
127: else
128: goto jump_over;
129: if ((*cmp) ((void *) mid, (void *) lo) < 0)
130: SWAP (mid, lo, size);
131: jump_over:;
132:
133: left_ptr = lo + size;
134: right_ptr = hi - size;
135:
136: /* Here's the famous ``collapse the walls'' section of quicksort.
137: Gotta like those tight inner loops! They are the main reason
138: that this algorithm runs much faster than others. */
139: do
140: {
141: while ((*cmp) ((void *) left_ptr, (void *) mid) < 0)
142: left_ptr += size;
143:
144: while ((*cmp) ((void *) mid, (void *) right_ptr) < 0)
145: right_ptr -= size;
146:
147: if (left_ptr < right_ptr)
148: {
149: SWAP (left_ptr, right_ptr, size);
150: if (mid == left_ptr)
151: mid = right_ptr;
152: else if (mid == right_ptr)
153: mid = left_ptr;
154: left_ptr += size;
155: right_ptr -= size;
156: }
157: else if (left_ptr == right_ptr)
158: {
159: left_ptr += size;
160: right_ptr -= size;
161: break;
162: }
163: }
164: while (left_ptr <= right_ptr);
165:
166: /* Set up pointers for next iteration. First determine whether
167: left and right partitions are below the threshold size. If so,
168: ignore one or both. Otherwise, push the larger partition's
169: bounds on the stack and continue sorting the smaller one. */
170:
171: if ((size_t) (right_ptr - lo) <= max_thresh)
172: {
173: if ((size_t) (hi - left_ptr) <= max_thresh)
174: /* Ignore both small partitions. */
175: POP (lo, hi);
176: else
177: /* Ignore small left partition. */
178: lo = left_ptr;
179: }
180: else if ((size_t) (hi - left_ptr) <= max_thresh)
181: /* Ignore small right partition. */
182: hi = right_ptr;
183: else if ((right_ptr - lo) > (hi - left_ptr))
184: {
185: /* Push larger left partition indices. */
186: PUSH (lo, right_ptr);
187: lo = left_ptr;
188: }
189: else
190: {
191: /* Push larger right partition indices. */
192: PUSH (left_ptr, hi);
193: hi = right_ptr;
194: }
6. 插入排序中的元素交换是用位交换完成的。简单来说，设有a, b, c, d四个元素，现在要将d插到a前(a, b,c以排序)，则先保存d的最后一位，然后分别将c, b, a的最后一位移到后一个元素的最后一位，最后将保存的d的最后一位放在a的最后一位；其他各位也按照这个方法处理。这段代码在行226-249.
226 while ((run_ptr += size) <= end_ptr)
227 {
228 tmp_ptr = run_ptr - size;
229 while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
230 tmp_ptr -= size;
231
232 tmp_ptr += size;
233 if (tmp_ptr != run_ptr)
234 {
235 char *trav;
236
237 trav = run_ptr + size;
238 while (--trav >= run_ptr)
239 {
240 char c = *trav;
241 char *hi, *lo;
242
243 for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
244 *hi = *lo;
245 *hi = c;
246 }
247 }
248 }
249 }
ps: qsort.c文件中代码其实很好读，注释也相当完善。
原文链接: https://www.cnblogs.com/meteorgan/archive/2012/03/10/2389393.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/43897
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
