桶排序问题——非对比排序

2020-12-04 09:36

阅读：797

标签：fir 数字排序 sort array 适用于 second namespace ptr clu

题目描述：　　

　　不使用比较排序，实现一个数组排序
　　时间复杂度O(N)，额外空间复杂度O(N)

解题思路：
　　使用桶排序思维，申请一个额外数组，叫桶，用来记录数字出现的次数，然后输出即可，但桶排序一般适用于0-9的元素数字排序，因为此时桶只需申请0-9的空间，若array元素为999，则桶的空间至少得申请0-999，那样就不适用。

　　扩展：使用map来实现桶，那么就可以实现任何数组桶排序功能

代码实现：

 1 #pragma once
 2 
 3 #include  4 #include  5 
 6 using namespace std;
 7 
 8 //使用桶数组
 9 void Test01(const int array[], int N)
10 {
11     int TT[10] = { 0 };
12     for (int i = 0; i i)
13         TT[array[i]]++;
14     for (int i = 0; i 10; ++i)
15         for (int j = 0; j j)
16             cout "  ";
17 
18     cout "*******************"  endl;
19 }
20 
21 
22 //使用map
23 void Test02(const int array[], int N)
24 {
25     mapint, int>M;
26     for (int i = 0; i i)
27         M[array[i]]++;
28 
29     for (auto ptr = M.cbegin(); ptr != M.cend(); ++ptr)
30         for (int j = 0; j second; ++j)
31             cout first "  ";
32     cout "*******************"  endl;
33 
34 
35 
36 }
37 
38 void NoSort()
39 {
40     int arr[] = { 9,1,4,8,5,6,7,1,2,5,4,9,0,6 };
41     Test01(arr, sizeof(arr) / sizeof(arr[0]));
42     Test02(arr, sizeof(arr) / sizeof(arr[0]));
43 
44 }

桶排序问题——非对比排序

标签：fir 数字排序 sort array 适用于 second namespace ptr clu

原文地址：https://www.cnblogs.com/zzw1024/p/10987856.html

上一篇：Spring配置redis

下一篇：CSS标签大全

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：桶排序问题——非对比排序
文章链接：http://soscw.com/index.php/essay/23294.html

亲，登录后才可以留言！

桶排序问题——非对比排序

评论

热门文章

推荐文章

最新文章

置顶文章