算法-排序-插入排序

1.1 描述

算法描述如下：

• 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序；

• 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；

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

• 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；

• 將新元素插入到該位置后；

• 重復(fù)步驟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 總結(jié)

插入排序需要注意三個(gè)點(diǎn)：

• 1.分兩層循環(huán)，第一層循環(huán)用于確定從后往前遍歷的范圍，不斷往后偏移一個(gè)位置；
• 2.第二層循環(huán)起始位置為第一層循環(huán)的位置，但是開始比較的位置為這個(gè)位置的后一個(gè)位置，只有當(dāng)后一個(gè)位置比前一個(gè)位置小的時(shí)候，兩者發(fā)生交換，同時(shí)交換的還有位置的索引，否則只交換數(shù)字，會(huì)導(dǎo)致比較元素丟失。
• 3.第二層循環(huán)交換元素完成之后，索引往前挪，挪的位置始終是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

示意圖如下：