加入收藏 | 设为首页 | 会员中心 | 我要投稿 西双版纳站长网 (https://www.0691zz.com.cn/)- 数据计算、IT业界、服务器、教程、云日志!
当前位置: 首页 > 服务器 > 安全 > 正文

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

发布时间:2021-03-31 03:13:06 所属栏目:安全 来源:网络整理
导读:计数排序: #define?_CRT_SECURE_NO_WARNINGS?1#includeiostreamusing?namespace?std;#includeassert.h#includevectorvoid?Print(vectorint??a){????for?(int?i?=?0;?i??a.size();?i++)????{????????cout??a[i]??"??";????}????cout??endl;}void?CountSort(v

计数排序:

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

(编辑:西双版纳站长网)

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

    热点阅读