三种插入排序代码实现 (直接插入排序 +折半插入排序 +希尔排序)

迈不过友情╰ 2022-05-26 12:54 230阅读 0赞

**插入排序**

**1、直接插入排序**

**2、折半插入排序**

**3、希尔排序**

1、直接插入排序

package sort;
    
    public class InsertSort {//直接插入排序
    
    	//有序区    无序区  [前：后]
    	public static void sortA(int[] arr,int n){
    		int tmp;//临时值
    		int i,j;
    		for(i=1;i<n;i++){//保证从小到大
    			if(arr[i]<arr[i-1])//后一个数  <前一个数
    			{
    				tmp=arr[i];//存放那个值
    				//比较大的数，向右移动
    				//不可缺少的条件：j>=0
    				
    				//失败一：
    				//for(j=i-1;arr[j]>tmp;j--){
    				//失败二：
    				//for(j=i-1;arr[j]>tmp&&j>=0;j--){
    				
    				for(j=i-1;j>=0&&arr[j]>tmp;j--){  // i-1  >  i
    					arr[j+1]=arr[j];
    				}
    				arr[j+1]=tmp;
    			}
    		}
    	}
    
    	
    	public static void main(String[] args) {
    		int  arr[]={4,5,6,3,1,9,0,8,7,2};
    		
    		System.out.println("排序前：");
    		for(int i=0;i<arr.length;i++){
    			System.out.print(arr[i]+" ");
    		}
    		
    		sortA(arr,arr.length);
    		
    		System.out.println("\n排序后：");
    		for(int i=0;i<arr.length;i++){
    			System.out.print(arr[i]+" ");
    		}
    	}
    }

2、折半插入排序

package sort;
    
    //折半插入排序
    public class HalfInsertSort {
    
    	// 有序区 无序区 [前：后]
    	public static void sortA(int[] arr, int n) {
    		int tmp;// 临时值
    		int i, j;
    		int low, mid, high;// 左边 中间 右边
    		for (i = 1; i < n; i++) {// 保证从小到大
    			tmp = arr[i];// 存放那个值
    			// 改进了直接插入排序的插入点位置
    			// 通过折半查找的方法进行查找插入位置，优化
    			low = 0;
    			high = i - 1;
    //			high = n - 1;//错误
    			while (low <= high) {// 在arr[low .. high] 中折半查找 有序 插入的位置
    				mid = (low + high) / 2;// 中间位置
    				if (arr[mid] > tmp) {// 插入位置 在 左半区【左】
    					high = mid - 1;
    				} else
    					low = mid + 1;// 插入位置 在 右半区【右】
    			}//low>high的时候终止
    //			System.out.println("low:"+low+"---high:"+high);
    			//此时，知道了插入的元素位置
    			
    			
    			//插入位置为 x=high+1=low   
    			//方法一：
    			//注意:j=i-1开始，因为for循环的开始，是1开始
    			for(j=i-1;j>=high+1;j--){  // i-1  >  i
    				arr[j+1]=arr[j];
    			}
    			arr[high+ 1] = tmp;
    			
    			//将插入位置到待插入元素的位置上的元素整体向后移动一个位置
    			//方法二：
    //	        for(j = i; j > low; j--) {
    //	        	arr[j] = arr[j-1];
    //	        }
    //	        arr[low] = tmp;
    		}
    	}
    
    	public static void main(String[] args) {
    		int arr[] = { 4, 5, 6, 3, 1, 9, 0, 8, 7, 2 };
    
    		System.out.println("排序前：");
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i] + " ");
    		}
    
    		sortA(arr, arr.length);
    
    		System.out.println("\n排序后：");
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i] + " ");
    		}
    	}
    }

3、希尔排序

package sort;
    
    //希尔排序    优于  n*n
    public class ShellSort {
    
    	//直接插入排序 -->  希尔排序
    	public static void sortA(int[] arr,int n){
    		int tmp;//临时值
    		int i,j;
    		
    		int gap=n;//间隔
    		while(gap>1){//gap=1的时候，排序完成
    			gap=gap/3+1;
    			//直接插入排序：比较   i  和   i-1
    			//希尔排序：        比较   i  和   i-gap
    			for(i=gap;i<n;i++){//保证从小到大
    				if(arr[i]<arr[i-gap])//后一个数  <前一个数
    				{
    					tmp=arr[i];//存放那个值
    					//比较大的数，向右移动
    					
    					//直接插入排序：比较   i-1  >  i   移动  j--
    					//希尔排序：        比较   i-gap >  i  移动  j=j-gap
    					for(j=i-gap;j>=0&&arr[j]>tmp;j=j-gap){  
    						arr[j+gap]=arr[j];
    					}
    					arr[j+gap]=tmp;
    				}
    			}
    		}
    	}
    
    	
    	public static void main(String[] args) {
    		int  arr[]={4,5,6,3,1,9,0,8,7,2};
    		
    		System.out.println("排序前：");
    		for(int i=0;i<arr.length;i++){
    			System.out.print(arr[i]+" ");
    		}
    		
    		sortA(arr,arr.length);
    		
    		System.out.println("\n排序后：");
    		for(int i=0;i<arr.length;i++){
    			System.out.print(arr[i]+" ");
    		}
    	}
    }