정렬 의 힐 정렬 삽입

3513 단어 삽입 정렬
데이터 구조 와 알고리즘 분석
 
/*希尔排序(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 일 때 정렬 을 직접 삽입 합 니 다.

좋은 웹페이지 즐겨찾기