• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]桶排序|Bucketsort

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

1、原理:将数组元素分到有限数量的桶里。每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。

2、桶排序步骤:

(1)、设置一个定量的数组当作空桶。

(2)、遍历序列,并且把元素一个个放到对应的桶中去。

(3)、对每个不是空的桶子进行排序。

(4)、从不是空的桶子里把项目再放回原来的序列中。

3、算法分析:

最坏时间复杂度 :    

平均时间复杂度: ,其中k是桶的数量。 

最坏空间复杂度:

4、最坏情况分析

(1)、当输入均匀分布在一个范围内时,存储桶排序主要是有用的。

(2)、当输入包含几个彼此接近的键(聚类)时,这些元素可能放在同一个桶中,这导致一些桶包含的元素多于平均值。当所有元素都放在一个桶中时,会出现最坏的情况。然后,整体性能将由用于对每个桶进行排序的算法主导。

5、图示元素分布在桶中:

元素在每个桶中排序:

6、数组桶排序:

 

 1 //MARK:桶排序
 2 func bucketSort(_ arr:[Int],_ gap:Int) -> [Int]
 3 {
 4     //1.得到数列的最大值和最小值
 5     let maxNum:Int = arr.max()!
 6     let minNum:Int = arr.min()!
 7     //2.初始化桶数量
 8     let bucketCount:Int = (maxNum - minNum) / gap + 1
 9     //建桶
10     var bucketlist:[[Int]] = [[Int]](repeating:[Int](),count:bucketCount)
11     //3.遍历原始数组,将每个元素放入桶中
12     for i in 0..<arr.count
13     {
14         let index:Int = (arr[i] - minNum) / gap
15         bucketlist[index].append(arr[i])
16     }
17     //4.对每个通内部进行排序
18     for i in 0..<bucketCount {
19         //判断桶是否为空
20         if bucketlist[i].count > 0 {
21             shellSort(&bucketlist[i])
22         }
23     }
24     //5.连接全部桶内元素
25     var arr = [Int]()
26     for i in 0..<bucketCount {
27         let bucket:[Int] = bucketlist[i]
28         //判断桶是否为空
29         if bucket.count > 0 {
30             //数组添加
31             arr += bucket
32         }
33     }
34     return arr
35 }
36 37 //MARK:桶內元素希尔排序
38 func shellSort(_ arr:inout [Int])
39 {
40     var number:Int = arr.count / 2
41     var j:Int = 0
42     var temp:Int = 0
43     while (number >= 1)
44     {
45         for i in number..<arr.count
46         {
47             temp = arr[i]
48             j = i - number
49             //需要注意的是,这里array[j] < temp将会使数组从大到小排列
50             while (j >= 0 && arr[j] > temp)
51             {
52                 arr[j + number] = arr[j]
53                 j = j - number
54             }
55             arr[j + number] = temp
56         }
57         number = number / 2
58     }
59 }

测试:

1 var arr:[Int] = [1,9,2,8,3,7,4,6,5,10,11,12]
2 print(bucketSort(arr,3))
3 //Print [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

 7、链表桶排序:

 1 class Node
 2 {
 3     var key: Int
 4     var next: Node?
 5     init(_ val: Int)
 6     {
 7         self.key = val
 8         self.next = nil
 9     }
10 }
11 
12 //MARK:桶排序
13 func bucketSort(_ arr:[Int],_ gap:Int) -> [Int]
14 {
15     //1.得到数列的最大值和最小值
16     let maxNum:Int = arr.max()!
17     let minNum:Int = arr.min()!
18     //2.初始化桶数量
19     let bucketCount:Int = (maxNum - minNum) / gap + 1
20     //链表第一个节点的key记录当前桶中的数据量
21     var bucketlist:[Node] = [Node](repeating:Node(0), count: bucketCount)
22     for j in 0..<arr.count
23     {
24         let node:Node = Node(0)
25         node.key = arr[j]
26         node.next = nil
27         //计算各元素放入对应桶的编号  自行定义规则
28         let index:Int = (arr[j] - minNum) / gap
29         var p:Node = bucketlist[index]
30         //链表插入排序
31         while (p.next != nil && p.next!.key <= node.key)
32         {
33             p = p.next!
34         }
35         node.next = p.next
36         p.next =  node
37         bucketlist[index].key += 1
38     }
39     //5.连接全部桶内元素
40     var ans = [Int]()
41     var k:Node? = bucketlist[0].next
42     while(k != nil && k!.key > 0)
43     {
44         ans.append(k!.key)
45         k = k!.next
46     }
47     return ans
48 }

测试:

1 var arr:[Int] = [1,9,2,8,3,7,4,6,5,10,11,12]
2 print(bucketSort(arr,3))
3 //Print [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode317.建筑物的最短距离$ShortestDistancefromAllBuildings发布时间:2022-07-13
下一篇:
Swift学习字符串、数组、字典发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap