前言

昨天介紹了最直覺的Selection sort，今天就來介紹另外一種排序方法 - Insertion Sort 。

Insertion Sort的排序方式，就很像我們在玩撲克牌的時候，當發牌者將撲克牌一張一張的發給我們，我們每拿到一張牌，就會把那一張牌插入手上已經排過順序的撲克牌當中的正確位置。

Insertion Sort

將數列的第一個元素作為已經排序過的數值，接著從第二個元素開始往右邊依次取出，並插入已經排序過的數字中的正確位置。

• 時間複雜度: O(n²)，Best Case : O(n)

實作 :

public class Insertion_Sort 
{
	public static void main (String args[])
	{
		int ex[] =  {52, 99, 31, 60, 7, 46, 53};
        
        // before sort
		PrintArray(ex); 
		
        System.out.println("--------------------");
		InsertionSort (ex);
        
        // after sort
		PrintArray(ex); 
	}
	
	public static void InsertionSort(int ex[])
    {
		// 將array的第一個元素當成排序過的
        for(int i = 1; i < ex.length; i++)
        {
        	int temp = ex[i]; // 紀錄比較的值
        	int j = i; // 紀錄正在比較的位置(空格)
        	
        	// 如果空格左邊比空格的值大，值就往右邊補上
        	while(j > 0 && temp < ex[j - 1]) 
        	{
        		ex[j] = ex[j - 1];
        		j--;
        	}
        	
        	ex[j] = temp;
        }
    }
	
	public static void PrintArray(int ex[])
	{
		for(int i = 0; i < ex.length; i++)
	    {
			System.out.print(ex[i] + " ");
	    }
		System.out.println();
	}
}

輸出結果:

52 99 31 60 7 46 53 
--------------------
7 31 46 52 53 60 99 

註: 筆者習慣數列從左到右，值會由小到大