C#實現插入排序
在選擇排序中,從第一個元素開始,依次遍歷數組中的元素,找出當前遍歷元素之後的最小元素,與當前遍歷元素交換位置,依此類推,是一種由前往後的排序。而在插入排序中,從第二個元素開始,依次遍歷數組中的元素,把當前遍歷元素與之前的元素進行比較,並插入到之前的某個位置,是一種由後往前的排序。
自定義一個類,裡面維護著一個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 < arr.Length; i++) { arr[i] = r.Next(10, 100); } } //插入排序 public void Sort() { int insert; for (int i = 1; i < arr.Length; i++) //從第二個元素開始遍歷 { insert = arr[i];//把當前遍歷元素視為插入元素,放到臨時變量insert中 int moveItem = i;//movieItem可以理解為一個動態索引,初始位置在當前遍歷元素的索引 while (moveItem > 0 && arr[moveItem -1] > insert) //如果前面一個元素比插入元素大 { arr[moveItem] = arr[moveItem - 1];//那就把前面這個元素賦值給後面位置,相當於往後移一位 moveItem--;//再把動態索引位置向前移動一位 } arr[moveItem] = insert; Print(); } } //打印數組元素 public void Print() { foreach (var item in arr) { Console.Write(item + " "); } Console.WriteLine(); } }
以上,大致過程是:從數組中第二個元素開始,先把當前遍歷元素賦值給一個臨時變量,比如說是insert,insert這個變量肯定要插入到當前遍歷元素之前的某個位置,如何確定插入位置呢?假設用moveItem變量表示最終要插入的索引位置,先把當前遍歷元素的索引賦值給moveItem,如果moveItem-1位置上的元素大於insert,那就把moveItem-1位置上的元素向後移動一位,並把moveItem-1位置的索引賦值給moveItem,insert是要插入到當前的這個moveItem位置嗎?不一定。再繼續拿當前moveItem位置的前面一個位置上的元素與insert比較,隻要是比insert大,就把該位置上的元素向後移動一位,並重新設置moveItem的值,直到停止循環。此時moveItem的值就是insert需要插入的位置。
客戶端調用。
class Program { static void Main(string[] args) { MyArray myArray = new MyArray(8); Console.WriteLine("排序前:"); myArray.Print(); Console.WriteLine("排序後:"); myArray.Sort(); Console.ReadKey(); } }
對於插入排序,當依次遍歷數組元素時,進行瞭n-1次迭代,當把第二個元素插入到之前某個位置時進行瞭1次迭代,當把第三個元素插入到之前某個位置時進行瞭2次迭代……第n個元素進行瞭n-1次迭代,以時間復雜度來說,忽略小項和常數項,插入排序基本上是一個平方階,寫成O(n²)。
到此這篇關於C#實現插入排序的文章就介紹到這瞭。希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。