对于比较排序,大家如果感兴趣,可以查看我的博客: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 #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, 4, 93, 7, 5, 2, 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, 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; }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。