插入排序之希尔排序

数据结构与算法分析 写道

 

/*希尔排序(Shell Sort)是插入排序的一种。其基本思想是：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1
	 * 个组，所有距离为d1的倍数的记录放在同一个组中，在各个组中进行插入排序；然后，取第二个增量d2<d1，重复上述的分组和排序，
	 * 直至所取的增量dt=1(dt<dt-1<...<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
	 * new int[]{8,5,1,7,9,4,6}，开始分割集合的间隔长度为3的情况，[[6][3][0]比较排序后，[4]和[1]比较排序后，[5]和[2]比较排序后，
	 * 分割集合的间隔长度为1，这时[1]和[0]比较排序后，[2][1][0]....,和直接插入排序一样了。*/
	public static void shellSort(int[] intArray) {
		 System.out.print("将要排序的数组为:        ");
		 for(int k=0;k<intArray.length;k++)
	    		System.out.print(" "+intArray[k]+" ");
	    	System.out.println();
		
		int arrayLength=intArray.length;
		int j,k;//循环变量
		int temp;//暂存变量
		boolean isChange;//数据是否改变
		int dataLength;//分割集合的间隔长度
		int pointer;//进行处理的位置
		dataLength=arrayLength/2;//初始集合间隔长度
		while(dataLength!=0){//数列仍可进行分割
			//对各个集合进行处理
			for(j=dataLength;j<arrayLength;j++){
				isChange=false;
				temp=intArray[j];//暂存，待交换值时用
			    pointer=j-dataLength;//计算进行处理的位置
			    //进行集合内数值的比较与交换值
			    while(temp<intArray[pointer]&&pointer>=0&&pointer<arrayLength){
			    	intArray[pointer+dataLength]=intArray[pointer];
			    	//计算下一个欲进行处理的位置
			    	pointer=pointer-dataLength;
			    	isChange=true;
			     	System.out.print("every changing result: ");
			    	for(k=0;k<arrayLength;k++)
			    		System.out.print(" "+intArray[k]+" ");
			    	System.out.println();
			    	if(pointer<0||pointer>arrayLength)
			    		break;
			    }
			    //与最后的数值交换
			    intArray[pointer+dataLength]=temp;
			    if(isChange){
			    	System.out.print("Current sorting result: ");
			    	for(k=0;k<arrayLength;k++)
			    		System.out.print(" "+intArray[k]+" ");
			    	System.out.println();
			    }
			}
			System.out.print("指定分割集合的间隔长度为"+dataLength+"，对各个集合进行处理后，Current sorting result: ");
	    	for(k=0;k<arrayLength;k++)
	    		System.out.print(" "+intArray[k]+" ");
	    	System.out.println();
	    	dataLength=dataLength/2;//计算下次分割的间隔长度
		}
	}

 运行后的结果为：

将要排序的数组为:         8  5  1  7  9  4  6 
every changing result:  8  5  1  8  9  4  6 
Current sorting result:  7  5  1  8  9  4  6 
every changing result:  7  5  1  8  9  4  8 
every changing result:  7  5  1  7  9  4  8 
Current sorting result:  6  5  1  7  9  4  8 
指定分割集合的间隔长度为3，对各个集合进行处理后，Current sorting result:  6  5  1  7  9  4  8 
every changing result:  6  6  1  7  9  4  8 
Current sorting result:  5  6  1  7  9  4  8 
every changing result:  5  6  6  7  9  4  8 
every changing result:  5  5  6  7  9  4  8 
Current sorting result:  1  5  6  7  9  4  8 
every changing result:  1  5  6  7  9  9  8 
every changing result:  1  5  6  7  7  9  8 
every changing result:  1  5  6  6  7  9  8 
every changing result:  1  5  5  6  7  9  8 
Current sorting result:  1  4  5  6  7  9  8 
every changing result:  1  4  5  6  7  9  9 
Current sorting result:  1  4  5  6  7  8  9 
指定分割集合的间隔长度为1，对各个集合进行处理后，Current sorting result:  1  4  5  6  7  8  9 

 当分割的间隔为1时，变成了直接插入排序。