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