Java基礎算法(2)——插入排序

1.插入排序思路簡述

周遊時每一進制素插入前面已排序的序列中的合适位置(若為升序則大于前一進制素小于後一進制素)

以c s d n x i n g w e i 為例子，排序過程如下：

因為要插入元素，是以直接從第二個元素開始周遊：

以下為排序過程：

第一次插入s: s>c,s插入c後面： c s d n x i n g w e i

第二次插入d: d>c,與下一進制素比較 d<s 插入c和s之間：c d s n x i n g w e i

第三次插入n: n>c,n>d,n<s,插入d和s之間：c d n s x i n g w e i

第四次差入x: x>c,x>d,x>n,x>s,插入s之後 :c d n s x i n g w e i

第五次差入i : i>c,i>d,i<n i插入d和n之間:c d i n s x n g w e i

第六次差入n: … c d i n n s x g w e i

第七次差入g: … c d g i n n s x w e i

第八次差入w: … c d g i n n s w x e i

第九次差入e: … c d e g i n n s w x i

第十次差入i: … c d e g i i n n s w x

當然以上比較大小是從前往後，是尋找比目前大的數值，也可是從後往前，從後往前就是尋找比目前小或等于的數值，下面代碼實作是采用從後往前比較大小，若目前元素大于所周遊的元素則交換位置：

同樣是上面例子：

分析最後一次插入過程：

第9次周遊結果 c d e g i n n s w x i

插入i

采用從後往前比較大小，尋找第一個比目前插入值小或等于的數值，并放在此數值之後。

i<x,比目前插入值大，是以i和x交換位置

c d e g i n n s w i x

i<w,比目前插入值大，是以i和w交換位置

c d e g i n n s i w x

i<s,比目前插入值大，是以i和s交換位置

c d e g i n n i s w x

i<n,比目前插入值大，是以i和n交換位置

c d e g i n i n s w x

i<n,比目前插入值大，是以i和n交換位置

c d e g i i n n s w x

i=i，是比目前插入值小或等于的數值，是以不用交換位置了，目前所在位置即使合理的插入位置

是以第10次周遊結果 c d e g i i n n s w x

2.完整代碼實作(含注釋）

與上一篇文章選擇排序類似，繼承排序類模闆類Template

Java基礎算法(1)——選擇排序

package Algorithm.Sort;

/**
 * 插入排序
 * time:2019.08.20
 * author:lipiao
 */
public class InsertionSort extends Template {

    //升序
    public static void sort(Comparable[] a) {
        int N = a.length;
        System.out.println("排序過程:");

        //從下标為1開始周遊
        for (int i = 1; i < N; i++) {

            //周遊a[i]之前的元素 并插入到大于前一進制素小于後一進制素的位置
            //以此保證每次插入元素後下标為0到i的序列為升序
            for (int j=i;j>0&&less(a[j],a[j-1]);j--){
                exch(a,j,j-1);
            }
            //輸出每次周遊後的結果
            show(a);

        }
    }

    public static void main(String[] args) {
        String[] a = {"c", "s", "d", "n", "x", "i", "n", "g", "w", "e", "i"};
        System.out.println("插入排序前");
        show(a);
        sort(a);
        assert isSorted(a);
        System.out.println("插入排序後");
        show(a);
    }
}


           

3.運作效果

完整的排序過程分析：

插入排序前
c s d n x i n g w e i 
排序過程:
插入s
第1次周遊結果 c s d n x i n g w e i 
=============
插入d
d<s,是以d和s交換位置
c d s n x i n g w e i 
第2次周遊結果 c d s n x i n g w e i 
=============
插入n
n<s,是以n和s交換位置
c d n s x i n g w e i 
第3次周遊結果 c d n s x i n g w e i 
=============
插入x
第4次周遊結果 c d n s x i n g w e i 
=============
插入i
i<x,是以i和x交換位置
c d n s i x n g w e i 
i<s,是以i和s交換位置
c d n i s x n g w e i 
i<n,是以i和n交換位置
c d i n s x n g w e i 
第5次周遊結果 c d i n s x n g w e i 
=============
插入n
n<x,是以n和x交換位置
c d i n s n x g w e i 
n<s,是以n和s交換位置
c d i n n s x g w e i 
第6次周遊結果 c d i n n s x g w e i 
=============
插入g
g<x,是以g和x交換位置
c d i n n s g x w e i 
g<s,是以g和s交換位置
c d i n n g s x w e i 
g<n,是以g和n交換位置
c d i n g n s x w e i 
g<n,是以g和n交換位置
c d i g n n s x w e i 
g<i,是以g和i交換位置
c d g i n n s x w e i 
第7次周遊結果 c d g i n n s x w e i 
=============
插入w
w<x,是以w和x交換位置
c d g i n n s w x e i 
第8次周遊結果 c d g i n n s w x e i 
=============
插入e
e<x,是以e和x交換位置
c d g i n n s w e x i 
e<w,是以e和w交換位置
c d g i n n s e w x i 
e<s,是以e和s交換位置
c d g i n n e s w x i 
e<n,是以e和n交換位置
c d g i n e n s w x i 
e<n,是以e和n交換位置
c d g i e n n s w x i 
e<i,是以e和i交換位置
c d g e i n n s w x i 
e<g,是以e和g交換位置
c d e g i n n s w x i 
第9次周遊結果 c d e g i n n s w x i 
=============
插入i
i<x,是以i和x交換位置
c d e g i n n s w i x 
i<w,是以i和w交換位置
c d e g i n n s i w x 
i<s,是以i和s交換位置
c d e g i n n i s w x 
i<n,是以i和n交換位置
c d e g i n i n s w x 
i<n,是以i和n交換位置
c d e g i i n n s w x 
第10次周遊結果 c d e g i i n n s w x 
=============
插入排序後
c d e g i i n n s w x 

Process finished with exit code 0