[HackerRank]插入排序法2(Insertion Sort - Part 2)

題目描述

給定一個沒有經過排序的陣列，請使用插入排序法將這個陣列排序好，並將每次把元素移動到正確位置時的過程輸出。

原題網址

輸入格式

輸入有兩行。第一行是陣列的大小，範圍在1到1000之間(包含1和1000)。第二行是陣列的所有元素，每個元素都是範圍-10000到10000(包含-10000到10000)的整數，使用空格隔開。

輸出格式

分行輸出排序時元素移動到正確位置時的過程。

範例輸入

範例輸出

額外解釋

有關於插入排序法的介紹可以參考以下這篇文章：

一開始，排序好的子陣列尚未建立，因此直接將索引0的元素作為進入子陣列的第一個元素。再來要將之後的元素插入至這個子陣列中，並確保子陣列元素的順序，插入元素的過程如下：

　　　 ●
索引    0   1   2   3   4   5
數值    1   4   3   5   6   2

　　　 ○  ●
索引    0   1   2   3   4   5
數值    1   4   3   5   6   2
       └┬┘
       1 < 4    →    找到正確位置

　　　 ○  ○  ●
索引    0   1   2   3   4   5
數值    1   4   3   5   6   2    →    輸出
           └┬┘
           4 > 3

　　　 ○   3  ●
索引    0   1   2   3   4   5
數值    1   4   4   5   6   2
           └→┘

　　　 ○   3  ●
索引    0   1   2   3   4   5
數值    1   4   4   5   6   2
       └┬┘
       1 < 3    →    找到正確位置

　　　 ○  ○  ○  ●
索引    0   1   2   3   4   5
數值    1   3   4   5   6   2    →    輸出
               └┬┘
               4 < 5    →    找到正確位置

　　　 ○  ○  ○  ○  ●
索引    0   1   2   3   4   5
數值    1   3   4   5   6   2    →    輸出
                   └┬┘
                   5 < 6    →    找到正確位置

　　　 ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5
數值    1   3   4   5   6   2    →    輸出
                       └┬┘
                       6 > 2

　　　 ○  ○  ○  ○   2  ●
索引    0   1   2   3   4   5
數值    1   3   4   5   6   6
                       └→┘

　　　 ○  ○  ○  ○   2  ●
索引    0   1   2   3   4   5
數值    1   3   4   5   6   6
                   └┬┘
                   5 > 2

　　　 ○  ○  ○   2  ○  ●
索引    0   1   2   3   4   5
數值    1   3   4   5   5   6
                   └→┘

　　　 ○  ○  ○   2  ○  ●
索引    0   1   2   3   4   5
數值    1   3   4   5   5   6
               └┬┘
               4 > 2

　　　 ○  ○   2  ○  ○  ●
索引    0   1   2   3   4   5
數值    1   3   4   4   5   6
               └→┘

　　　 ○  ○   2  ○  ○  ●
索引    0   1   2   3   4   5
數值    1   3   4   4   5   6
           └┬┘
           3 > 2

　　　 ○   2  ○  ○  ○  ●
索引    0   1   2   3   4   5
數值    1   3   3   4   5   6
           └→┘

　　　 ○   2  ○  ○  ○  ●
索引    0   1   2   3   4   5
數值    1   3   3   4   5   6
       └┬┘
       1 < 2    →    找到正確位置

　　　 ○  ○  ○  ○  ○  ●
索引    0   1   2   3   4   5
數值    1   2   3   4   5   6    →    輸出

解題概念

從陣列的索引1開始，將之後的元素透過插入排序法插入至之前的元素所組成的已排序好的陣列中。原理還是一樣請參考以下這篇文章：

參考答案

import java.util.Scanner;

public class Solution {

    public static void main(final String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        int[] ar = new int[s];
        for (int i = 0; i < s; i++) {
            ar[i] = in.nextInt();
        }
        insertionSortPart2(ar);
    }

    private static void printArray(int[] ar) {
        for (int n : ar) {
            System.out.print(n + " ");
        }
        System.out.println("");
    }

    public static void insertionSortPart2(int[] ar) {
        for (int i = 1; i < ar.length; ++i) {
            final int n = ar[i];
            int j = i - 1;
            for (; j >= 0; --j) {
                if (n < ar[j]) {
                    ar[j + 1] = ar[j];
                } else {
                    break;
                }
            }
            ar[j + 1] = n;
            printArray(ar);
        }
    }
}