1. 冒泡排序
?思想：
- 從現(xiàn)有元素中取出最大的元素，移到相應(yīng)的位置，直到所有元素都就位。
- 通過比較和交換逐步調(diào)整現(xiàn)有序列，最終找出最大元素并使其就位。
?設(shè)計：
? 輸入是待排數(shù)組及其長度，輸出排序后的數(shù)組。
??在冒泡過程中對數(shù)組的有序情況進行檢查，在數(shù)組已經(jīng)有序時便結(jié)束算法。
代碼：
void BubbleSort(int nArray[], int nLength)
{
???? bool bSorted = false;
???
???? if (nArray == NULL)
???????? throw -1;
???
???? if (nLength < 2)
??????? ?return;
???
??? for (int i = nLength; !bSorted && i > 1; i--)
??? {
??????? ?bSorted = true;
???????
???????? for (int j = 1; j < i; j++)
??????? {
???????????? if (nArray[j] < nArray[j-1])
??????????? {
???????????????? int n;
???????????????? n = nArray[j];
???????????????? nArray[j] = nArray[j-1];
???????????????? nArray[j-1] = n;
???????
???????????????? bSorted = false;
???????????? }//if
???????? }
?????}
}
2. 雙向冒泡排序
void BiBubbleSort(int nArray[], int nLength)
{
????int? low, high;
?
????if (nArray == NULL)
???????throw -1;
????if (nLength < 2)
???????returnt;
??? low = 0;
????high = nLength - 1;
??? while (low < high)
?? {
???????int t;
???????t = low;
???????for (int i = low; i < high; i++)
?????? {
?????????? if (nArray[i] > nArray[i+1])
????????? {
????????????? int n;
????????????? n = nArray[i];
????????????? nArray[i] = nArray[i+1];
????????????? nArray[i+1] = n;
????????????? t = i + 1;
????????? }
?????? }
?????? high = t - 1;
????? t = high;
???? ?for (int j = high; j > low; j--)
????? {
????????? if (nArray[j] < nArray[j-1])
?????? ?? {
???????????? int n;
???????????? n = nArray[j];
???????????? nArray[j] = nArray[j-1];
???????????? nArray[j-1] = n;
????????????
???????????? t = j - 1;
????????? }
????? }
???? low = t + 1;
? }//while
}
3. 快速排序
?思想：
?選一個樞軸元素，把待排序列劃分成兩段，前一段不大于樞軸，?后一段不小于樞軸。如果這兩段分別有序，原序列也隨之有序。通過劃分，一個段的排序可以轉(zhuǎn)化為兩個子段的排序，即同樣性質(zhì)但較小規(guī)模的問題。當(dāng)段的長度為1時，本身是有序的，轉(zhuǎn)化可以終止。
設(shè)計：
用一個遞歸函數(shù)來實現(xiàn)快速排序算法，遞歸終止條件是段的長度小于等于1。
一次劃分過程設(shè)計如下：取段的第一個元素為樞軸，從最后一個元素向前與樞軸比較，發(fā)現(xiàn)小于樞軸的元素時，與樞軸交換位置，從第二個元素向后與樞軸比較，這樣兩端是已完成劃分的部分，中間是待劃分的部分，樞軸始終處于中間部分的一端，比較從另一端向該端進行，發(fā)現(xiàn)分類不同的元素就同樞軸交換。隨著比較和交換的進行，中間部分不斷收縮(每次長度縮短1)，當(dāng)收縮到長度為1時，劃分終止。
實現(xiàn)要點：
遞歸函數(shù)的參數(shù)是待排序列及前后邊界。
劃分過程需要用兩個變量記錄中間部分的邊界。
代碼：
void QuickSort(int nArray[], int low, int high)
{
???? int pivot = nArray[low];
???? int?i = low，j = high;
???
???? if (high < low)
???????????return;???
????
???? while (i < j)
???? {
????????? while (i <?j && nArray[j] >= pivot) j--;
????????? if (i < j)?
?????????????? nArray[i++] = nArray[j];
?
????????? while (i <?j && nArray[i] <= pivot) i++;
????????? if (i < j)?
?????????????? nArray[j--] = nArray[i];
???? }
????
???? nArray[i] = pivot;
???
???? QuickSort(nArray, low,?i - 1);
???? QuickSort(nArray,?i + 1, high);
}
測試要點：
- 遞歸終止條件。必須是high < low，而不能是 high?== low。遞歸的終止是很重要的邊界情況，在實現(xiàn)之前有一個概念上的終止條件，但在實現(xiàn)時處理必須準確。終止條件和遞推方式有關(guān)，需要結(jié)合實際的遞推方式來確定。
- 遞歸的遞推方式。
- 分劃的終止條件。分劃過程在i == j時終止，雖然在比較的過程中可能進行交換，但是每次未分劃部分的長度減1，用該長度控制分劃的終止。
- 分劃過程中改變方向時的交接。
算法分析：
假設(shè)原序列有2n個元素，每次分劃把一個段等分成兩段，則經(jīng)過n級遞歸算法終止，每一級遞歸的比較總數(shù)為n, 所以QuickSort()的時間為O(nlog(n))，這是平均情況。當(dāng)原序列本身有序時，QuickSort()出現(xiàn)最壞情況，時間為O(n2)。