百度推广要不要建网站,东台网站制作公司,北京海淀建设规划局,公司的网站建设公司网站建设08 基数排序#xff08;Radix Sort#xff09; 基数排序是一种非比较型整数排序算法#xff0c;其原理是将整数按位数切割成不同的数字#xff0c;然后按每个位数分别比较。排序过程是将所有待比较数值统一为同样的数位长度#xff0c;数位较短的数前面补零#xff0c;然… 08 基数排序Radix Sort 基数排序是一种非比较型整数排序算法其原理是将整数按位数切割成不同的数字然后按每个位数分别比较。排序过程是将所有待比较数值统一为同样的数位长度数位较短的数前面补零然后从最低位开始依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。 int getMax(int arr[], int n)
{ int mx arr[0]; for (int i 1; i n; i) if (arr[i] mx) mx arr[i]; return mx;
} void countSort(int arr[], int n, int exp)
{ int output[n]; int i, count[10] {0}; for (i 0; i n; i) count[ (arr[i]/exp)%10 ]; for (i 1; i 10; i) count[i] count[i - 1]; for (i n - 1; i 0; i--) { output[count[ (arr[i]/exp)%10 ] - 1] arr[i]; count[ (arr[i]/exp)%10 ]--; } for (i 0; i n; i) arr[i] output[i];
} void radixsort(int arr[], int n)
{ int m getMax(arr, n); for (int exp 1; m/exp 0; exp * 10) countSort(arr, n, exp);
} 空间效率O(r) 时间效率最好情况O(d(nr)) 平均情况O(d(nr)) 最坏情况O(d(nr)) 稳定性相同元素相对位置变化情况稳定 09 桶排序Bucket Sort 桶排序的原理是将数组分到有限数量的桶中再对每个桶子再分别排序有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序最后将各个桶中的数据有序的合并起来。 排序过程 假设待排序的一组数统一的分布在一个范围中并将这一范围划分成几个子范围也就是桶将待排序的一组数分档规入这些子桶并将桶中的数据进行排序将各个桶中的数据有序的合并起来 void bucketSort(int arr[], int n)
{ vectorfloat b[n]; for (int i0; in; i) { int bi n*arr[i]; b[bi].push_back(arr[i]); } for (int i0; in; i) sort(b[i].begin(), b[i].end()); int index 0; for (int i 0; i n; i) for (int j 0; j b[i].size(); j) arr[index] b[i][j];
} 空间效率O(NM) 时间效率最好情况O(N) 平均情况O(N) 最坏情况O(Nlog2N) 稳定性相同元素相对位置变化情况稳定 转载于:https://www.cnblogs.com/wanghao-boke/p/10424469.html
