依舊的博客

1. 從現有元素中取出最大的元素，移到相應的位置，直到所有元素都就位。
2. 通過比較和交換逐步調整現有序列，最終找出最大元素并使其就位。

?設計：

? 輸入是待排數組及其長度，輸出排序后的數組。
??在冒泡過程中對數組的有序情況進行檢查，在數組已經有序時便結束算法。

代碼：

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. 快速排序

?思想：

?選一個樞軸元素，把待排序列劃分成兩段，前一段不大于樞軸，?后一段不小于樞軸。如果這兩段分別有序，原序列也隨之有序。通過劃分，一個段的排序可以轉化為兩個子段的排序，即同樣性質但較小規模的問題。當段的長度為1時，本身是有序的，轉化可以終止。

設計：

用一個遞歸函數來實現快速排序算法，遞歸終止條件是段的長度小于等于1。
一次劃分過程設計如下：取段的第一個元素為樞軸，從最后一個元素向前與樞軸比較，發現小于樞軸的元素時，與樞軸交換位置，從第二個元素向后與樞軸比較，這樣兩端是已完成劃分的部分，中間是待劃分的部分，樞軸始終處于中間部分的一端，比較從另一端向該端進行，發現分類不同的元素就同樞軸交換。隨著比較和交換的進行，中間部分不斷收縮(每次長度縮短1)，當收縮到長度為1時，劃分終止。

實現要點：

遞歸函數的參數是待排序列及前后邊界。
劃分過程需要用兩個變量記錄中間部分的邊界。

代碼：

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);
}

測試要點：

1. 遞歸終止條件。必須是high < low，而不能是 high?== low。遞歸的終止是很重要的邊界情況，在實現之前有一個概念上的終止條件，但在實現時處理必須準確。終止條件和遞推方式有關，需要結合實際的遞推方式來確定。
2. 遞歸的遞推方式。
3. 分劃的終止條件。分劃過程在i == j時終止，雖然在比較的過程中可能進行交換，但是每次未分劃部分的長度減1，用該長度控制分劃的終止。
4. 分劃過程中改變方向時的交接。

算法分析：

假設原序列有2ⁿ個元素，每次分劃把一個段等分成兩段，則經過n級遞歸算法終止，每一級遞歸的比較總數為n, 所以QuickSort()的時間為O(nlog(n))，這是平均情況。當原序列本身有序時，QuickSort()出現最壞情況，時間為O(n²)。