【数据结构】非比较排序的算法实现（包括计数排序、计数排序）

对于比较排序，大家如果感兴趣，可以查看我的博客：http://10740184.blog.51cto.com/10730184/1774508

计数排序

思路：

我们假设升序排序
排序序列为2000，2001，3000，4000
遍历序列，取出最小值min，最大值max，开辟一个空间为max-min的空间大小的数组，遍历数组a将排序序列a中的每个元素出现的次数放在数组count的每个a[i]-min处。就是说，2000出现一次了，把次数1放在2000-2000位置处，2001出现的次数放在2001-2000位置上，3000出现的次数放在3000-2000位置上，4000出现的次数放在4000-2000位置上，5000出现的次数放在5000-2000位置上。后面遇到相同元素了，那将该位置处的次数加加就统计出每个元素的次数了。
这样，对于数组count，里面放的元素就是序列a的次数，count的下标就是a的元素。
往出来取元素的过程，就是拿出排序好的序列的过程。每次从数组count里拿出下标，放回去就可以了。如果此时count中的元素大于1，说明排序序列a有重复元素，那我们多拿几次就行了。

代码实现：

#define _CRT_SECURE_NO_WARNINGS 1#includeusing namespace std;#include#includevoid Print(vector  a){    for (int i = 0; i < a.size(); i++)    {        cout << a[i] << "  ";    }    cout << endl;}void CountSort(vector& a){    int max = a[0];    int min = a[0];    //找出序列的最大值与最小值，开辟max-min+1个空间大小的count数组    for (int i = 1; i < a.size(); i++)    {        if (maxa[i])            min = a[i];    }    int* count = new int[max - min + 1];        memset(count, 0, (max - min + 1) * sizeof(int));//将数组初始化    /*对要排序的数组a进行个数统计，a数组的元素i就放在count数组的i-min处，    而不是i处。因为：若序列为1000  2000 3000，开辟的count从下标0开始，就将1000放于count的1000-1000=0处*/    for (int i = 0; i < a.size(); i++)    {        count[a[i]-min]++;    }    //将count数组往回去拿，i+min代表还原下标    int j = 0;    for (int i = 0; i < max - min + 1; i++)    {        while (count[i]>0)//此时该数重复n次，那就将该数拿回去n次        {            a[j++] = i + min;            count[i]--;        }            }    }void TestCountSort(){    vector a = { 12, 34, 12222, 4568, 26, 1, 16, 10, 2, 4, 4, 93, 7, 5, 2, 4 };    CountSort(a);    Print(a);    }int main(){    TestCountSort();    system("pause");    return 0;}

基数排序：

#define _CRT_SECURE_NO_WARNINGS 1#includeusing namespace std;#includevoid Print(int*  a,int size){    for (int i = 0; i < size; i++)    {        cout << a[i] << "  ";    }    cout << endl;}int MaxRadix(int* a, int size){    int radix = 10;    int count = 1;    int i = 0;    for (int i = 0; i radix)        {            radix *= 10;            count++;        }    }        return count;}void _PartRadix(int* a, int size,int divisor){    int count[10] = { 0 };    //处理数组count，统计每个数据的个、十、百等位出现的个数    for (int i = 0; i < size; i++)    {        int num = a[i] / divisor;        count[num % 10]++;    }    //处理数组start，统计每个元素的起始位置    int start[10] = { 0 };    for (int i = 1; i < 10; i++)    {        start[i] = start[i - 1] + count[i - 1];    }    //遍历数组a,将这些元素放在tmp的计算好的位置上    int* tmp = new int[size];    for (int i = 0; i < size; i++)    {        int num = a[i] / divisor;        tmp[start[num % 10]++] = a[i];//若该位有重复数，则加加坐标向起始位置的后面放即可    }    //拷回个位或十位或百位排序好的数组，开始下一个位的排序    for (int i = 0; i < size; i++)    {        a[i] = tmp[i];    }}void RadixSort(int* a, int size){    assert(a);    for (int i = 1; i <= MaxRadix(a, size);i++)    {        int divisor = 1;//获得除数，便于依次得到数据个位、十位、百位……        int k = i;        while (--k)        {            divisor *= 10;        }        _PartRadix(a, size, divisor);    }}void TestRadixSort(){    int a[] = { 12, 34, 12222, 4568, 26, 1, 16, 10, 2, 4, 4, 93, 7, 5, 2, 4 };    RadixSort(a, sizeof(a) / sizeof(a[0]));    Print(a,sizeof(a)/sizeof(a[0]));}int main(){    TestRadixSort();    system("pause");    return 0;}