数组插入排序

Dear 丶 2022-03-12 14:12 203阅读 0赞

排序算法是一个重要且基础的知识点。惭愧的是，个人而言，只有选择排序和冒泡排序理解起来容易些。碰到快速排序和插入排序，虽然逻辑上可以理解，但在代码实现时却碰到不小问题。

下面给出**插入排序**的一种代码实现。

**逻辑**：分为**两层循环**。设数组为array，长度为n。

**外循环**：执行n-1次插入排序，循环索引从1到到n-1。

**内循环**：索引 0到 i-1的元素为已排完序，需要将array\[i\]挨个与其前面 i 个元素作比较。先将array\[i\]赋值给一个临时变量tmp（*重要，因为array\[i\]后面会随着元素的位置交换而变化，得先将其保存*），接下来从右往左挨个比较。如果tmp更小，则交换位置。否则，结束该内循环（表明已经将tmp放到合适的位置了）。已排序的元素个数加1，接下来进行下一个外循环，即给索引为i+1的元素找到合适的插入位置。如此重复，直到为数组末端的元素找到合适位置。至此，排序结束。

import java.util.Random;
    
    public class Demo1{
        public static void main(String[] args) {
    	  int[] array = new int[10];
    	  Random random = new Random();
    	  for(int i=0; i<array.length; i++) {
    		  //生成100以内的随机正整数
    		  array[i] = random.nextInt(100);
    	  }
    	  System.out.println("10个随机整数：");
    	  printArray(array);
    	  System.out.println();
    	  insertSort(array);
    	}
    	
    	//插入排序
    	protected static void insertSort(int[] array) {
    	  for(int i=1; i<array.length; i++) {
    		  /*
    		   * 必须创建变量存储array[i]
    		   * 且这一句不能放在内循环
    		   * 因为内循环执行过程中，array[i]会变化
    		   */
    		  int tmp = array[i];
    		  for(int j=i-1; j>=0; j--) {
    			  if(tmp<array[j]) {
    				  int temp;
    				  temp = array[j];
    				  array[j] = array[j+1];
    				  array[j+1] = temp;  
    			  }
    			  else
    				  break;
    		  }
    	  }
    	  System.out.println("排序后数组：");
    	  printArray(array);
      }
    	
    	//打印数组
    	protected static void printArray(int[] array) {
    	  for(int j=0; j<array.length; j++) {
    		  System.out.print(array[j]+"  ");
    	  }
        }
    }

结果如下：

![20190306111429872.png][]

[20190306111429872.png]: /images/20220312/78ee47b67cf844db99f3074537a03dd9.png