算法-排序-插入排序

1.1 描述

算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；

• 取出下一个元素，在已经排序的元素序列中从后向前扫描；

• 如果该元素（已排序）大于新元素，将该元素移到下一位置；

• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

• 将新元素插入到该位置后；

• 重复步骤2~5。

1.2 代码

public class HelloWorld {    public static void insertSort(){      int[] numbers = {5,4,3,7,2,5,1,9,12,6,8,1,34};        int length = numbers.length;      int index = 0;      while(index < length - 1){         int later = index + 1;            int front = index;            while(front >= 0){             if(numbers[later] < numbers[front]){                   int temp = numbers[front];                    numbers[front] = numbers[later];                  numbers[later] = temp;                    later = front;                }             --front;          }         index++;      }     for(int value:numbers){           System.out.println("value is:" + value);      } }  public static void main(String[] args) {      insertSort(); }}

1.3 总结

插入排序需要注意三个点：

• 1.分两层循环，第一层循环用于确定从后往前遍历的范围，不断往后偏移一个位置；
• 2.第二层循环起始位置为第一层循环的位置，但是开始比较的位置为这个位置的后一个位置，只有当后一个位置比前一个位置小的时候，两者发生交换，同时交换的还有位置的索引，否则只交换数字，会导致比较元素丢失。
• 3.第二层循环交换元素完成之后，索引往前挪，挪的位置始终是2中被比较的元素，这也是为什么需要交换索引的原因。

以1 4 3 2为例：

1 4 3 2 => 1 4 3 2

1 4 3 2 => 1 3 4 2

1 3 4 2 => 1 3 2 4

1 3 2 4 => 1 2 3 4

示意图如下：