經典排序算法 - 選擇排序Selection sort
顧名思意,就是直接從待排序數組裡選擇一個最小(或最大)的數字,每次都拿一個最小數字出來,順序放入新數組,直到全部拿完再簡單點,對著一群數組說,你們誰最小出列,站到最後邊
然後繼續對剩余的無序數組說,你們誰最小出列,站到最後邊
再繼續剛才的操作,一直到最後一個,繼續站到最後邊,現在數組有序了,從小到大
舉例
先說看每步的狀態變化,後邊介紹細節,現有無序數組[6 2 4 1 5 9]
第一趟找到最小數1,放到最前邊(與首位數字交換)
交換前:| 6 | 2 | 4 | 1 | 5 | 9 |
交換後:| 1 | 2 | 4 | 6 | 5 | 9 |
第二趟找到余下數字[2 4 6 5 9]裡的最小數2,與當前數組的首位數字進行交換,實際沒有交換,本來就在首位
交換前:| 1 | 2 | 4 | 6 | 5 | 9 |
交換後:| 1 | 2 | 4 | 6 | 5 | 9 |
第三趟繼續找到剩余[4 6 5 9]數字裡的最小數4,實際沒有交換,4待首位置無須交換
第四趟從剩余的[6 5 9]裡找到最小數5,與首位數字6交換位置
交換前:| 1 | 2 | 4 | 6 | 5 | 9 |
交換後:| 1 | 2 | 4 | 5 | 6 | 9 |
第五趟從剩余的[6 9]裡找到最小數6,發現它待在正確的位置,沒有交換
排序完畢輸出正確結果[1 2 4 5 6 9]
第一趟找到最小數1的細節
當前數組是| 6 | 2 | 4 | 1 | 5 | 9 |
先把6取出來,讓它扮演最小數
當前最小數6與其它數一一進行比較,發現更小數就交換角色
當前最小數6與2比較,發現更小數,交換角色,此時最小數是2,接下來2與剩余數字比較
當前最小數2與4比較,不動
當前最小數2與1比較,發現更小數,交換角色,此時最小數是1,接下來1與剩余數字比較
當前最小數1與5比較,不動
當前最小數1與9比較,不動,到達末尾
當前最小數1與當前首位數字進行位置交換,如下所示
交換前:| 6 | 2 | 4 | 1 | 5 | 9 |
交換後:| 1 | 2 | 4 | 6 | 5 | 9 |
完成一趟排序,其余步驟類似
代碼僅供參考
static void selection_sort(int[] unsorted)
{
for (int i = 0; i < unsorted.Length; i++)
{
int min = unsorted[i], min_index = i;
for (int j = i; j < unsorted.Length; j++)
{
if (unsorted[j] < min)
{
min = unsorted[j];
min_index = j;
}
}
if (min_index != i)
{
int temp = unsorted[i];
unsorted[i] = unsorted[min_index];
unsorted[min_index] = temp;
}
}
}
static void Main(string[] args)
{
int[] x = { 6, 2, 4, 1, 5, 9 };
selection_sort(x);
foreach (var item in x)
{
Console.WriteLine(item);
}
Console.ReadLine();
}