希爾排序的總結2

昨天手寫希爾排序的時候總是失敗，是以再次總結一下希爾排序。希爾排序是對直接插入排序的更新，表現在每一個分組(相隔相同增量的元素)都是使用的直接插入排序，隻不過希爾排序中不在是j--而是j=-increment，控制循環次數的外for的初始值不是i=1，而是

increment = n;           

i=increment+1；           

increment=increment/k+1；           

;這裡的k即相隔量。這裡好久沒想明白，若increment正好被k整除這裡就和直接插入排序的初始值一樣。若不能被整除，餘數有可能是1~k-1，此時increment的取值範圍為2~K，所有的可能值就變為1~k。個人認為這是保證i的取值能周遊到這個分組的每一個元素。即開始的位置包含了一個分組的所有可能性。從代碼中分析：

do{
			increment = increment/3+1;

			for(i=increment+1;i<a.length;i++){
					if(a[i]<a[i-increment]){
					a[0] = a[i];
						for(j=i-increment;j>0&&a[j]>a[0];j-=increment){
							if(a[j]>a[0]){
								a[j+increment] = a[j];
							}
						}//for
					a[j+increment] = a[0];
				}
				
			}
		}
		while(increment>1);<pre name="code" class="java">for(i=1;i<a.length;i++){
			j = i-1;
			temp = a[i];

			while(j>=0 && temp<a[j]){
				a[j+1] = a[j];//本質上是元素後移，原因是a[i]比前面的元素小，要為它留出一個空間
				j--;
			}

			a[j+1] = temp;
		}           

可以看出兩者的差別，即j的增量由1變成了increment，i的增量還是1.隻不過這裡的j的增量是可以變化的。但是再去驗證手寫的代碼的正确性的時候我寫的代碼是這樣的：

do{
			increment = increment/3+1;

			for(i=increment+1;i<a.length;i++){
					if(a[i]<a[i-increment]){
					a[0] = a[i];
						for(j=i-increment;j>0;j-=increment){
							if(a[j]>a[0]){
								a[j+increment] = a[j];
							}
						}//for
					a[j+increment] = a[0];
				}
				
			}
		}
		while(increment>1);           

就是少寫了這一個條件  &&a[j]>a[0]

結果就是不正确，于是分别列印每次排序的結果，結果發現這裡的a[0]類似于直接插入排序中哨兵的作用，其實應該就是哨兵。