Java資料結構 希爾排序

思想

希爾排序的思想是：先選擇一個小于排序資料個數n的整數di(稱為步長，一般為小于n的質數），将間隔di的數為一組，對每組的元素進行直接插入排序，即将需要排序的資料插入到已經排序好的序列中。當步長為1時，完成整個資料的排序。排序的流程為：

1、根據步長的個數，對于每個步長進行分組；

2、對每組進行插入排序，主要操作如下：

1）如果待插入資料比前一個資料小，将該資料存儲到臨時周遊temp中；

2）将前面比他大的資料全部向後移動一位；

3）再将temp的資料插入到最後移動的資料位置；

給你到問題是，将标準輸入的n個整數采用希爾排序，步長取5，3，1，并需要顯示出每次需要插入的數，并完成該資料的排序。

輸入：标準輸入，輸入的第一行為整數的個數n值，第二行為n個整數，每個整數之間為一個空格。

輸出：标準輸出，輸出第一行依次輸出排序過程中需要插入的數，每個輸出資料之間使用一個空格隔開,第二行輸出排序後的序列，每個輸出資料之間使用一個空格隔開。

相關視訊連結

資料結構排序算法之希爾排序示範

https://www.bilibili.com/video/av17062242?t=48

代碼

import java.util.Scanner;
public class shellsort1 {
public static void main(String[] args) {
	Scanner sc = new Scanner (System.in);
	int n=sc.nextInt();
	int data[]=new int[n];
	int d[]= {5,3,1};//步長
	for (int i=0;i<n;i++)
		data[i] = sc.nextInt();
	shellsort(data,d);
	//System.out.println();
	for (int i=0;i<n;i++)
		System.out.print(data[i]+" ");
}

private static void shellsort(int[] data, int[] d) {
	// TODO Auto-generated method stub
	int k,h,j,temp,p;
	for (k=0;k<3;k++) {
		h=d[k];
		for(j=h;j<data.length;j++) {//選元素
			if(data[j]<data[j-h]) {
				temp=data[j];
				System.out.print(data[j]+" ");
				
				for(p=j;p>=h&&temp<data[p-h];p=p-h) {//将選中的元素放在合理的位置上；
					data[p] = data[p-h];
				}
				data[p]=temp;
			}
		}		
	}
	System.out.println();
}
}
           

用例

輸入樣例：

14

39 80 76 41 13 29 50 78 30 11 100 7 41 86

輸出樣例：

29 50 30 11 7 41 39 13 86 7 29 11 30 41 50 80 78

7 11 13 29 30 39 41 41 50 76 78 80 86 100

結果