客服电话
APP下载
迪恩网络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]
|
请发表评论