插入排序法(思路及代码实现)

ゝ一世哀愁。 2023-07-15 13:03 10阅读 0赞

### 插入排序法思想： ###

插入排序的基本思想是：把n个待排序的元素看成一个有序表和一个无序表，开始时有序表只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。  
下图中的初始状态时，17就为有序表中的一个元素，剩下的元素都包含在无序表中，然后取数据3与17进行比较，然后插入到合适的位置，依次循环。插入排序的插入次数是n-1次，也就是数组长度-1次。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTE1MTk2MA_size_16_color_FFFFFF_t_70]

### 代码实现： ###

//插入排序法
    public class InsertSort { 
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		int[] arr = { 100,20,40,1};
    		insertSort(arr);
    
    	}
    	
    	public static void insertSort(int[] arr) { 
    		for(int i = 1 ; i< arr.length;i++) { 
    			int insertVal = arr[i]; //定义待插入的数据
    			int insertIndex = i-1; //定义待插入数据的前一个数据的下标
    			
    			//insertIndex >= 0 判断待插入数的前一个数下标 是不是大于等于0 如果不是的话 寄说明下标越界了 即保证数组不越界
    			//insertVal < arr[insertIndex] 判断待插入数是否小于前一位数据 如果小的话再去更换位置 
    			while(insertIndex >= 0 && insertVal < arr[insertIndex]) {  
    				//这一步就是在待插入数小于前一位数的情况下 将前一位数后移 
    				//注意：以上数组为例,移动后的数组为{100,100,40,1} 并不是{20,100,40,1}
    				//在一开始 我们就将待插入数取了出来 定义到了insertVal中 
    				arr[insertIndex+1] = arr[insertIndex]; 
    				insertIndex--; 
    			}
    			//当跳出while循环 说明插入的位置已经找到了 位置下标为 inserIndex+1 
    			//说明下位置下标为什么是inserIndex+1 比如数组为{20,30,40}
    			//当30和20比较的时候 30比20大 就不需要移动位置了 这是30应该所处的位置下标就是1
    			//而insertIndex是0 所以 待插入数的位置下标应该是insertIndex + 1;
    			arr[insertIndex + 1] = insertVal;
    			
    			System.out.println("第"+i+"次排序");
    			System.out.println(Arrays.toString(arr));
    		
    		}
    	}
    
    }

[冒泡排序][Link 1]  
[选择排序][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTE1MTk2MA_size_16_color_FFFFFF_t_70]: /images/20230528/06e664ea0f104869af92a90efd16748d.png
[Link 1]: https://blog.csdn.net/weixin_45151960/article/details/104761269
[Link 2]: https://blog.csdn.net/weixin_45151960/article/details/104762648