个人对MSD基数排序的理解
- 大多数排序算法是比较两个数的大小，而基数排序是分割一个数字比较。学习她会非常有价值的。
- 提取待排序的数字 的最高位，按从小到大0-9，分别放入10个木桶里装入。
- 然后分别再对10个木桶操作 上一步，直到木桶里只有一个数字或者数字相等。
时间复杂度与自己想法
- 基数排序的时间复杂度 o(d(n+r)) ，r为基数，d为位数，并且她是稳定排序
- 多线程奇思妙想：（猜想）
利用此思想，如果排序的数字比较多和大， 我们可以先用 基数排序思想分段 ，现在cpu都是多线程，然后可以在每段上开启线程，同时开启快速排序，最后合并分段的序列。 速度是否会提升，待确定。
c++版本
#include <iostream>
#include <malloc.h>
using namespace std;
int getdigit(int x,int d)
{
int a[] = {1,1,10};
return ((x/a[d]) % 10);
}
void PrintArr(int ar[],int n)///打印数组
{
for(int i = 0; i < n; i++)
cout<<ar[i]<<" ";
cout<<endl;
}
void msdradixSort(int arr[],int begin, int end, int d){
int i, j;
int count[10] = {0};
//分配木桶
int *bucket = (int *) malloc((end-begin+1) * sizeof(int));
//统计各木桶的需要装 元素的个数
for (i = begin; i <= end; i++) {
count[getdigit(arr[i], d)]++;
}
//统计 每一个木桶存放的位置 末位置
for (i = 1; i < 10; i++){
count[i] = count[i] + count[i - 1];
}
///这里从右向左扫，保证稳定性
for (i = end; i >= begin; i--){
j = getdigit(arr[i], d); //求出关键字 12 。 就是j 就是1
bucket[count[j]-1] = arr[i] ;// 放入木桶
count[j]--; //木桶 减少一个位置
}
//收集木桶数据
for (i = begin,j = 0; i <= end; i++ ,j++){
arr[i] = bucket[j];
}
free(bucket);
for (i = 0; i < 10; i++) {
int p1 = begin + count[i]; //第i个桶的左边界
int p2 = begin + count[i+1]-1; //第i个马桶的右边界
if (p2>p1 && d>1){ //木桶里有俩参数以上，且d>1
msdradixSort(arr, p1, p2, d-1);
}
}
}
int main(){
int a[] = {12,14,54,5,6,3,9,8,47,89,89};
int len = sizeof(a)/sizeof(int);
msdradixSort(a, 0, len-1, 2);
PrintArr(a, len);
return 0;
}
swift 版本
过两天再写， 先去学习总结堆排序了。
-
看我那么可爱n(≧▽≦)n
- 关注我的微薄 (梁同桌)：http://weibo.com/tongrenyinsheng
- 个人博客： http://www.liangtongzhuo.com
- ios 个人写的app （同人音声）ASMR音乐
