【数据结构】非比较排序的算法实现(包括计数排序、计数排序)
发布时间: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; } (编辑:西双版纳站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |