iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 26
0
自我挑戰組

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

[Data Structure][Sort] - Selection Sort

前言

在前面介紹了很多種資料結構,可以知道資料有很多種不同的儲存方式。
那麼,今天來介紹把資料排大小順序的方法吧。

排序 Sort (筆者習慣數列從左到右,值會由小到大)

假設你現在手上有5張學號不同的的考卷,然後你要將他們由小到大排好,方便登記分數,會想到怎麼做呢?

  • 最直覺的方法,是先從5個學號裡面找最大的,再找出剩下4個裡面最大的學號,依此找下去,就能將學號由小到大排出來。

  • 或是,比較第1張和第2張考卷的學號大小,如果左小右大,就繼續找第3張來跟第2張考卷比較,如果右小左大,就把兩張考卷交換順序,接著再把下1張考卷與前1張考卷比較,那麼比到最後一張的時候,最後一個學號就會是最大的,這樣就是一輪,比較完一輪就會找出一個最大值,所有有幾個數值就需要比較幾次,接著再按照這種方式重頭比較一次,直到比到第5次,就全部由小到大排序完了。

  • 或是先取出任何一張考卷,在從剩下的考卷取出一張,與先取出的比較,一樣左小右大排序,然後再從剩下的考卷中取出一張,與剛剛取出的兩張考卷排出大小順序,依此類推,直到沒有未排大小的考卷。

那我們先介紹最直覺的方法,Selection Sort。

Selection Sort

從數列取出最小值,與數列最左邊的值對調,再重複從剩下的數值中找出最小值,放在排序好的數字後面。

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

實作:

public class Selection_Sort 
{
	public static void main (String args[])
	{
		int ex[] =  {52, 99, 31, 60, 7, 46, 53};
		Show(ex);
		System.out.println("--------------------");
		SelectionSort (ex);
		
	}
	public static void SelectionSort(int ex[])
    {
        for(int i = 0; i < ex.length; i++)
        {
        	System.out.println();
        	System.out.println("最小值的index: " + FindMin(ex, i, ex.length));
        	Swap(ex, i, FindMin(ex, i, ex.length));
        	
        	Show(ex);
        }
    }
	
	public static int FindMin(int ex[], int x, int len)
	{
		int min = Integer.MAX_VALUE;
		int index = 0;
		for(int i = x; i < len; i++)
		{
			if(ex[i] < min)
			{
				min = ex[i];
				index = i;
			}
		}
		return index;
	}
	public static void Swap(int ex[], int x, int y)
	{
		int temp = ex[x];
		ex[x] = ex[y];
		ex[y] = temp;
	}
	
	public static void Show(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 
--------------------

最小值的index: 4
7 99 31 60 52 46 53 

最小值的index: 2
7 31 99 60 52 46 53 

最小值的index: 5
7 31 46 60 52 99 53 

最小值的index: 4
7 31 46 52 60 99 53 

最小值的index: 6
7 31 46 52 53 99 60 

最小值的index: 6
7 31 46 52 53 60 99 

最小值的index: 6
7 31 46 52 53 60 99 


上一篇
[Data Structure][Tree] - Huffman tree
下一篇
[Data Structure][Sort] - Insertion Sort
系列文
學習資料結構30天30

尚未有邦友留言

立即登入留言