【數(shù)據(jù)結(jié)構(gòu)】非比較排序的算法實現(xiàn)（包括計數(shù)排序、計數(shù)排序）

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

計數(shù)排序

思路：

我們假設(shè)升序排序
排序序列為2000，2001，3000，4000
遍歷序列，取出最小值min，最大值max，開辟一個空間為max—min的空間大小的數(shù)組，遍歷數(shù)組a將排序序列a中的每個元素出現(xiàn)的次數(shù)放在數(shù)組count的每個a[i]-min處。就是說，2000出現(xiàn)一次了，把次數(shù)1放在2000-2000位置處，2001出現(xiàn)的次數(shù)放在2001-2000位置上，3000出現(xiàn)的次數(shù)放在3000-2000位置上，4000出現(xiàn)的次數(shù)放在4000-2000位置上，5000出現(xiàn)的次數(shù)放在5000-2000位置上。后面遇到相同元素了，那將該位置處的次數(shù)加加就統(tǒng)計出每個元素的次數(shù)了。
這樣，對于數(shù)組count，里面放的元素就是序列a的次數(shù)，count的下標(biāo)就是a的元素。
往出來取元素的過程，就是拿出排序好的序列的過程。每次從數(shù)組count里拿出下標(biāo)，放回去就可以了。如果此時count中的元素大于1，說明排序序列a有重復(fù)元素，那我們多拿幾次就行了。

代碼實現(xiàn)：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

#include<assert.h>
#include<vector>

void Print(vector<int>  a)
{
    for (int i = 0; i < a.size(); i++)
    {
        cout << a[i] << "  ";
    }
    cout << endl;
}


void CountSort(vector<int>& a)
{
    int max = a[0];
    int min = a[0];

    //找出序列的最大值與最小值，開辟max-min+1個空間大小的count數(shù)組
    for (int i = 1; i < a.size(); i++)
    {
        if (max<a[i])
            max = a[i];
        if (min>a[i])
            min = a[i];
    }
    int* count = new int[max - min + 1];
    
    memset(count, 0, (max - min + 1) * sizeof(int));//將數(shù)組初始化

    /*對要排序的數(shù)組a進(jìn)行個數(shù)統(tǒng)計，a數(shù)組的元素i就放在count數(shù)組的i-min處，
    而不是i處。因為：若序列為1000  2000 3000，開辟的count從下標(biāo)0開始，就將1000放于count的1000-1000=0處*/
    for (int i = 0; i < a.size(); i++)
    {
        count[a[i]-min]++;
    }

    //將count數(shù)組往回去拿，i+min代表還原下標(biāo)
    int j = 0;
    for (int i = 0; i < max - min + 1; i++)
    {
        while (count[i]>0)//此時該數(shù)重復(fù)n次，那就將該數(shù)拿回去n次
        {
            a[j++] = i + min;
            count[i]--;
        }
        
    }
    
}


void TestCountSort()
{
    vector<int> 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;
}

基數(shù)排序：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

#include<assert.h>


void 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<size; i++)
    {
        while (a[i] > radix)
        {
            radix *= 10;
            count++;
        }
    }
    
    return count;
}


void _PartRadix(int* a, int size,int divisor)
{
    int count[10] = { 0 };

    //處理數(shù)組count，統(tǒng)計每個數(shù)據(jù)的個、十、百等位出現(xiàn)的個數(shù)
    for (int i = 0; i < size; i++)
    {
        int num = a[i] / divisor;
        count[num % 10]++;
    }

    //處理數(shù)組start，統(tǒng)計每個元素的起始位置
    int start[10] = { 0 };
    for (int i = 1; i < 10; i++)
    {
        start[i] = start[i - 1] + count[i - 1];
    }

    //遍歷數(shù)組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];//若該位有重復(fù)數(shù)，則加加坐標(biāo)向起始位置的后面放即可
    }

    //拷回個位或十位或百位排序好的數(shù)組，開始下一個位的排序
    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;//獲得除數(shù)，便于依次得到數(shù)據(jù)個位、十位、百位……
        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;
}