[經典算法]計數排序

概述：

計數排序是一個非基于比較的排序算法，該算法于1954年由 Harold H. Seward 提出。它的優勢在于在對一定範圍内的集合排序時，它的複雜度為Ο(n+k)（其中k是元素的範圍），快于任何比較排序算法。

計數排序本質上是通過計算無序集合中元素出現的次數來決定集合應該如何排序的。

例如一個數組{1, 4, 1, 2, 7, 5, 2}，進行計數排序過程

1、使用Count數組記錄元素次數

Index:     0  1  2  3  4  5  6  7  8  9
Count:     0  2  2  0  1  1  0  1  0  0      

2、調整Count數組，統計元素在以排序數組中的偏移

Index:     0  1  2  3  4  5  6  7  8  9
Count:     0  2  4  4  5  6  6  7  7  7      

3、反向周遊資料，根據元素的偏移把元素放置到以排序集合中，并減少一次計數。

比如最後一個元素2，對應Count中值Count[2]是4，則在Sorted中第4位置放一個元素2。即Sorted[Count[2]-1] = 2;

Index: 0 1 2 3 4 5 6 7 8 9       

Count: 0 2 4 4 5 6 6 7 7 7      

Sorted:- - - 2 - - - - - -      

基本特性：

1、集合中元素可以轉換成整型索引值，且不會沖突。

2、轉換的索引值範圍已知且有限。

3、時間複雜度為O(n+k)，不是基于比較的排序算法，是以效率非常之高。

4、穩定性好

5、需要輔助空間，計數數組和已排序數組

     如果索引值可以直接用元素值，并且不需要考慮相同值元素之間的先後，可以節省“以排序數組”所用的空間，優化代碼參考後面

程式代碼：

#include <gtest/gtest.h>
#include <algorithm>
using namespace std;

// 元素值可以直接用作索引值，并行不考慮相同值元素先後關系
// 這樣可以節省以排序資料的輔助空間
void CountingSort2(int* data, int size, int max)
{
    int* counts = new int[max];
    memset(counts, 0, max * sizeof(int));

    for (int i=0; i<size; ++i)
    {
        counts[data[i]]++;
    }

    int index = 0;
    for (int i=0; i<max; i++)
    {
        while(counts[i]-- > 0)
        {
            data[index++] = i;
        }
    }

    delete[] counts;
}

// 計數排序
int ConvDataToIndex(float data, int max)
{
    return (int)(data * 10);
}

template<typename T, typename F>
void CountingSort(T* data, int size, int max, F conv)
{
    int* counts = new int[max];    //計數數組
    T*   sorted = new T[size];    //排序緩存

    memset(counts, 0, max*sizeof(int));

    for (int i = 0; i<size; ++i)
    {
        counts[conv(data[i], max)]++;
    }

    for (int i = 1; i<max; ++i)
    {
        counts[i] += counts[i-1];
    }

    for (int i = size-1; i >=0; --i )
    {
        int j = --counts[conv(data[i], max)];
        sorted[j] = data[i];
    }

    memcpy(data, sorted, size * sizeof(T));
    delete[] counts;
    delete[] sorted;
}

// 輔助函數
template<typename T>
static void ShowElem(T& val)
{
    cout << val << " ";
}

template<typename T>
static bool Validate(T* data, int len)
{
    for (int i=0; i < len-1; ++i)
    {
        if (data[i] > data[i+1])
        {
            return false;
        }
    }

    return true;
}

//測試代碼
TEST(Algo, tCountSort)
{
    
    float d4[] = {0, 1.2, 3.1, 4.0, 1.5, 2.6, 10.4, 9.7, 8.2};
    CountingSort(d4, 9, 105, ConvDataToIndex);
    for_each(d4, d4+9, ShowElem<float>);
    ASSERT_TRUE(Validate(d4,9));
    cout << endl;

    int d1[] = {2,8,7,1,3,5,6,4};
    CountingSort2(d1, 8, 9);
    for_each(d1, d1+8, ShowElem<int>);    
    ASSERT_TRUE(Validate(d1,8));    
    cout << endl;

    int d2[] = {2};
    CountingSort2(d2, 1, 3);
    for_each(d2, d2+1, ShowElem<int>);
    ASSERT_TRUE(Validate(d2,1));
    cout << endl;

    int d3[] = {2,4,5,6,7,5,2,3,5,7,10,111,2,4,5,6,3,4,5};
    CountingSort2(d3, 19, 112);
    for_each(d3, d3+19, ShowElem<int>);
    ASSERT_TRUE(Validate(d3,19));
    cout << endl;
}      

參考引用：

http://www.geeksforgeeks.org/counting-sort/