C#實現選擇排序
選擇排序是一種低效的排序算法,大致過程是:遍歷數組的每一個元素,先假設0號位置上的元素是最小的,並把0號索引賦值給一個表示最小元素索引的變量,比如說是smallest,再遍歷0號位置以後的元素,一旦發現有比0號位置元素更小的元素,就把該元素的索引賦值給smallest,繼續遍歷,最終把0號位置以後最小元素的索引賦值給瞭smallest變量,再把0號位置和smallest位置上的元素互換,這樣,在0號位置上放上瞭最小元素。接著,在1號位置放上倒數第二小的元素,在2號位置放上倒數第三小的元素……以此類推,最終得到一個升序排列的數組。由於是依次循環遍歷數組元素,個人更願意把選擇排序理解成線性排序。
自定義一個類,裡面維護著一個int[]類型數組,通過構造函數定義數組長度並初始化,並提供瞭打印和選擇排序的相關方法。
public class MyArray { private static int[] arr; private static Random r = new Random(); public MyArray(int size) { arr = new int[size]; for (int i = 0; i < size; i++) { arr[i] = r.Next(1, 100); } } //選擇排序算法 public void Sort() { int smallest; //最小元素的索引 //最後一個索引位置不需要遍歷,因為在代碼段的內部循環中包含瞭對最後一個索引位置的處理 for (int i = 0; i < arr.Length - 1; i++) { //把當前遍歷的元素的索引賦值給smallest,即假設當前遍歷的數組元素為最小元素 smallest = i; //遍歷當前遍歷元素後面的所有元素 //獲取最小元素的索引 for (int index = i + 1; index < arr.Length; index++) { if (arr[index] < arr[smallest]) { smallest = index; } } //把當前遍歷元素和最小元素交換位置 Swap(i, smallest); //每次排完序打印 Print(); } } //交換2個位置上的元素 public void Swap(int first, int second) { int temp = arr[first]; arr[first] = arr[second]; arr[second] = temp; } //打印數組元素 public void Print() { foreach (var item in arr) { Console.Write(item + " "); } Console.WriteLine("\n"); } }
客戶端調用。
class Program { static void Main(string[] args) { MyArray myArray = new MyArray(8); Console.Write("排序前: "); myArray.Print(); Console.WriteLine("排序後: "); myArray.Sort(); Console.ReadKey(); } }
可見,對選擇排序來說,外部循環進行瞭n-1次迭代,內部循環第一次進行瞭n-1迭代,第二次進行瞭n-2次迭代……以時間復雜度來說,忽略小項和常數項,選擇排序基本上是一個平方階,寫成O(n²)。
到此這篇關於C#實現選擇排序的文章就介紹到這瞭。希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。