希尔排序的有序性证明

数据结构 希尔排序 的证明~

希尔排序的一个特性：设k < h，则h-sorted的数组经过希尔排序k-sort后还是h-sorted的。
我觉得用归纳法证明。先把数组看成h列的一个二维数组，则h-sorted的数组就是各列上排好序的数组。

数组中所有元素分成k条不同的链（元素在一维数组中的下标除以k得到的余数决定它在第几条链中），我们假想希尔排序的次序是所有链并行进行第一次插入排序，然后所有链并行进行第二次插入排序……直到所有链内排好序（k-sorted）。注意这里排序的结果和希尔排序结果必然是一致的。

对这个假想的排序过程的轮数进行归纳法论证。分三步：
第n = 0轮时，数组是h-sorted（所给条件即是，不需要证明）。
假设n = k轮时，数组是h-sorted，则n = k + 1轮时，数组是h-sorted。
有归纳法可知，对任意自然数n，n轮后数组是h-sorted。

所以关键是证明第2步。大概思路如下，我们用反证法，假设第一次h-sorted被违背是发生在某一轮内的各列上某一次插入排序比较/交换操作后，存在A[m] > A[m + p*h]（某一列上发生了违背h-sorted的情况）。则要么A[m + p*h]的值是从它所在链的后面被交换上来的，否则如果A[m + p*h]位置未发生交换，则A[m]只可能会被它所在链后面更小的值所替代，假设不能成立。这里对于A[m]位置上是否发生了交换有两种可能，但证明过程基本一样，所以我们只假设A[m]位置上已经排好了序（无论是否交换过），即A[m] <= A[n]。

假设A[m + p*h]是被A[n + p*h]替换的（n > m，且n - m是k的整数倍，因为插入排序发生在各链之内）， 则我们观察这四个位置：A[m], A[m + p*h], A[n], A[n + p*h]。

由于插入排序开始前根据假设各列是h-sorted，则A[n] A[n + p*h] >= A[n]。

所以我们得到了A[m] > A[n]。这跟我们假设A[m]和A[n]这两个位置已经排好了序矛盾，所以假设不成立。原题得证。

如果你觉得上面的证明过程费解，那你需要在草稿纸上画一画，主要是A[m], A[m + p*h], A[n], A[n + p*h]这四个位置。前两个在同一列上，后两个在同一列上。

希尔排序基本思想：先取一个小于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为间隔再搞一次（实际上这一步就是从左到右两两比较，调整位置），就得到了想要的结果。
这就是希尔排序，其要义就是先进行宏观调整，再进行微观调整。

希尔排序的一个特性：设k < h，则h-sorted的数组经过希尔排序k-sort后还是h-sorted的。

我觉得用归纳法证明。先把数组看成h列的一个二维数组，则h-sorted的数组就是各列上排好序的数组。

数组中所有元素分成k条不同的链（元素在一维数组中的下标除以k得到的余数决定它在第几条链中），我们假想希尔排序的次序是所有链并行进行第一次插入排序，然后所有链并行进行第二次插入排序……直到所有链内排好序（k-sorted）。注意这里排序的结果和希尔排序结果必然是一致的。

对这个假想的排序过程的轮数进行归纳法论证。分三步：

第n = 0轮时，数组是h-sorted（所给条件即是，不需要证明）。
假设n = k轮时，数组是h-sorted，则n = k + 1轮时，数组是h-sorted。
有归纳法可知，对任意自然数n，n轮后数组是h-sorted。

所以关键是证明第2步。大概思路如下，我们用反证法，假设第一次h-sorted被违背是发生在某一轮内的各列上某一次插入排序比较/交换操作后，存在A[m] > A[m + p*h]（某一列上发生了违背h-sorted的情况）。则要么A[m + p*h]的值是从它所在链的后面被交换上来的，否则如果A[m + p*h]位置未发生交换，则A[m]只可能会被它所在链后面更小的值所替代，假设不能成立。这里对于A[m]位置上是否发生了交换有两种可能，但证明过程基本一样，所以我们只假设A[m]位置上已经排好了序（无论是否交换过），即A[m] <= A[n]。

假设A[m + p*h]是被A[n + p*h]替换的（n > m，且n - m是k的整数倍，因为插入排序发生在各链之内）， 则我们观察这四个位置：A[m], A[m + p*h], A[n], A[n + p*h]。

由于插入排序开始前根据假设各列是h-sorted，则A[n] <= A[n + p*h]必然成立。由于A[m]和A[n]的距离必然等于A[m + p*h]和A[n + p*h]之间的距离，则各列并行进行插入排序时，A[m + p*h]和A[n + p*h]进行比较/交换时，A[m]和A[n]也在进行比较交换。根据前面的推理，在当前插入排序交换之前，我们有A[m] > A[n + p*h] >= A[n]。

所以我们得到了A[m] > A[n]。这跟我们假设A[m]和A[n]这两个位置已经排好了序矛盾，所以假设不成立。原题得证。

如果你觉得上面的证明过程费解，那你需要在草稿纸上画一画，主要是A[m], A[m + p*h], A[n], A[n + p*h]这四个位置。前两个在同一列上，后两个在同一列上。

---

元宝山区17796712835： 数据结构 希尔排序 的证明 - ？
松芝加味： program xzpx; const n=7; var a:array[1..n] of integer; i,j,k,t:integer; begin write('Enter date:'); for i:= 1 to n do read(a); writeln; for i:=1 to n-1 do begin k:=i; for j:=i+1 to n do if a[j] if ki then begin t:=a;a:=a[k];a[k]:=t;end; end; write('output data:'); for i:= 1 to n do write(a:6); writeln; end.

元宝山区17796712835： 希尔排序法原理?? - ？
松芝加味： 希尔排序法(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序的方法.算法思想简单描述 在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,并且对插入下一个数没有提供任何帮助....

元宝山区17796712835： 希尔排序算法证明？
松芝加味： 希尔排序:* 不需要大量的辅助空间,和归并排序一样容易实现.希尔排序是基于插入排序的一种算法,* 在此算法基础之上增加了一个新的特性,提高了效率.希尔排序的时间复杂度为 O(N*(logN)2),* 没有快速排序算法快 O(N*(logN)),因...

元宝山区17796712835： 希尔排序的希尔分析 - ？
松芝加味： 希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高.所以,希尔排序的时间复杂度会比o(n^2)好一些.

元宝山区17796712835： 奇数个数字如何用希尔排序法排序 - ？
松芝加味： 1. 希尔排序与元素个数的奇偶性无关,5个元素,先取步长为2,再取步长为1即可. 2. 希尔排序只要保证最终一趟的步长为1即可保证整个序列有序.其他步长的排序趟数只是为了降低比较和移动数据的次数 3. 如果只做一趟希尔排序,则其会直接退化为普通的插入排序. 第一点就是说明如何排序了,下面说明下详细过程: 先取步长2进行插入排序得到序列: (1,2,4,6,5) 注:步长2将其中的序列分为了(4,5,1)和(2,6)两个序列,经过插入排序后 得到(1,4,5)和(2,6) 再取步长1进行插入排序得: (1,2,4,5,6)

元宝山区17796712835： 关于数据结构,希尔排序的一个问题!那个有增量必须是奇数吗?图中书上给的增量分别是1,3,5.而下面 - ？
松芝加味： 希尔排序的原理是每次对无序序列中的数隔d(增量)进行排序,这样,对着增量的减小,序列也会越来越有序,当增量减小到1时,序列也就成有序状态了.增量不一定是奇数,事实上,增量数组的选取是一个有很深入学问的事情,一个好的增量数组,可以使算法效率达到最快,这与数据的数量和混乱程度有关,然而,只要一个数组是递减的,并且最后一个值是1,都可以作为增量数组使用,并且也能完成排序工作,但是效率上可能就低一点了,也就是说算法的复杂度要升高.对于数据结构这门课,我大学的时候也曾经修过,好像没有要求掌握增联数组的算法,所以你可以放心了,考试的时候一般会给,你不放心的话可以问问老师.

元宝山区17796712835： 为什么希尔排序不把增量直接设置为1啊? - ？
松芝加味： 希尔排序的思想是让数组里面任意间隔为h的元素都是有序的,也就是h个相互独立的数组组合在一起.我们要做的就是逐渐的缩小h,让他部分有序,直至全部有序.你所说的增量设置为1是插入排序,插入排序最大的弊端就是太依赖于要排序数组的有序性,排序数组越有序,他排序时间越短,越无序时间越长.希尔排序是他的升级版,希尔排序先让数组部分有序,最后再将h设为1,从而实现全部有序.他权衡了数组的规模性还有有序性,对大型数组,任意排列的数组表现都很好.

元宝山区17796712835： 希尔排序的的思想是什么?(例证) - ？
松芝加味： 希尔排序基本思想 基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数的记录放在同一个组中.先在各组内进行直接插人排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的...

元宝山区17796712835： 希尔排序究竟是怎么排的? - ？
松芝加味： 希尔排序的算法思想 先将整个待排序元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的),分别进行直接插入排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序. 希尔排序算...

元宝山区17796712835： 希尔排序的排序过程 - ？
松芝加味： 希尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序. 排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1,...