RodneyX

交換排序的基本思想：

每次比較無序表L[0...n-1]中相鄰兩個元素大小，若為逆序則交換

一般常見的交換排序有兩個，一個冒泡排序（非常簡單），一個是快速排序（內部排序平均效率最好的排序算法）

冒泡排序的基本思想：

1. 從前往后，每次比較無序表L[0...n-1]中相鄰兩個元素大小，若為逆序則交換

2. 以結果為非遞減序列為例，每次從前往后對1.中操作進行一輪，則會有一個無序表中的最大值到達最終位置上，因此只需要執行執行n-1次操作1.，并且某次執行若未發生元素交換則表明表已經有序排序完畢

于是有如下實現

void bubble_Sort(int A[], int length)
{
    for (int i = 1; i < length; ++i)
    {
        int flag = 0;
        for (int j = 0; j < length - i; ++j)  // 升序下每趟排序待排序序列中的最大的值會在最終位置上，故j < length - i
        {
            if (A[j] > A[j + 1])
            {
                int swap_val = A[j];
                A[j] = A[j + 1];
                A[j + 1] = swap_val;
                flag = 1;
            }
        }
        if (!flag) // 未發生交換則已經排序完畢
            return;
    }
}

快速排序的基本思想：

1. 對表L[0...n-1]，每次選擇一個表中一個元素作為樞軸（pivot），然后將比pivot小的元素置于pivot元素在表最終位置的左邊（以非遞減的排序結果為例），比pivot大的元素置于pivot元素在表最終位置的右邊（這是快速排序的精髓）

2. 經過1.后，記pivot最終的索引為lo，表被劃分為L[0...i-1]和``L[i+1...n-1]，對這兩個無序表遞歸執行1.，直到遞歸到無序表長為小于等于1，則此時有序，完成排序

對于1.，常用的實現方式是選擇表頭元素作為樞軸，并設lo = 表頭元素的索引，hi = 表位元素的索引

然后從hi開始，如果hi所指元素小于lo，將這個元素移動到lo所指向的位置，反之hi遞減

對于lo的操作類似，只是和hi的操作相反即可，并且讓hi與lo的移動交替進行，當hi == lo時這個位置就是pivot的最終位置

于是我們有如下實現

// cannot be called by user
int _partition(int A[], int lo, int hi)
{
    int pivot = A[lo];
    while (lo < hi)
    {
        while (lo < hi && A[hi] >= pivot)  // 不能采用嚴格不等號，也就是說相等也移動，否則死循環
            --hi;
        A[lo] = A[hi];
        while (lo < hi && A[lo] <= pivot)
            ++lo;
        A[hi] = A[lo];
    }
    A[lo] = pivot;
    return lo;
}

void quick_Sort(int A[], int length)  //這個函數建議按教材來實現，我這個可讀性稍差
{
    if (length <= 1) // 終止條件
        return;
    int pivot = _partition(A, 0, length - 1);
    quick_Sort(A, pivot);
    quick_Sort(A + pivot + 1, length - pivot - 1);
}