算法導論（3） 快速排序、計數排序、基數排序

1.快速排序

快速排序也采用了分治思想：

• 分解：數組A[p..r]劃分為兩個可能為空的子數組A[p..q-1]和A[q+1..r]，前者均小于等于A[q]，後者均大于等于A[q]。
• 解決：遞歸調用，對兩個子數組繼續采用快速排序的方法。
• 合并：數組是原址操作，不需要合并。

因為看過好多次快速排序的實作方式，是以學習了多種快速排序的實作方式，不過算法導論上的方法QuickSort2更容易了解以及記憶。其實隻要會一種可以熟練應用就可以了。

template<class T>
void QuickSort(T a[], int left, int right)
{
    T key = a[(left + right) / ];
    T temp=;
    int l, r;
    l = left;
    r = right;
    while (l< r)
    {
        while (a[r] > key){
            r--;
        }
        while(a[l]<key){
            l++;
        }
        if (l<=r){
            temp = a[r];
            a[r] = a[l];
            a[l] = temp;
            r--;
            l++;
        }
        if (l == r){
            l++;
        }
    }
        if (left < r)
        {
            QuickSort(a, left, l-);
        }
        if (right >l)
        {
            QuickSort(a, r+, right);
        }

}

template<class T>
void QuickSort2(T a[], int left, int right)
{
    T temp, x = a[right];
    int i,j,q;
    if (left < right){
        i = left - ;
        for (j = left; j < right; j++)
        {
            if (a[j] <= x)
            {
                i += ;
                temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
        temp = a[right];
        a[right] = a[i + ];
        a[i + ] = temp;
        q = i + ;
        QuickSort2(a, left, q - );
        QuickSort2(a, q + , right);
    }
}
template<class T>
void QuickSort3(T a[], int left, int right)
{
    T temp, x = a[left];
    int i, j, q;
    if (left < right){
        i = right+ ;
        for (j = right; j > left; j--)
        {
            if (a[j] >= x)
            {
                i -= ;
                temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
        temp = a[left];
        a[left] = a[i -];
        a[i - ] = temp;
        q = i - ;
        QuickSort2(a, left, q - );
        QuickSort2(a, q + , right);
    }
}

template<class T>
void QuickSort4(T a[], int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int first = left;
    int last = right;
    int key = a[first];

    while (first < last)
    {
        while (first < last && a[last] >= key)
        {
            --last;
        }

        a[first] = a[last];

        while (first < last && a[first] <= key)
        {
            ++first;
        }

        a[last] = a[first];

    }
    a[first] = key;
    QuickSort4(a, left, first - );
    QuickSort4(a, first + , right);
}
           

快速排序的運作時間依賴于劃分是否平衡，如果平衡，其性能與歸并排序一樣，如果不平衡，其性能接近于插入排序。最壞情況下，子問題分别包含n-1和0個元素，其運作時間時O(n^2)，性能還不如插入排序，因為假如數組已有序，插入排序O(n)，而快速排序還是O(n^2)。最好情況下為Θ(nlog⁡n)。

快速排序的平均運作時間更接近與最好情況，而非最壞情況，即使每次劃分的比例都是9:1，看似很不平衡，但其時間複雜度仍是O(nlog⁡n)。

目前為止這幾種排序方法都是通過元素之間的比較進行排序的，是以被稱為比較排序，在最壞情況下，任何比較排序算法都需要做Ω(nlog⁡n)次比較。是以歸并排序和堆排序是漸進最優的。但快速排序通常是實際應用排序中最好的選擇，是以其平均性能非常好。期望時間複雜度為Θ(nlog⁡n)，并且Θ(nlog⁡n)其中隐含的常數因子非常小，能夠進行原址排序。

2.計數排序

假設n個輸入元素中每一個都是在0到k區間的一個整數，其中k為某個整數。計數排序的基本思想是，對一個輸入元素x，确定小于x的元素個數，利用這一資訊将其放在對應的輸出位置上。

void CountSort(int a[], int b[], int n,int k)
{
    vector<int> c;
    c.resize(k);
    for (int i = ; i < k; i++)
    {
        c[i] = ;
    }
    //記錄某個元素出現了幾次
    for (int j = ; j < n; j++)
    {
        c[a[j]] += ;
    }
    //累加，記錄某個元素應該出現在哪個位置上
    for (int i = ; i < k; i++)
    {
        c[i] += c[i - ];
    }
    //将原數組中元素放到對應的位置上，c數組減一是為處理有相同值的情況
    for (int j = n-; j>=; j--)
    {
        b[c[a[j]]-] = a[j];
        c[a[j]] -= ;
    }
}
           

總得時間代價是Θ(k+n)，實際工作中，如果k=O(n)時，一般會采用計數排序，運作時間為Θ(n)。計數排序是穩定的，具有相同值的元素在輸入輸出數組中的相對位置時一樣的。個人感覺上隻能用來處理整數排序，而且運作時間要取決于k值的大小。

3.基數排序

通過對數值一位一位（不是二進制是十進制）比較而達到排序的目的，通常采用按最低有效位來排序。一位數的排序算法必須是穩定的。感覺上也是針對整數的排序，但應該可以改寫成針對其他類型資料的排序，時間複雜度上也可以達到線性的時間代價。

//求資料的最大位數
int maxbit(int data[], int n) 
{
    //儲存最大的位數
    int d = ; 
    int p = ;
    for (int i = ; i < n; i++)
    {
        while (data[i] >= p)
        {
            p *= ;
            d++;
        }
    }
    return d;
}
//基數排序
void radixsort(int data[], int n) 
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    //計數器
    int *count = new int[];
    int i, j, k;
    int radix = ;
    //進行d次排序
    for (i = ; i <= d; i++) 
    {
        //計數排序
        for (j = ; j < ; j++)

            count[j] = ; 
        for (j = ; j < n; j++)
        {
            k = (data[j] / radix) % ; 
            count[k]++;
        }
        for (j = ; j < ; j++)
            count[j] = count[j - ] + count[j]; 
        for (j = n - ; j >= ; j--) 
        {
            k = (data[j] / radix) % ;
            tmp[count[k] - ] = data[j];
            count[k]--;
        }
        for (j = ; j < n; j++) 
            data[j] = tmp[j];
        radix = radix * ;
    }
    delete[]tmp;
    delete[]count;
}
           

4.桶排序

算法導論中講述的是假設要排序的數組均勻、獨立分布在[0,1)之間。然後将[0,1)區間劃分為n個大小相同的區間，稱為桶，然後先對每個桶中的元素進行排序，最後按照次序将桶中元素列出即可。時間複雜度也是線性時間。

感覺類似于基數排序，但是是按照最高位進行排序，然後把相同最高位的分别進行排序，最後按照次序列出。這也說明基數排序也是可以修改為對浮點數等類型進行排序。這兩種算法的基本思想就是一位一位進行排序，而書中針對一位數排序時，基數排序是讓采用穩定的排序方法，而桶排序采用的是插入排序。這幾種排序方法均可以線上性時間内完成。