代码说明
代码是我亲自码的，调试通过的，代码中有算法思想和详细的注释，一目了然。
递归实现版本见我的另一篇blog:https://blog.csdn.net/weixin_39408343/article/details/107083607
项目已经上传到我的github：https://github.com/yisun03/sort
项目中还有另外得九种排序算法的c++实现代码以及其思想。
十种排序算法清代如下(附我的blog链接)： 1 选择排序：https://blog.csdn.net/weixin_39408343/article/details/107063290 2 插入排序：https://blog.csdn.net/weixin_39408343/article/details/107070155 3 冒泡排序：https://blog.csdn.net/weixin_39408343/article/details/107070658 4 希尔排序：https://blog.csdn.net/weixin_39408343/article/details/107071758 5.1 归并排序递归实现：https://blog.csdn.net/weixin_39408343/article/details/107083607 5.2 归并排序非递归实现：https://blog.csdn.net/weixin_39408343/article/details/107084688 6.1 快速排序递归实现：https://blog.csdn.net/weixin_39408343/article/details/107086104 6.2 快速排序非递归实现：https://blog.csdn.net/weixin_39408343/article/details/107087359 7 堆排序：https://blog.csdn.net/weixin_39408343/article/details/107092851 8 计数排序：https://blog.csdn.net/weixin_39408343/article/details/107094547 9 桶排序：https://blog.csdn.net/weixin_39408343/article/details/107113821 10 基数排序：https://blog.csdn.net/weixin_39408343/article/details/107115403术语说明
1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。
2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
3、原地排序：原地排序指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
4、非原地排序：需要利用额外的数组来辅助排序。
5、时间复杂度：一个算法执行所消耗的时间。
6、空间复杂度：运行完一个算法所需的内存大小。
性能分析
时间复杂度：O(n*log(n))
空间复杂度：O(n)
稳定的非原地排序
void sort::merge(std::vector<int> &data, int left, int mid, int right) { // 将有序的两个子序列合并. // 获取两个子序列的第一个元素. int i = left; int j = mid + 1; // 创建临时容器来保存合并结果,同时指定容器大小. std::vector<int> temp; temp.resize(right - left + 1); // 开始合并. int k = 0; while((i <= mid) && (j <= right)) { if(data.at(i) <= data.at(j)) { temp.at(k++) = data.at(i++); } else { // data.at(j) < data.at(i); temp.at(k++) = data.at(j++); } } // 到此为止肯定有一个子序列已经完全放到临时容器里,现在将另子序列的元素放入临时容器. while(i <= mid) { temp.at(k++) = data.at(i++); } while(j <= right) { temp.at(k++) = data.at(j++); } // 最后将临时容器里的元素复制到原容器完成合并. // 切记这里不能直接使用赋值：data = temp; // 因为这是递归操作,如果这样赋值,那么data的长度会变成2(思考一下为什么是2), // 那么后续操作中会导致"std::out_of_range"错误. for(int n = 0; n < k; n++) { data.at(left++) = temp.at(n); } } void sort::sort_merge_non_recursive(std::vector<int> &data) { // 思想： // 归并排序这里不再是直接在原始序列上进行操作; // 归并排序利用的是分而治之的思想,将序列分成两个子序列,将两个子序列排好序后合并为有序的序列; // 而对两个子序列进行排序同样用分而治之,如此递归下去; // 归并分为三步：分,治,合;治是关键,而治又是最简单的,将序列分为只有一个元素的两个子序列后自然变得有序; // 所以归并可以分为两步：将序列一直分成只有一个元素的子序列,然后将这些有序的子序列合并. // 获取序列长度. int length = data.size(); // 开始合并子序列,子序列长度为1,2,4,8....成倍增长(初始子序列长度必须为1,思考为什么). for(int i = 1; i < length; i *= 2) { // 划分子序列. int left = 0; int mid = left + i - 1; int right = mid + i; // 开始合并. // 注意此处while语句的结合条件,思考有什么问题. while(right < length) { // 合并函数和递归实现的合并函数一样. merge(data, left, mid, right); // 更新left,mid,right以合并下一对序列. left = right +1; mid = left + i -1; right = mid + i; } // while条件是有问题的,因为right = mid + i,随意可能出现情况： right < length < right + i; // 这样会导致right后面到length可能有元素被遗漏,没有对他们进行排序,此处要单独处理. if((left < length) && (mid < length)) { merge(data,left,mid,length - 1); } } }
