[C#] 選擇排序法 (Selection Sort)

  • 12767
  • 0

[C#] 選擇排序法 (Selection Sort)

Introduction

將元素分為 已排序(右邊)未排序(左邊)的 。重複在未排序的部分尋找最大元素,將找到的元素放到已排序的前面,一直到未排序的部分沒有元素為止。

比方說 List 中有 N 個元素。

所以必須比較 n - 1 回。每回比較 n - i 次。

 

Examples

 

   public static void selectSort(int[] list) {
            int temp, winner_no, winner_position;
            int n = list.Length;
            
            for (int round = 1; round <= n - 1; round++)      // 外層迴圈控制比賽回數
            {
                winner_position = n - round;        // 設定優勝者位置,開始時在最右側
                winner_no = 0;                    // 0號選手永遠是種子選手,是剛開始的優勝者
                for (int i = 1; i <= n - round; i++) { 	// 內層迴圈控制每回比賽次數
                    if (list[i] > list[winner_no]) {
                        winner_no = i; // i號選手是新的優勝者
                    }
                }
                // 內圈迴路結束,取得本回最大值
                // 將本回最大值與未排序區裡最右邊的值對調
                temp = list[winner_no];
                list[winner_no] = list[winner_position];
                list[winner_position] = temp;

                //以下印出每回合的排序結果
                Console.WriteLine("\nround : " + round.ToString());
                for (int index = 0; index < list.Length; index++)
                    Console.Write(list[index] + " ");
            }
        }
        static void Main(string[] args) {            
            int[] list = new int[] {70,80 ,31, 37, 10, 1 ,48, 60, 33, 80};
            Console.WriteLine("Before sort");
            for (int n = 0; n < list.Length; n++)
                Console.Write(list[n] + " ");
            selectSort(list);
            Console.WriteLine("\nAfter sort");
            for (int n = 0; n < list.Length; n++)
                Console.Write(list[n] + " ");

            Console.ReadKey();
        }

 

結果:

2010-04-12_220032

 

Refrence

http://en.wikipedia.org/wiki/Selection_Sort

三小俠  小弟獻醜,歡迎指教