[C#] 插入排序法(Insertion Sort)

2010-04-29

11595
0

Introduction

維基百科的解釋：

插入排序（Insertion Sort）的演算法描述是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。

Examples

   1: public static void insertionSort(int[] list)          2:     {          3:         // 手上第一張牌與自己無從比較，所以由第二張牌開始比(i=1)          4:         for (int i = 1; i < list.Length; i++)          5:         {          6:             int pivot = list[i];  // 依序抽一張牌          7:             for (int j = i - 1; j >= 0; j--)          8:             {      // 和已抽出來的(已排序過的)牌比大小           9:                 if (list[j] > pivot)         10:                 {        // 比較大的牌往右移動一格         11:                     list[j + 1] = list[j];         12:                     if (j == 0) list[j] = pivot;  // 如果所有牌都移動了，將已抽出的牌插入         13:                 }         14:                 else         15:                 {        // 如果沒有較大的牌可移動，將已抽出的牌插入         16:                     list[j + 1] = pivot;         17:                     break;    // 結束內圈迴路到下一個外圈迴路，抽下張牌         18:                 }         19:             }   // 內層迴圈         20:         }   // 外層迴圈         21:           22:     }          23:           24:     public static void Main()         25:     {         26:         int[] list = new int[12] { 1, 3, 6, 8, 9, 11, 7, 12, 5, 2, 13, 4 };         27:         Console.WriteLine("Before sort");         28:         for (int n=0;n<list.Length;n++)         29:            Console.Write(list[n]+" ");         30:         insertionSort(list);         31:         Console.WriteLine("\nAfter sort");         32:         for (int n = 0; n < list.Length; n++)         33:             Console.Write(list[n] + " ");         34:           35:         Console.ReadKey();         36:     } 

執行結果

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

回首頁

Introduction

維基百科 的解釋 ：

維基百科的解釋：