代码说明
代码是我亲自码的，调试通过的，代码中有算法思想和详细的注释，一目了然。
项目已经上传到我的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(1)
非稳定的原地排序
void sort::sort_shell(std::vector<int> &data) { // 思想： // 还是在原待排序序列上进行操作; // 该算法是插入排序的变种和优化,当无序序列不理想,简单的插入排序会有很多的交换操作,影响效率; // 希尔排序做的改进是将原始待排序序列以一个偏移量h进行逻辑上的分组,对组内的元素采用插入排序,使得原始序列基本有序; // 偏移量逐渐减小,每减小一次进行组内插入排序,最后一轮则以1为偏移量,也就是将原书待排序列分为同一组进行组内排序,也就是简单的插入排序; // 该排序算法对于无序序列很不理想的情况有利. // 注：一般将h初始值设为length/2,h逐倍递减直至1,其实还有更理性的分组方法,对最终效率也有所优化. // 对于分组方法,可以戳链接：https://mp.weixin.qq.com/s/4kJdzLB7qO1sES2FEW0Low int length = data.size(); if(length < 2) { return; } // 组内排序,注意排序方法是对各个分组进行交替排序. for(int h = length/2; h > 0; h /= 2) { // 对偏移量为h的分组交替进行插入排序. // i = h是第一组的第二个元素,仔细想想. for(int i = h; i < length; i++) { insert_i(data,h,i); } } } void sort::insert_i(std::vector<int> &data, int h, int i) { // 该部分代码其实就是插入排序的代码. // 将第i个元素插入到以h为偏移量分的组的有序区的适当位置. int temp = data.at(i); int k; for(k = i - h; k >= 0 && data.at(k) > temp; k -= h) { // 腾出插入位置. data.at(k+h) = data.at(k); } // 已找到要插入的位置为k+h,插入. data.at(k+h) = temp; }
