一, 背景
睡前忽然想写两行代码练练手, 想起快速排序的一种变种实现, 于是写了快速排序, 在理论上完全没问题的情况下测试结果却很诡异, debug 半天发现是宏定义导致, 作为经验教训记录下来.
二, 快速排序变种实现
原理:
- |_| |_| |_________________________________________|
- L R unSorted
- ---------------------------------------------------------------------------------------------------------------------
1, 取哨兵下标为 low, 即首元素; 初始状态 L 和 R 集合都为空, L 集合用来存放小于 pivot 的值, R 集合用于存放大于 pivot 的值.
pivot = vector<T>& vec[low] ; mi = low;
↓mi
- |--|
- |_| |_| |_________________________________________|
- L R unSorted
2, 遍历初始集合, 如果发现当前下标元素值大于 pivot 则迭代器加 1, 不做任何操作, 效果相当于移动元素到 R 中.
- idx
- |_| |__| |________________________________________|
- L R unSorted
3, 如果发现当前下标元素值小于 pivot 则需要将当前值放于集合 L 中, 为了提升效率, 使当前元素和 R 集合的首元素交换, 然后迭代器加 1; 作用效果相当于 L 元素新增, R 元素整体后移一位.
mi
↓ idx
- |__| |__| |_______________________________________|
- L R unSorted
4, 当遍历完当前序列后 unSorted 的将为空, L 和 R 将包含所有小于 / 大于 pivot 元素的集合.
mi
↓
- |___________________| |_________________________|
- L R
5, 最终将首元素, 即 pivot 和 mi 所指的元素交换, 左右效果是 mi 这个选出来的哨兵节点已经就位, 完成了一趟排序, 之后将调用递归的方式对前半段和后半段进行排序 (和大家所熟知的快排一致).
三, 具体实现, 以下代码中 swap 函数用宏定义实现, 为了逻辑紧凑, 在 swap 的参数中用了 "++" 操作符.
1, 排序逻辑
- #ifndef __ALGO_SORT_QUICK_SORT_IMPROVED_H__
- #define __ALGO_SORT_QUICK_SORT_IMPROVED_H__
- #include <vector>
- #include <iostream>
- using namespace std;
- #define swap(a, b) ({ 9 typeof(a) tmp = (a) ; 10 (a) = (b); 11 (b) = tmp; })
- template<typename Type>
- static int partion(std::vector<Type>& elems, int low, int high)
- {
- Type pivot = elems[low];
- int mi = low;
- for (int i = low + 1; i <= high; i++)
- {
- if (elems[i] <pivot)
- {
- //++mi;
- swap(elems[++mi], elems[i]);
- }
- }
- swap(elems[mi], elems[low]);
- return mi;
- }
- template<typename Type>
- void quick_sort_improved(std::vector<Type>& elems, int low, int high)
- {
- if (low <high)
- {
- int mi = partion(elems, low, high);
- quick_sort_improved(elems, low, mi - 1);
- quick_sort_improved(elems, mi + 1, high);
- }
- }
- #endif
2, 测试程序
- vector<double> nums{18.1,16.12,32.21,12.22,13.1,53.21,221.5,354,123,42,22.11,33};
- quick_sort_improved<double>(nums, 0, nums.size() - 1);
- for (int i = 0; i <nums.size(); i++ )
- {
- cout << nums[i] << " ";
- }
- cout << endl;
3, 测试输出
- [email protected]:~/workspace/Algo/src/sort/insertSort$ ./a.out
- 6.52013e-319 6.52013e-319 6.52013e-319 12.22 12.22 16.12 33 0 0 0 42 42
4, 分析: 由上结果可知, 测试结果并未按照预期输出, 乱七八糟的.
四, 修复版
加了诸多 debug 信息, 得知问题出在使用宏定义的过程中传入了 ++ 操作符, 熟悉宏定义的人肯定遇到过类似问题; 当前问题是: 宏定义中表达式出现几次,++ 将会被调用几次, 这当然不是期望的结果; 知道原因后稍加修改.
- template<typename Type>
- static int partion(std::vector<Type>& elems, int low, int high)
- {
- Type pivot = elems[low];
- int mi = low;
- for (int i = low + 1; i <= high; i++)
- {
- if (elems[i] < pivot)
- {
- ++mi;
- swap(elems[mi], elems[i]);
- }
- }
- swap(elems[mi], elems[low]);
- return mi;
- }
测试输出: 正确, 符合预期
- [email protected]:~/workspace/Algo/src/sort/insertSort$ ./a.out
- 12.22 13.1 16.12 18.1 22.11 32.21 33 42 53.21 123 221.5 354
五, 总结
日常代码中宏定义有时候无法避免, 就像上面用到的 swap, 即便实现上已经避免了很多低级错误; 但宏定义依然有很多不尽人意之处, 就像上面的使用, 编译器甚至都不会给个警告, 在运行期也可以正常运行, 但结果通却是莫名其妙的错误; 通过一番折腾找出原因所在, 以后在使用宏定义的地方一定要避免这种操作.
来源: http://www.bubuko.com/infodetail-3357075.html