iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 27
0
自我挑戰組

學習資料結構30天系列 第 27

[Data Structure][Sort] - Insertion Sort

前言

昨天介紹了最直覺的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 

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


上一篇
[Data Structure][Sort] - Selection Sort
下一篇
[Data Structure][Sort] - Merge Sort
系列文
學習資料結構30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言