八大排序算法~希尔排序【改良版的直接插入排序】
直接插入排序文章：https://www.cnblogs.com/shan333/p/15043607.html
✿●✿希尔排序思想由来~先思考直接插入排序在什么情况下效率比较高？
希尔排序思想： 先将整体待排记录序列分割成若干个子序列，分别进行直接插入排序， 待整个序列中的记录“基本有序”时，再对全体进行一次直接插入排序。
1，为什么需要改良直接插入排序，以及改良后的希尔排序实现了什么效果？
希尔排序：对直接插入排序的改良版，原来的直接排序面对大量数的效率太低了，需要先对待排序数据进行处理，
（希尔排序就是通过取一定间隔进行数据处理，
使得小的数基本在前边，大的数基本在后边，使得整体的数字看起来是基本有序的 ）
2，如何实现希尔排序?
（1）希尔排序通过取某个“间隔”对原整体的数据进行分组
【不断以 某间隔划分有序区跟无序区，然后遍历无序区数据，跟有序区数据比较，找合适位置】。然后这个“间隔”缩小，再分组；“间隔”再缩小，再分组…直到“间隔”为1，进行最后的分组就是数据本身的整体了。（间隔的取值是整体数据的一半，即d=n/2）
（2）然后小组内部需要直接排序
(3)图解：引自《数据结构c语言版严蔚敏PPT.pdf ~
https://wenku.baidu.com/view/9e73cb8b69dc5022aaea00c1.html》
3，代码逻辑分析：
第一层循环（间隔循环地缩小，直到间隔为1）：for(int i = n/2; i >=1; i = i/2) 外循环（不断地取出无序区的数）：for(j = 1 + i; j <=n; j++) ~1+i 无序区离有序区的距离是i，初始时，有序区只在第一个位置 内循环（取出的数不断地与有序区做比较，找到一个合适位置插入）：for(k = j – i; r[0] < r [k] && k > 0; k = k – i) ~有序区离无序区的距离是i，无序区第一个数距离i前就是有序区的最后一个数
4，直接上代码，分析如上：
for(int i = n/2; i >=1; i = i/2){ for(j = 1 + i; j <=n; j++){ arr[0] = arr[j]; //哨兵元素，作用：可以不用再添加额外的辅助空间；省去对数组下标越界的判断 for(k = j – i; arr[0] < arr [k] && k > 0; k = k – i){ //边比较，边移动数组空间 arr[k + i] = arr[k]; } arr[k + i] = arr[0]; } }
