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

计数排序：

#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数组
????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));//将数组初始化

????/*对要排序的数组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<int>?a?=?{?12,?34,?12222,?4568,?26,?1,?16,?10,?2,?4,?93,?7,?5,?4?};
????CountSort(a);
????Print(a);
????
}


int?main()
{
????TestCountSort();
????system("pause");
????return?0;
}

基数排序：

#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?};

????//处理数组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,?4?};
????RadixSort(a,?sizeof(a)?/?sizeof(a[0]));
????Print(a,sizeof(a)/sizeof(a[0]));

}


int?main()
{
????TestRadixSort();
????system("pause");
????return?0;
}

（编辑：新余站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!