排序方法？
1.插入排序
算法思想
插入排序使用了兩層嵌套循環，逐個處理待排序的記錄。每個記錄與前面已經排好序的記錄序列進行比較，并將其插入到合適的位置。假設數組長度為n，外層循環控制變量i由1至n-1依次遞進，用于選擇當前處理哪條記錄；里層循環控制變量j，初始值為i，并由i至1遞減，與上一記錄進行對比，決定將該元素插入到哪一個位置。這里的關鍵思想是，當處理第i條記錄時，前面i-1條記錄已經是有序的了。需要注意的是，因為是將當前記錄與相鄰的上一記錄相比較，所以循環控制變量的起始值為1（數組下標），如果為0的話，上一記錄為-1，則數組越界。
現在我們考察一下第i條記錄的處理情況：假設外層循環遞進到第i條記錄，設其關鍵碼的值為X，那么此時有可能有兩種情況：
如果上一記錄比X大，那么就交換它們，直到上一記錄的關鍵碼比X小或者相等為止。
如果上一記錄比X小或者相等，那么之前的所有記錄一定是有序的，且都比X小，此時退出里層循環。外層循環向前遞進，處理下一條記錄。
算法實現(C#)
public class SortAlgorithm {
// 插入排序
public static void InsertSort<T, C>(T[] array, C comparer)
where C:IComparer<T>
{
for (int i = 1; i <= array.Length - 1; i++) {
//Console.Write("{0}: ", i);
int j = i;
while (j>=1 && comparer.Compare(array[j], array[j - 1]) < 0) {
swap(ref array[j], ref array[j-1]);
j--;
}
//Console.WriteLine();
//AlgorithmHelper.PrintArray(array);
}
}
// 交換數組array中第i個元素和第j個元素
private static void swap<T>(ref T x,ref T y) {
// Console.Write("{0}<-->{1} ", x, y);
T temp = x;
x = y;
y = temp;
}
}
上面Console.WriteLine()方法和AlgorithmHelper.PrintArray()方法僅僅是出于測試方便，PrintArray()方法依次打印了數組的內容。swap<T>()方法則用于交換數組中的兩條記錄，也對交換數進行了打?。ㄟ@里我注釋掉了，但在測試時可以取消對它們的注釋）。外層for循環控制變量i表示當前處理第i條記錄。
public class AlgorithmHelper {
// 打印數組內容
public static void PrintArray<T>(T[] array) {
Console.Write(" Array:");
foreach (T item in array) {
Console.Write(" {0}", item);
}
Console.WriteLine();
}
}
// 獲得Comparer，進行比較
public class ComparerFactory {
public static IComparer<int> GetIntComparer() {
return new IntComparer();
}
public class IntComparer : IComparer<int> {
public int Compare(int x, int y) {
return x.CompareTo(y);
}
}
}
上面這段代碼我們創建了一個ComparerFactory類，它用于獲得一個IntComparer對象，這個對象實現了IComparer<T>接口，規定了兩個int類型的關鍵碼之間比較大小的規則。如果你有自定義的類型，比如叫MyType，只需要在ComparerFactory中再添加一個類，比如叫MyTypeComparer，然后讓這個類也實現IComparer<T>接口，最后再添加一個方法返回MyTypeComparer就可以了。
輸出演示(C#)
接下來我們看一下客戶端代碼和輸出：
static void Main(string[] args) {
int[] array = {42,20,17,13,28,14,23,15};
//int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
AlgorithmHelper.PrintArray(array);
SortAlgorithm.InsertSort
(array, ComparerFactory.GetIntComparer());
}
算法實現(C++)
// 對int類型進行排序
class IntComparer{
public:
static bool Smaller(int x, int y){
return x<y;
}
static bool Equal(int x, int y){
return x==y;
}
static bool Larger(int x, int y){
return x>y;
}
};
// 插入排序
template <class T, class C>
void InsertSort(T a[], int length){
for(int i=1;i<=length-1;i++){
int j = i;
while(j>=1 && C::Smaller(a[j], a[j-1])){
swap(a[j], a[j-1]);
j--;
}
}
}
2.冒泡排序
算法思想
如果你從沒有學習過有關算法方面的知識，而需要設計一個數組排序的算法，那么很有可能設計出的就是泡沫排序算法了。因為它很好理解，實現起來也很簡單。它也含有兩層循環，假設數組長度為n，外層循環控制變量i由0到n-2遞增，這個外層循環并不是處理某個記錄，只是控制比較的趟數，由0到n-2，一共比較n-1趟。為什么n個記錄只需要比較n-1趟？我們可以先看下最簡單的兩個數排序：比如4和3，我們只要比較一趟，就可以得出3、4。對于更多的記錄可以類推。
數組記錄的交換由里層循環來完成，控制變量j初始值為n-1（數組下標），一直遞減到1。數組記錄從數組的末尾開始與相鄰的上一個記錄相比，如果上一記錄比當前記錄的關鍵碼大，則進行交換，直到當前記錄的下標為1為止（此時上一記錄的下標為0）。整個過程就好像一個氣泡從底部向上升，于是這個排序算法也就被命名為了冒泡排序。
我們來對它進行一個考察，按照這種排序方式，在進行完第一趟循環之后，最小的一定位于數組最頂部（下標為0）；第二趟循環之后，次小的記錄位于數組第二（下標為1）的位置；依次類推，第n-1趟循環之后，第n-1小的記錄位于數組第n-1（下標為n-2）的位置。此時無需再進行第n趟循環，因為最后一個已經位于數組末尾（下標為n-1）位置了。
算法實現(C#)
// 泡沫排序
public static void BubbleSort<T, C>(T[] array, C comparer)
where C : IComparer<T>
{
int length = array.Length;
for (int i = 0; i <= length - 2; i++) {
//Console.Write("{0}: ", i + 1);
for (int j = length - 1; j >= 1; j--) {
if (comparer.Compare(array[j], array[j - 1]) < 0) {
swap(ref array[j], ref array[j - 1]);
}
}
//Console.WriteLine();
//AlgorithmHelper.PrintArray(array);
}
}
輸出演示(C#)
static void Main(string[] args) {
int[] array = {42,20,17,13,28,14,23,15};
AlgorithmHelper.PrintArray(array);
SortAlgorithm.BubbleSort
(array, ComparerFactory.GetIntComparer());
}
算法實現(C++)
// 冒泡排序
template <class T, class C>
void BubbleSort(T a[], int length){
for(int i=0;i<=length-2;i++){
for(int j=length-1; j>=1; j--){
if(C::Smaller(a[j], a[j-1]))
swap(a[j], a[j-1]);
}
}
}
3.選擇排序
算法思想
選擇排序是對冒泡排序的一個改進，從上面冒泡排序的輸出可以看出，在第一趟時，為了將最小的值13由數組末尾冒泡的數組下標為0的第一個位置，進行了多次交換。對于后續的每一趟，都會進行類似的交換。
選擇排序的思路是：對于第一趟，搜索整個數組，尋找出最小的，然后放置在數組的0號位置；對于第二趟，搜索數組的n-1個記錄，尋找出最小的（對于整個數組來說則是次小的），然后放置到數組的第1號位置。在第i趟時，搜索數組的n-i+1個記錄，尋找最小的記錄（對于整個數組來說則是第i小的），然后放在數組i-1的位置（注意數組以0起始）?？梢钥闯?，選擇排序顯著的減少了交換的次數。
需要注意的地方是：在第i趟時，內層循環并不需要遞減到1的位置，只要循環到與i相同就可以了，因為之前的位置一定都比它?。ㄒ簿褪堑趇小）。另外里層循環是j>i，而不是j>=i，這是因為i在進入循環之后就被立即保存到了lowestIndex中。
算法實現(C#)
public static void SelectionSort<T, C>(T[] array, C comparer)
where C : IComparer<T>
{
int length = array.Length;
for (int i = 0; i
