登陆 注册

java算法实现之插入排序

守望者 2020-04-09 176人围观 ,发现0个评论 java

    所谓插入排序就是指将数组分成左右两个小数组 a, b , 

数组a元素个数从一个开始递增,直至arr.lenth完成整个数组的排序,通常数组a的第一个元素是arr[0],范围逐步向右拓展;

数组b元素个数从arr.len开始递减,通常b数组第一个元素逐步替换为arr[1], arr[2], arr[3].....arr[arr.lenth-1],范围逐步向右缩小;


排序过程如下:


     拿到b数组的一个元素(从第一个开始),记为key值(key=arr[i]),

然后将key值与数组a的元素(arr[j])自右而左进行比较:

如果arr[j]>key, 则将arr[j]元素往后移动;

如果arr[j]<key,则将key值放在arr[j]位置,并立即退出比较;


重复以上步骤,直至完成b数组的所有元素的遍历。

最终,完成遍历b数组的所有元素并进行元素位置相应调整,完成整个数组的升序排列。


插入排序函数代码如下:

	// 插入排序
	public static void sort(int[] arr) {
		
	      for(int i=1;i<arr.length;i++) {
	    	  
	    	  int key = arr[i];
	    	  int j=i-1;
	    	  
	    	  for(;j>-1;j--) {
	    		   if(arr[j]>key) {
	    			    arr[j+1] = arr[j];
	    			  
	    		   }
	    		   else {
//	    			   arr[j+1] = key;
	    			   break;
	    			}
	    	  } // for
	    	  
	    	   arr[j+1] = key;
	    	  
	      } // for
	}


    转载请注明本文链接:https://tufeng.xyz/java/44.html,谢谢合作!

请发表您的评论
请关注微信公众号
微信二维码