他日卧龙终得雨
今朝放鹤且冲天
CSDN 请求进入专栏
是否进入《C++专栏》?
确定
排序的概念
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增 或 递减 的排列起来的操作。
排序稳定性
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序
数据元素全部放在内存中的排序。
外部排序
数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
目录
插入排序的概念
直接插入排序
算法思想
算法实现
排序原理
特性总结
希尔排序
算法思想
排序原理
排序原理
算法实现
特性总结
插入排序的概念
插入排序分为两类：直接插入排序、希尔排序
直接插入排序
对于直接插入排序，我想大家都很熟悉，例如我们玩的扑克，洗牌时就运用了直接插入排序
算法思想
把 待排序 的记录按其关键码值的大小 逐个插入 到一个已经排好序的 有序序列 中，直到所有的记录插入完为止，得到一个新的有序序列 。
例如：对于一组将要排序的数据，我们应该从 前往后遍历 ，遍历到的数据我们就与前面排好序的数据进行比较。我们以 升序 为例，若当前数据比前面的数据小就要两者交换，如果再比前面的数据还小就继续进行交换直到数据有序为止，下面呈上动图以便老铁们理解。
当插入第 i (i>=1) 个元素时，前面的 array[0]，array[1] … array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1]，array[i-2] … array[0] 的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移
算法实现
（以升序为例）
void InserSort(int* a, int n) // a数组的首地址，n数组要排序的元素个数 { for (int i = 0; i < n - 1; i++) // 从数组的第一个元素开始遍历无序数据 { int end = i; int tmp = a[end + 1]; // 临时存储待排数据 while (end >= 0) { if (a[end] > tmp) // 待排数据与前面的有序数据进行比较 { a[end + 1] = a[end]; // 待排数据小于有序数据就在合适位置交换 --end; } else { break; } } // 走到这里分两种情况，待排数据比有序数据都大或者都小 a[end + 1] = tmp; // 直接插入就可以了 } }排序原理
在 [0，end] 区间插入 tmp ，先比较 tmp 与 end 的大小关系，如果比 end 小，那么将 end 往后面挪一个，在用 tmp 和 end-1 比较，如果比 end-1 小，再将 end-1 往后挪，直到 tmp 比 [0,end] 区间中那个元素大，那么就停止，如果 tmp 比这个区间的所有数都要小，那么直接将tmp放在第一个位置。
代码测试
特性总结
<1>元素集合越接近有序 直接插入排序算法的时间效率越高 <2>时间复杂度 O(N^2) <3>空间复杂度 O(1) <4>稳定性 它是一种稳定的排序算法
希尔排序
算法思想
希尔排序是对直接插入排序的 优化 ：
若面对这样一组数据 arr[ ] = {9,8,7,6,5,4,3,2,1} 按升序排序，如果使用直接插入排序的话时间复杂度为 O(N^2) ，为了提高代码效率，我们会对原数据 进行预排 ，这就是希尔排序。
排序原理
其实希尔排序就是将数据 分组 ，在每个组内进行 直接插入排序
那么如何分组呢？
设置一个增量序列，开始的增量通常是数组长度的一半，然后下一次增量减半，增量设为gap
假设有一组｛9, 1, 2, 5, 7, 4, 8, 6, 3, 5｝按 升序 排序
N即数组个数：１０
第一趟排序： 设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。接下来，按照直接插入排序的方法对每个组进行排序。第二趟排序： 将上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为2组。按照直接插入排序的方法对每个组进行排序。
第三趟排序： 再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为1的元素组成一组，即只有一组。按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。
注：需要注意一下的是，图中有两个相等数值的元素5和5。我们可以清楚的看到，在排序过程中，两个元素位置交换了。
下面呈上动图以便老铁们理解：
排序原理
希尔排序法又称 缩小增量法 ：
先选定一个整数 gap ，把待排序文件中所有记录分成几个组，所有距离为 gap 的记录分在同一组内，并对每组使用直接插入排序算法排序。然后取重复上述分组和排序的工作。
当 gap 减至 1 时，所有元素在统一组内排好序，算法便终止。
算法实现
void ShellSort(int* a, int n) { int gap = n; while (gap > 1) { gap = gap / 2; for (int i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } } }代码测试
特性总结
<1>当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
<2>希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些树中给出的 希尔排序的时间复杂度都不固定。
时间复杂度情况如下：（n指待排序序列长度）
(1)最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即 O(n)
(2)最坏情况：O(nlog2n)
(3) 渐进时间复杂度（平均时间复杂度）：O(nlog2n)因此希尔排序在效率上较直接插入排序有较大的改进
<3>希尔排序的空间复杂度 O(1) 。
<4>由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是 不稳定 的。