去年11月份利用冒泡排序，用js實現了一個機票查詢結果按照機票的票面價格和出發日期的頁面無刷新排序。這一段時間客戶又要求改為按照實際支付價格和日期進行排序，匆匆改好以後，感覺自己的算法和數據結構的能力幾乎荒廢了（好像以前也沒有過這種能力^_^）。這裡整理一下常用的排序算法，用c#實現，以備日後再用。Code is cheap.看具體實現吧。
1.冒泡排序
將被排序的記錄數組R[1..n]垂直排列，每個記錄R[i]看作是重量為R[i].key的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"（冒泡因此得名）。如此反復進行，直到最後任何兩個氣泡都是輕者在上，重者在下為止。
using System;
using System.Collections;
using System.Collections.Generic;
namespace BubbleSort
{
public class BubbleSorter
{
/// <summary>
/// 冒泡排序
/// </summary>
/// <param name="numArr"></param>
public void Sort(int[] numArr)
{
int tmpNum;
bool flag = false; //交換標志
for (int i = 1; i < numArr.Length; i++) //最多做numArr.Length-1趟排序
{
flag = false;
for (int j = numArr.Length - 1; j >= i; j--) //對當前無序區自下向上掃描
{
if (numArr[j] < numArr[j - 1]) //當前無序區: 輕的在下面，“冒泡”到上面
{
tmpNum = numArr[j];
numArr[j] = numArr[j - 1];
numArr[j - 1] = tmpNum;
flag = true;
}
}
if (!flag) //如果沒有發生交換，終止算法
return;
}
}
public class Program
{
public static void Main()
{
int[] testArr = new int[] { 1, 5, 11, 6, 4, 21, 99, 2, 15, 11, 34, 0, 33, 47 };
BubbleSorter sh = new BubbleSorter();
sh.Sort(testArr);
for (int m = 0; m < testArr.Length; m++)
Console.Write("{0} ", testArr[m]);
Console.Read();
}
}
}
}
冒泡算法小結：
因為每一趟排序都使有序區增加了一個氣泡，在經過n-1趟排序之後，有序區中就有n-1個氣泡，而無序區中氣泡的重量總是大於等於有序區中氣泡的重量，所以整個冒泡排序過程至多需要進行n-1趟排序。若在某一趟排序中未發現氣泡位置的交換，則說明待排序的無序區中所有氣泡均滿足輕者在上，重者在下的原則，因此，冒泡排序過程可在此趟排序後終止。為此，在下面給出的算法中，引入一個布爾量flag,在每趟排序開始前，先將其置為false,若排序過程中發生了交換，則將其置為true.各趟排序結束時檢查flag,若未曾發生過交換則終止算法，不再進行下一趟排序。（不加flag也可以實現排序，但是會造成不必要的循環和比較）。
2.快速排序 ***
一、算法思想
快速排序是C.R.A.Hoare於1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。分治法的基本思想是：將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然後將這些子問題的解組合為原問題的解。
二、快速排序的基本思想
設當前待排序的無序區為R[low..high]，利用分治法可將快速排序的基本思想描述為：
(1)分解：
在R[low..high]中任選一個記錄作為基准(Pivot)，以此基准將當前無序區劃分為左、右兩個較小的子區間R[low..pivotpos-1)和R[pivotpos+1..high]，並使左邊子區間中所有記錄的關鍵字均小於等於基准記錄(不妨記為pivot)的關鍵字pivot.key，右邊的子區間中所有記錄的關鍵字均大於等於pivot.key，而基准記錄pivot則位於正確的位置(pivotpos)上，它無須參加後續的排序。注意：劃分的關鍵是要求出基准記錄所在的位置pivotpos。劃分的結果可以簡單地表示為(注意 pivot=R[pivotpos] )： R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys,
其中low≤pivotpos≤high。(邊界條件)
(2)求解：
通過遞歸調用快速排序對左、右子區間R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
(3)組合：
因為當"求解"步驟中的兩個遞歸調用結束時，其左、右兩個子區間已有序。對快速排序而言，"組合"步驟無須做什麼，可看作是空操作。
using System;
namespace QuickSorter
{
public class QuickSort
{
public static void Sort(int[] numArr)
{
Sort(numArr, 0, numArr.Length - 1);
}
private static void Sort(int[] numArr, int left, int right)
{
if (left < right)
{
int middle = numArr[(left + right) / 2];
int i = left - 1;
int j = right + 1;
while (true)
{
while (numArr[++i] < middle) ;
while (numArr[--j] > middle) ;
if (i >= j)
break;
Swap(numArr, i, j);
}
Sort(numArr, left, i - 1);
Sort(numArr, j + 1, right);
}
}
private static void Swap(int[] numArr, int i, int j)
{
int number = numArr[i];
numArr[i] = numArr[j];
numArr[j] = number;
}
}
public class Program
{
static void Main(string[] args)
{
int[] arr = new int[] { 20, 41, 27, 14, 16, 1, 8, 55, 9, 35, 22, 14 };
QuickSort.Sort(arr);
Console.WriteLine("Numbers after quicksort:");
foreach (int i in arr)
{
Console.WriteLine(i);
}
Console.Read();
}
}
}
網上還有一種相似的代碼，一起貼出來：
using System;
namespace QuickSorter
{
public class QuickSorter
{
/// <summary>
/// 快速排序算法
/// </summary>
/// 快速排序為不穩定排序,時間復雜度O(nlog2n),為同數量級中最快的排序方法
/// <param name="arr">劃分的數組</param>
/// <param name="low">數組低端上標</param>
/// <param name="high">數組高端下標</param>
/// <returns></returns>
public static int Partition(int[] arr, int low, int high)
{
//進行一趟快速排序,返回中心軸記錄位置
// arr[0] = arr[low];
int pivot = arr[low];//把中心軸置於arr[0]
while (low < high)
{
while (low < high && arr[high] >= pivot)
--high;
//將比中心軸記錄小的移到低端
Swap(ref arr[high], ref arr[low]);
while (low < high && arr[low] <= pivot)
++low;
Swap(ref arr[high], ref arr[low]);
//將比中心軸記錄大的移到高端
}
arr[low] = pivot; //中心軸移到正確位置
return low; //返回中心軸位置
}
public static void Swap(ref int i, ref int j)
{
int t;
t = i;
i = j;
j = t;
}
public static void Sort(int[] arr, int low, int high)
{
if (low < high - 1)//當 arr[low,high]為空或只一個記錄無需排序
{
int pivot = Partition(arr, low, high);
Sort(arr, low, pivot - 1);
Sort(arr, pivot + 1, high);
}
}
}
public class Program
{
static void Main(string[] args)
{
int[] arr = new int[] { 20, 41, 27, 14, 16, 1, 8, 55, 9, 35, 22, 14 };
QuickSorter.Sort(arr, 0, arr.Length - 1);
Console.WriteLine("Numbers after quicksort:");
foreach (int i in arr)
{
Console.WriteLine(i);
}
Console.Read();
}
}
}
3.選擇排序
using System;
namespace SelectionSorter
{
/// <summary>
/// 選擇排序(Selection Sort)的基本思想是：每一趟從待排序的記錄中選出關鍵字最小的記錄，順序放在已排好序的子文件的最後，直到全部記錄排序完畢。
/// </summary>
public class SelectionSort
{
public static void Sort(int[] numArray)
{
int min, tmp;
for (int i = 0; i < numArray.Length - 1; i++)
{
min = i;
for (int j = i + 1; j < numArray.Length; j++)
{
if (numArray[j] < numArray[min])
{
min = j;
}
}
tmp = numArray[i];
numArray[i] = numArray[min];
numArray[min] = tmp;
}
}
}
public class Program
{
static void Main(string[] args)
{
int[] arr = new int[] { 20, 41, 27, 14, 16, 1, 8, 55, 9, 35, 22, 14 };
SelectionSort.Sort(arr);
Console.WriteLine("Numbers after selectionsort:");
foreach (int i in arr)
{
Console.WriteLine(i);
}
Console.Read();
}
}
}
4.插入排序
using System;
namespace InsertSorter
{
/// <summary>
/// 插入排序(Insertion Sort)的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對於未排序數據，
/// 在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常采用in-place排序(即只需用到O(1)的額外空間的排序)，
/// 因而在從後向前掃描過程中，需要反復把已排序元素逐步向後挪位， 為最新元素提供插入空間。
/// </summary>
public class InsertSort
{
public static void Sort(int[] numArr)
{
for (int i = 1; i < numArr.Length; i++) //i從1開始
{
int t = numArr[i]; //標志當前未排序數據
int j = i;
while ((j > 0) && (numArr[j - 1] > t))
{
numArr[j] = numArr[j - 1];
j--;
}
numArr[j] = t; //在已排序序列中插入當前值
}
}
}
public class Program
{
static void Main(string[] args)
{
int[] arr = new int[] { 20, 41, 27, 14, 16, 1, 8, 55, 9, 35, 22, 14 };
InsertSort.Sort(arr);
Console.WriteLine("Numbers after insertsort:");
foreach (int i in arr)
{
Console.WriteLine(i);
}
Console.Read();
}
}
}
雖然在實際的項目中，我們的確很少用到這些或其他更高級的算法，但是”算法是程序的靈魂“。雖然算法確實很難，但是”當你用它們巧妙地解決問題的時候，那種純粹的喜悅和快樂是任何不曾體驗過的人所能感受到的“。很不幸，我還沒有體驗幾次這樣的快樂。
