代码说明
代码是我亲自码的，调试通过的，代码中有算法思想和详细的注释，一目了然。
非递归实现版本见我的另一篇blog:https://blog.csdn.net/weixin_39408343/article/details/107084688
项目已经上传到我的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::sort_merge_recursive(std::vector<int> &data, int left, int right) { // 思想： // 归并排序这里不再是直接在原始序列上进行操作; // 归并排序利用的是分而治之的思想,将序列分成两个子序列,将两个子序列排好序后合并为有序的序列; // 而对两个子序列进行排序同样用分而治之,如此递归下去; // 归并分为三步：分,治,合;治是关键,而治又是最简单的,将序列分为只有一个元素的两个子序列后自然变得有序; // 所以归并可以分为两步：将序列一直分成只有一个元素的子序列,然后将这些有序的子序列合并. if(left < right) { // 将序列一分为二并获取中间位置. int mid = (left + right)/2; // 递归处理两个子序列使之有序. sort_merge_recursive(data, left, mid); sort_merge_recursive(data, mid + 1, right); // 合并两个有序子序列后结束归并排序. merge(data, left, mid, right); } } 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); } }
