第3章 基本排序算法
對計算機中數據存儲的兩個最常見的操作是排序與查找。自從計算機工業開始時這就是明確的，所以排序與查找也是計算機科學領域兩個研究最多的操作。本書討論的大部分數據結構都是主要設計為使結構中的數據存儲的排序及/或查找更容易且更高效。
本章將為你介紹排序與搜索數據的基本算法。這些算法只需要像數組這樣的數據結構，唯一"高級"的計算機技術就是循環。本章也介紹了我們整本書都使用的非正式的分析不同算法速度與效率的技術。
排序算法
我們每日工作中對大部分數據最常做的就是排序。我們通過按字母排序來搜索一個字典中的定義。我們通過姓氏的字母順序在本子中查找一個電話號碼。郵局按多種方式將郵件排序 – 先按郵政編碼，然後是地址，然後是姓名。排序是我們處理數據時的一種基本的方法，應該仔細研究。
就像我們之前提到的，有大量的工作被投入到不同排序技術的研究。雖然一些非常高級的排序算法已被發明出來，你也應當首先學習一些簡單的排序算法。這些算法如插入排序，冒泡排序，及選擇排序。這些算法都很易懂且很易用。雖然無論如何他們不是最好的排序算法，但是針對小的數據集或者其它一些特殊情況，它們是要使用的最佳算法。
一個數據類測試框架
要檢查這些算法，我們首先需要一個測試框架來實現並測試它們。我們要構建一個類來封裝在一個數組上執行的常見操作 – 元素插入，元素訪問，及顯示數組的內容。如下是代碼：
class CArray
{
private int[] arr;
private int upper;
private int numElements;
public CArray()
{ }
public CArray(int size)
{
arr = new int[size];
upper = size - 1;
numElements = 0;
}
public void Insert(int item)
{
arr[numElements] = item;
numElements++;
}
public void DisplayElements()
{
for (int i = 0; i <= upper; i++)
Console.Write(arr[i] + " ");
}
public void Clear()
{
for (int i = 0; i <= upper; i++)
arr[i] = 0; numElements = 0;
}
}
class class1
{
static void Main()
{
CArray nums = new CArray();
for (int i = 0; i <= 49; i++)
nums.Insert(i);
nums.DisplayElements();
}
}
這段代碼輸入如下：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
在離開CArray類開始檢查排序與搜索算法之前，我們需要明白怎樣真實的向CArray對象中存儲數據。為了更有效的證明不同的排序算法的工作情況，數組中的數據需要隨機排序。最好的實現方法是使用一個隨機數生成器來將每個數組元素賦給待測數組。
C#中可以使用Random類來創建隨機數。這個類的對象可以產生隨機數。要實例化一個Random類，你需要向類構造函數傳入一個種子。這個種子可以被看作隨機數生成器可以生成的數值范圍的上界。
這有另一個使用CArray類存儲數字的程序，使用隨機數生成器選擇要存儲於數組中的數據。
static void Main()
{
CArray nums = new CArray();
Random rnd = new Random(100);
for (int i = 0; i < 10; i++)
nums.Insert((int)(rnd.NextDouble() * 100));
nums.DisplayElements();
}
這段程序輸出如下：
72 54 59 30 31 78 2 77 82 72
冒泡排序
首先要介紹的排序算法是冒泡排序。冒泡排序是可用的排序算法中最慢的之一，但是它也是最易理解最易使用的最簡單的排序算法，這使它成為我們學習的最佳候選。
這個排序的名稱來源於一個元素像"泡一樣"由數組的一段"浮動"到另一端。假定你要將一個數列按升序排列，較大的值浮動到右側同時較小的值移動到左側。這個行為是通過在列表中移動多次，比較臨近的值，如果左側值大於右側值則交換它們。
圖3.1展示了冒泡排序的工作。兩個數（2與72）被插入到上一個例子的數組中，以圓圈高亮表示。你可以觀察到72怎樣被由數組的開始部分移動到數組的中部，同時也可以看到2怎樣穿過數組的中部被移到數組的開始部分。
<
