清風竹林

冒泡和選擇排序該被踢出教材了(轉)

文章源于csdn的一篇帖子，原地址：http://topic.csdn.net/u/20100805/20/231B9356-847D-4FE9-87BA-2A2A3C55CA76.html

非常汗顏，樓主所提到的一些方法，像鴿巢排序與梳排序的名字我都沒聽說過，故摘抄至此，共勉之！

--------------------------------------------------------------------------------------
實用排序算法（復雜度小于等于O(n^2)）中效率最低但實現并不是最簡單的的兩個，C、C++教材卻總喜歡拿來大講特講，非常不利于初學者養成“程序效率”的思維。

實際上，各種排序算法里，除了堆排序實現較為復雜外，從代碼量的角度，大多數算法都不比冒泡、選擇算法復雜多少。

舉幾個高速的排序算法的例子，這些才適合進入教材

鴿巢排序，排序字節串、寬字節串最快的排序算法，計數排序的變種（將計數緩沖區大小固定，少一次遍歷開銷），速度是STL中std::sort的20多倍，更重要的是實現極其簡單！缺點是需要一個size至少等于待排序數組取值范圍的緩沖區，不適合int等大范圍數據

C/C++ code

void PigeonholeSort(BYTE *array, int length)
{
    int b[256] = {0};
    int i,k,j = 0;
    for(i=0; i<length; i++)
        b[array[i]]++;
    for(i=0; i<256; i++)
        for(k=0; k<b[i]; k++)
            array[j++] = i;
}

多一次遍歷的計數排序，排序字節串的話速度約是鴿巢排序的一半

C/C++ code

void CountingSort(BYTE *array, int length)
{
    int t;
    int i, z = 0;
    BYTE min,max;
    int *count;
    min = max = array[0];
    for(i=0; i<length; i++)
    {
        if(array[i] < min)
            min = array[i];
        else if(array[i] > max)
            max = array[i];
    }
    count = (int*)malloc((max-min+1)*sizeof(int));
    for(i=0; i<max-min+1; i++)
        count[i] = 0;
    for(i = 0; i < length; i++)
        count[array[i]-min]++;

    for(t = 0; t <= 255; t++)
        for(i = 0; i < count[t-min]; i++)
            array[z++] = (BYTE)t;
    free(count);
}

快速排序，快排最標準的遞歸實現，速度約是std::sort的一半

C/C++ code

void swap(BYTE *a,BYTE *b)
{
    BYTE tmp;
    if ( a != b )
    {
        tmp = *a;
        *a = *b;
        *b = tmp;
    }
}

int partition(BYTE *arr,int left, int right)
{
    int i = left - 1, j = right;
    BYTE v = arr[right];
    while(1)
    {
        while(arr[++i] < v);
        while(arr[--j] > v)
            if(j == 1)
                break;
        if(i >= j)
            break;
        swap(&arr[i],&arr[j]);
    }
    swap(&arr[i],&arr[right]);
    return i;
}

void quicksort(BYTE *arr, int left, int right)
{
    if (left < right)
    {
        int i = partition(arr,left,right);

        quicksort(arr,left,i-1);
        quicksort(arr,i+1,right);
    }
}

void QuickSort(BYTE *array,int length)
{
    quicksort(array,0,length-1);
}

這是速度與std::sort相當的三路劃分快排

C/C++ code

void swap(BYTE *a,BYTE *b)
{
    BYTE tmp;
    if ( a != b )
    {
        tmp = *a;
        *a = *b;
        *b = tmp;
    }
}

void quicksort(BYTE *arr, int left, int right)
{
    if (left < right)
    {
        BYTE v = arr[right];
        int i = left - 1,j = right,p = left - 1,q = right,k=0;
        while (1)
        {
            while (arr[++i] < v);
            while (arr[--j] > v)
                if(j==left)
                    break;
            if (i >= j)
                break;
            swap(&arr[i], &arr[j]);
            if(arr[i] == v)
            {
                p++;
                swap(&arr[p],&arr[i]);
            }
            if(arr[j] == v)
            {
                q--;
                swap(&arr[q],&arr[j]);
            }
        }
        swap(&arr[i],&arr[right]);
        j = i - 1;
        i++;
        for(k=left; k<=p; k++,j--)
            swap(&arr[k],&arr[j]);
        for(k=right-1; k>=q; k--,i++)
            swap(&arr[k],&arr[i]);
        quicksort(arr,left,j);
        quicksort(arr,i,right);
    }
}

void QuickSort(BYTE *array,int length)
{
    quicksort(array,0,length-1);
}

相當簡單的梳排序，效率是std::sort的三分之一

C/C++ code

void CombSort(BYTE *arr, int size)
{
    UINT gap = size, swapped = 1, i = 0;
    BYTE swap = 0;
    while ((gap > 1) || swapped)
    {
        if (gap > 1)
            gap = gap / 1.3;
        swapped = 0; 
        i = 0;
        while ((gap + i) < size)
        {
            if (arr[i] - arr[i + gap] > 0)
            {
                swap = arr[i];
                arr[i] = arr[i + gap];
                arr[i + gap] = swap;
                swapped = 1;
            }
            ++i;
        }
    }
}

LSD基數排序，與std::sort速度相當，但是需要一個與輸入緩沖一樣大的緩沖區

C/C++ code

#define R 256

#define digit(a, d)    ( a >> 8*d )

static BYTE *aux;

void radix_sort(BYTE *arr, int left, int right)
{
    if(left < right)
    {
        int d = 0;
        for(d=3; d>=0; d--)
        {
            int i=0, j=0, count[R+1];
            for(j=0; j<R; j++)
                count[j] = 0;
            for(i=left; i<=right; i++)
                count[digit(arr[i],d) + 1]++;
            for(j=1; j<R; j++)
                count[j] += count[j-1];
            for(i=left; i<=right; i++)
                aux[count[digit(arr[i],d)]++] = arr[i];
            for(i=left; i<=right; i++)
                arr[i] = aux[i-1];
        }    
    }
}

void RadixSort(BYTE *array,int length)
{
    aux = (BYTE*)malloc(length);
    radix_sort(array,0,length-1);
    free(aux);
}

歸并排序，效率越是std::sort的六分之一，通常的實現是遞歸，但和快排不同，歸并改循環極其容易

C/C++ code

void merge(BYTE *array, int low, int mid, int high)
{
    int i, k;
    BYTE *temp = (BYTE *) malloc(high-low+1);
    int begin1 = low;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = high;

    for (k = 0; begin1 <= end1 && begin2 <= end2; ++k)
        if(array[begin1]<array[begin2])
            temp[k] = array[begin1++];
        else
            temp[k] = array[begin2++];    
    while(begin1<=end1)
        temp[k++] = array[begin1++];
    while(begin2<=end2)
        temp[k++] = array[begin2++];
    for (i = 0; i < (high-low+1); i++)
        array[low+i] = temp[i];
    free(temp);
}

void merge_sort(BYTE *array, UINT first, UINT last)
{
    UINT mid,i;
    for(mid=1; mid<=last-first; mid += mid)
        for(i=first; i<=last-mid; i+=mid+mid)
            merge(array,i,i+mid-1,min(i+mid+mid-1,last));
}

void MergeSort(BYTE *array, UINT length)
{
    merge_sort(array,0,length-1);
}

posted on 2010-11-25 09:59 李現民 閱讀(902) 評論(2)  編輯 收藏 引用 所屬分類: 絕對盜版 、算法為魂