算法排序----插入排序法

淩亂°似流年 2022-05-22 20:59 179阅读 0赞

接下来我来讲述一下插入排序法。

首先来解释一下插入排序法的原理，它的原理是每插入一个数都要将它和之前的已经完成排序的序列进行重新排序，也就是要找到新插入的数对应原序列中的位置。那么也就是说，每次插入一个数都要对原来排序好的那部分序列进行重新的排序，时间复杂度同样为O（n²）。 这种算法是稳定的排序方法。

下面我用一个图来解释一下

首先这是一个未经排序的数组

![70][]

我们要做的从a\[1\]开始，至于为什么不是a\[0\]。a\[0\]之前没有与a\[0\]进行比较的元素。我们插入a\[1\]，这个时候我们需要遍历a\[1\]和a\[1\]之前的所有元素进行比较。这个时候我们需要设置一个变量j，用来记录第一个 比 a\[1\]元素小的那个元素的下标，也就是a\[1\]要插入的位置，这个时候跳出循环，并且每发现一个比a\[1\]大的元素，就要令这个元素后移一位。依次类推的算法直到整个数组的最后一个。

以a\[4\]为例，假设a\[3\]  (注意，这个地方，从a\[0\]到a\[3\]已经完成了排序)小于 a\[4\] ，那么就j的值是 3

那么这个时候 a\[4\] 就应该放在 下标是3+1 = 4的位置处

![70 1][]

下面我来展示一下我的代码并对代码进行具体的解释。

/**
    	 * 插入排序法<br>
    	 * <font color="red">时间复杂度: n²</font>
    	 * @param array
    	 * @return
    	 */
    public int[] insertSort(int[] array){
    	
    	//直接插入排序
    			//在排序之前我们需要搞清一个思路，新插入一个数据的时候，排序过后的数组都是
    			//从小到大排列好的，所以我们需要从后往前查找，直到找到比我们要插入的数字还小的
    			//值。这个时候我们需要一个变量j作为标识
    			for(int i = 1;i<array.length;i++){
    				int temp = array[i];
    				int j;
    				for(j = i-1;j>=0;j--){
    					//将大于temp的数向后移动一步
    					if(array[j]>temp){
    						array[j+1] = array[j];//记录j的值也就是temp要插入的位置
    					}else{
    						break;
    					}
    				}
    				array[j+1] = temp;
    			}
    			
    		
    	return array;
    }

我们可以看到，这个数组我是从 array\[1\] 开始的 。令temp 等于 array\[i\]。 将 i之前的所有元素和它对比。注意是倒序对比。因为实际上，每找到一个比array\[i\]大的元素 就要让它向后移动一位，空出一个位置，最后空出的位置就是temp 应该在的位置。

举个例子，a\[5\] 在排序中，假设 a\[4\] 比 a\[5\] 大，那么原先数组的 a\[5\] 值就要变成 a\[4\] 了 。这个时候 j 是 4.

![70 2][]

那么如果这个时候a\[3\] 比 a\[5\] 小呢，那么循环就要跳出。j的值是3

![70 3][]

那么这个temp的值应该放在哪里呢，很明显应该是 a\[4\]才对啊。

这就是插入排序法，它和冒泡排序法一样，适合于所有的情况。但是缺点就是时间消耗会非常大。

[70]: /images/20220523/803c655156ea4ab3a1dfbc5198fc2af4.png
[70 1]: /images/20220523/8739dbbacb894795bcbada120b1e1b8c.png
[70 2]: /images/20220523/89ef621586cd4d27bf276e4c3bbf2661.png
[70 3]: /images/20220523/22bf63b6b86b413db4f027e3c17ce12a.png