本文目录
- 希尔排序过程
- 希尔排序方法
- 希尔排序时间复杂度O(n¹.³)中的1.3是怎么来的
- 什么是希尔排序法
- 什么是希尔排序
- 希尔排序的详解
- 希尔排序究竟是怎么排的
- 希尔排序法特点
- 希尔排序算法
- 希尔排序怎么排啊
希尔排序过程
既然议论纷纷我就说下我得见解
｛9,38,65,36,76,13,27,49,11,4｝一共10个数，一般取10/2=5为增量
分为5个组：(s1,s6),(s2,s7),(s3,s8),(s4,s9),(s5,s10)
其中每一组中分别进行比较大小，左边大于右边的就互换，反之不变
如图
那么增量为5的排序结果为：9 27 49 11 4 13 38 65 36 76
其他趟分别使增量减1进行比较，直到全部集中在一组就行了，不赘述了
希尔排序方法
希尔排序是插入排序的一种。基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2《d1重复上述的分组和排序，直至所取的增量dt=1(dt《dt-l《…《d2《d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
希尔排序时间复杂度O(n¹.³)中的1.3是怎么来的
1、首先希尔排序是一种递减增量的排序算法，下面使用大小为9的数组：54、26、93、17、31、44、55、20。
2、令数据间隔为3，将该数组分成三个子数组，如下图所示，为下图中灰色的部分。
3、对每一个子数组都进行插入排序操作，将排序好的子数组合并到一个数组当中。这个时候，会发现，每个数字都会务必接近他应该存在的位置。
4、这是间隔为3的子数组排序后的结果，发现该排序后的数列非常接近我们需要的递减或者递增序列。下一步只需要，缩小间隔进行重复性操作即可
5、最后改变间隔，使间隔变成4，这个时候子数组反而有4组。这个说明希尔排序（shell sort）是一个不稳定的排序。
什么是希尔排序法
基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。序列分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。增量序列一般采用：ht=2t-1,1≤t≤[log2n]，其中n为待排序序列的长度。-----代码:void prshl(p,n) int n;double p; { int k,j,i; double t; k=n/2; while(k》0) { for(j=k;j《=n-1;j++) { t=p[j];i=j-k; while((i》=0)&&(p[i]》t)) { p[i+k]=p[i];i=i-k; } p[i+k]=t; } k=k/2; } return; }
什么是希尔排序
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。希尔排序基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成（n除以d1）个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2《d1重复上述的分组和排序，直至所取的增量dt=1(dt《dt-l《…《d2《d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。给定实例的shell排序的排序过程假设待排序文件有10个记录，其关键字分别是：49，38，65，97，76，13，27，49，55，04。增量序列的取值依次为：5，3，1
希尔排序的详解
希尔排序基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2《d1重复上述的分组和排序，直至所取的增量dt=1(dt《dt-l《…《d2《d1)，即所有记录放在同一组中进行直接插入排序为止。
举例说明：
对于这样一个无序的数组5 9 3 2 6 11 8 1 7 4 10 ，想把它变成顺序递增的数组1 2 3 4 5 6 7 8 9 10 11。先隔3个元素取一次：把5 2 8 4取了出来，往后搓一位，把9 6 1 10取出来，再往后搓一位，又把3 11 7取出来。分别对这三个小组排序成为递增的序列，再插回去，如图：
于是得到了第一趟排序的结果：2 1 3 4 6 7 5 9 11 8 10.现在再以2为间隔重复以上步骤（这次得到的是两个小组）得到了2 1 3 4 5 7 6 8 11 9 10。最后再以1为间隔再搞一次（实际上这一步就是从左到右两两比较，调整位置），就得到了想要的结果。
这就是希尔排序，其要义就是先进行宏观调整，再进行微观调整。
希尔排序究竟是怎么排的
希尔排序的算法思想 先将整个待排序元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的），分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。 希尔排序算法 void ShellInsert(SqList &L,int dk) {//对顺序表L作一趟希尔排序 for(i = 2; i 《= L.ength; i++) if (L.r[i].key 《 L.r[i-1].key) { L.r = L.r[i]; L.r[i] = L.[i-1]; for(j = i - 2; L.r.key 《 L.r[j].key]; j--) L.r[j+1] = L.r[j]; L.r[j+1] = L.r; }//if } //ShellInsertSort void ShellInsert(SqList &L,int dk) {//对顺序表L作一趟希尔排序 ...... } //ShellInsertSort void ShellSort(SqList &L,int dlta,int t) { //按增量序列dlta[0..t-1]进行希尔排序 for(k = 0; k 《 t; k++) ShellInsert(L,dlta[k]); //一趟增量为dlta[k]的希尔排序 } //ShellInsertSort
希尔排序法特点
1.3希尔排序特点·一次移动，移动位置较大，跳跃式地接近排序后的最终位置·最后一次只需要少量移动·增量序列必须递减的，最后一个必须是1·增量序列应该是互质的1.4希尔排序算法主程序：子函数： 上面代码中i=0处存储了哨兵，所以真正的序列是从1开始的，因此i是从增量+1开始的。 在希尔排序的理解时，我们倾向于对于每一个分组，逐组进行处理，但在代码实现中，我们可以不用这么按部就班地处理完一组再调转回来处理下一组（这样还得加个for循环去处理分组）。比如[5,4,3,2,1,0] ，首次增量设gap=length/2=3,则为3组[5,2] [4,1] [3,0]，实现时不用循环按组处理，我们可以从第gap个元素开始，逐个跨组处理。同时，在插入数据时，可以采用元素交换法寻找最终位置，也可以采用数组元素移动法寻觅。 在写代码时，我们从下标为第一个增量值处开始，进行跨组处理，而不是一组一组处理，如果要一组一组处理，则需要额外增加一个for循环，这样增加了算法的复杂度。例如，初始序列如下（无哨兵，故初始序列的下标从0开始，则i=增量）： 若取增量为4，则分组结果为：{5，1，2}、{3，6}、{7，4}，{9，8}按照理解希尔排序的思路，我们应该先将{5，1，2}排好序后，再排{3，6}……但是这样做我们需要给整个程序加一个用于分组处理的for循环，增加了算法复杂度。因此我们这样考虑：从下标4处开始，减一个增量，先将这2个数排好序，然后继续往后跨组移动排序，接下来下标为5，那么我们减一个增量，继续排序……这样我们一直进行到整个序列的最后一个元素，此时我们就已经将所有的数排好序了。那么此时或许有一个疑问，这样做每次只交换了2个数，可是对于分组中有大于3个数的组，程序是怎么解决的呢？ 比如说{5，1，2}，第一次时我们对5和1进行了排序，接下来我们跨组依次往后排序，此时到了2这个元素，那么我们用2减去增量，又到了5那个位置，将这2个数排好序，然后我们利用for循环再继续减增量，对这2个数再继续排序，，一直到减增量后的值小于0为终止条件，说明此时2以及2之前的5和1，这3个数已经彻底排好了序，如果说序列再足够长，等到有一个数减去增量后又等于2，那么再利用for循环对这4个数再依次进行排序。程序如下：1.5希尔排序算法分析 希尔排序算法效率增量序列的取值有关： ·Hibbard增量序列 ·