1. 說明

• 1.直接插入排序的方式和打牌一樣，剛開始數組為空
• 2.拿到一個數字后從左到右將它與數組中的每一個數字進行比較，然后插入合適的位置
• 3.到最后，數組按照既定的順序排序好

2. 舉個例子

• 示例： [5, 3, 4, 1, 2]
• 1. 獲取數組的長度5，從第二個數開始循環操作
• 2. 取下一個比較的值3，索引i為1，上一個索引j為0
• 3.判斷5是否大于3，則索引為1的數字改為5，得到 [5, 5, 4, 1, 2]，j=j-1=-1，j<0跳出循環
• 4.將索引0的位置的數字改為3，得到[3, 5, 4, 1, 2]
• 5. 取下一個比較的值4，索引i為2，上一個索引j為1 (索引0到索引j都是有序的)
• 6. 比較索引1位置的數字，5大于4，將索引2位置的數字改為5(往后挪一位)，得到[3, 5, 5, 1, 2]，j=j-1=0
• 7. 比較索引0位置的數字，3小于4，跳出循環
• 8. 將索引1位置的數字改為4，得到[3, 4, 5, 1, 2]
• 9. 取下一個比較的值1，索引i為3，上一個索引j為2 (索引0到索引j都是有序的)
• 10. 比較索引2位置的數字，5大于1，將索引3位置的數字改為5(往后挪一位)，得到[3, 4, 5, 5, 2]，j=j-1=1
• 11. 比較索引1位置的數字，4大于1，將索引2位置的數字改為4(往后挪一位)，得到[3, 4, 4, 5, 2]，j=j-1=0
• 12. 比較索引0位置的數字，3大于1，將索引1位置的數字改為3(往后挪一位)，得到[3, 3, 4, 5, 2]，j=j-1=-1，j<0跳出循環
• 13. 將索引0位置的數字改為1，得到[1, 3, 4, 5, 2]
• 14. 取下一個比較的值2，索引i為4，上一個索引j為3（索引0到索引j都是有序的）
• 15. 比較索引3位置的數字，5大于2，將索引4位置的數字改為5(往后挪一位)，得到[1, 3, 4, 5, 5]，j=j-1=2
• 16. 比較索引2位置的數字，4大于2，將索引3位置的數字改為4(往后挪一位)，得到[1, 3, 4, 4, 5]，j=j-1=1
• 17. 比較索引1位置的數字，3大于2，將索引2位置的數字改為3(往后挪一位)，得到[1, 3, 3, 4, 5]，j=j-1=0
• 18. 比較索引0位置的數字，1小于2，跳出循環
• 19. 將索引1位置的數字改為2，得到[1, 2, 3, 4, 5]

3. java代碼示例

package com.learning.algorithm.sort;/*** 直接插入排序* 示例： 5, 3, 4, 1, 2* 1.獲取數組的長度5，從第二個數開始循環操作* ===開始循環===* 2.取下一個比較的值3，索引i為1，上一個索引j為0* 3.判斷5是否大于3，則索引為1的數字改為5，得到 [5, 5, 4, 1, 2]，j=j-1=-1，j<0跳出循環* 4.將索引0的位置的數字改為3，得到[3, 5, 4, 1, 2]* ===繼續循環===* 5.取下一個比較的值4，索引i為2，上一個索引j為1 (索引0到索引j都是有序的)* 6.比較索引1位置的數字，5大于4，將索引2位置的數字改為5(往后挪一位)，得到[3, 5, 5, 1, 2]，j=j-1=0* 7.比較索引0位置的數字，3小于4，跳出循環* 8.將索引1位置的數字改為4，得到[3, 4, 5, 1, 2]* ===繼續循環===* 9.取下一個比較的值1，索引i為3，上一個索引j為2 (索引0到索引j都是有序的)* 10.比較索引2位置的數字，5大于1，將索引3位置的數字改為5(往后挪一位)，得到[3, 4, 5, 5, 2]，j=j-1=1* 11.比較索引1位置的數字，4大于1，將索引2位置的數字改為4(往后挪一位)，得到[3, 4, 4, 5, 2]，j=j-1=0* 12.比較索引0位置的數字，3大于1，將索引1位置的數字改為3(往后挪一位)，得到[3, 3, 4, 5, 2]，j=j-1=-1，j<0跳出循環* 13.將索引0位置的數字改為1，得到[1, 3, 4, 5, 2]* ===繼續循環===* 14.取下一個比較的值2，索引i為4，上一個索引j為3（索引0到索引j都是有序的）* 15.比較索引3位置的數字，5大于2，將索引4位置的數字改為5(往后挪一位)，得到[1, 3, 4, 5, 5]，j=j-1=2* 16.比較索引2位置的數字，4大于2，將索引3位置的數字改為4(往后挪一位)，得到[1, 3, 4, 4, 5]，j=j-1=1* 17.比較索引1位置的數字，3大于2，將索引2位置的數字改為3(往后挪一位)，得到[1, 3, 3, 4, 5]，j=j-1=0* 18.比較索引0位置的數字，1小于2，跳出循環* 19.將索引1位置的數字改為2，得到[1, 2, 3, 4, 5]*/
public class DirectInsertSort {public static void sort(int array[]) {// 獲取數組的長度int length = array.length;// 從第二位開始比較for (int i = 1; i < length; ++i) {// 獲取下一個比較的值int key = array[i];// 上一個索引int j = i - 1;// 比較到索引大于等于0的 且 遍歷前面的值 與 key比較大小，如果比key大，大的值往后挪一位while (j >= 0 && array[j] > key) {// 比key大的值往后挪一位array[j + 1] = array[j];// 繼續比較前面的值和key的大小j = j - 1;}// 當array[j]比key小，則array[j+1]的數字改為keyarray[j + 1] = key;}}/* A utility function to print array of size n*/public static void print(int[] array) {for (int i : array) {System.out.print(i + " ");}}public static void main(String args[]) {int array[] = {5, 3, 4, 1, 2};DirectInsertSort.sort(array);DirectInsertSort.print(array);}
}

4. java示例截圖