java排序：直接插入排序和希尔排序

秒速五厘米 2022-06-16 08:15 139阅读 0赞

插入排序的基本思想：每次将一个待排序关键字插入到已经排好顺序的序列中，直到全部记录插入为止。

直接插入是从第2个开始插入，之后逐一插入，而希尔排序是以一个间隔进行插入，逐渐缩小间隔进行插入。当数量较大时，希尔排序更快，但不稳定最好为O（n）最坏和直接插入相同为O(n²)。

import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.util.StringTokenizer;
    
    public class Sort {
    	public static int[]Data=new int[10];//数据数组
    	public static void main(String[] args) {
    		int i; //循环变量
    		int index; //数组下标变量
    		index=0;//数组下标变量初始化
    		//读取输入数据存入数组中
    		InputStreamReader is=new InputStreamReader(System.in);
    		BufferedReader br=new BufferedReader(is);
    		StringTokenizer st;
    		do{  //读取输入值
    			System.out.println("Data"+index+";");
    			try {
    				String myline=br.readLine();
    				st=new StringTokenizer(myline);
    				Data[index]=Integer.parseInt(st.nextToken());
    				System.out.println(Data[index]);
    				
    			} catch (Exception e) {
    				System.out.println("IO Error");
    			}
    			index++;
    		}while(Data[index-1]!=0);
    		//排序前数据内容
    		System.out.println("Before Insert Sorting");
    		for(i=0;i<index-1;i++){
    			System.out.println(""+Data[i]+"");
    		}
    		System.out.println("");
    		//InsertSort(index-1);
    		shellsort(index);
    		System.out.println("After Insert Sorting");
    		for(i=0;i<index-1;i++){
    			System.out.println(""+Data[i]+"");
    		}
    		System.out.println("");
    		/*
    		 * 3,4,1,2
    		 * 3,4,1,2
    		 * 1,3,4,2
    		 * 1,2,3,4
    		 */
    	}
    	public static void InsertSort(int index){
    		int i,j,k; //循环变量
    		int InsertNode ; //与插入数据变量
    		for(i=1;i<index;i++){
    			InsertNode=Data[i];//设定与插入的数值
    			j=i-1; 
    			//找适当的插入位置
    			while(j>=0&&InsertNode<Data[j]){
    				System.out.println("j:"+Data[j]);
    				System.out.println("j+1:"+Data[j+1]);
    				Data[j+1]=Data[j];
    				j--;
    			}
    			Data[j+1]=InsertNode;//将数值插入
    			//打印当前排序结果
    			System.out.println("Current sorting result");
    			for(k=0;k<index;k++){
    				System.out.println(""+Data[k]+"");
    			}
    			System.out.println("");
    		}
    		
    		
    		
    	}
    	public static void shellsort(int index){
    		int i,j,k; //循环变量
    		int Temp; //暂存变量
    		boolean Change; //数据是否改变
    		int DataLength; //分割集合的间隔长度
    		int pointer; //进行处理的位置
    		DataLength=(int)index/2;
    		while (DataLength!=0) {
    			//对各个集合进行处理
    			for(j=DataLength;j<index;j++){
    				Change=false;
    				Temp=Data[j];  //暂存data[j]的值，待交换值时用
    				pointer=j-DataLength; //计算进行处理的位置
    					//进行集合内数值的比较于交换值
    				while(Temp<Data[pointer]&&pointer>=0&&pointer<=index){
    					Data[pointer+DataLength]=Data[pointer];
    					pointer=pointer-DataLength;
    					Change=true;
    					if(pointer<0||pointer>index){
    						break;
    					}
    					
    					}
    				Data[pointer+DataLength]=Temp;//与最后的数值交换
    				if(Change){
    					System.out.println("Current sorting result");
    					for(k=0;k<index;k++){
    						System.out.println(""+Data[k]+"");
    					}
    					System.out.println("");
    				}
    				
    			}
    			DataLength=DataLength/2; //计算分割长度
    		}
    		
    		
    		
    	}
    }