客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ 1、定义： 计数排序（Counting sort）是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组，其中第i个元素是待排序数组中值等于的元素的个数。然后根据数组来将中的元素排到正确的位置。 2、特征： 当输入的元素是个到之间的整数时，它的运行时间是。计数排序不是比较排序，排序的速度快于任何比较排序算法。 由于用来计数的数组的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序算法中，能够更有效的排序数据范围很大的数组。 3、算法步骤： (1)、找出待排序的数组中最大和最小的元素 (2)、统计数组中每个值为的元素出现的次数，存入数组的第项 (3)、对所有的计数累加（从中的第一个元素开始，每一项和前一项相加） (4)、反向填充目标数组：将每个元素放在新数组的第项，每放一个元素就将减去1 4、Talk is cheap.Show me your code. 1 //MARK:计数排序 2 func countingSort(_ arr:[Int]) -> [Int] 3 { 4 //1.找出待排序的数组中最大和最小的元素 5 let maxNum:Int = arr.max()! 6 let minNum:Int = arr.min()! 7 //初始化一个与arr同样大小的数组 8 var b:[Int] = [Int](repeating: 0, count: arr.count) 9 //k的大小是要排序的数组中最大值和最小值之差 + 1 10 let k:Int = maxNum - minNum + 1 11 var c:[Int] = [Int](repeating: 0, count: k) 12 //2.统计数组中每个值为的元素出现的次数，存入数组的第项 13 for i in 0..<arr.count 14 { 15 //优化减小数组的大小,统计每个元素有几个 16 c[arr[i] - minNum] += 1 17 } 18 //3.对所有的计数累加（从中的第一个元素开始，每一项和前一项相加） 19 for i in 1..<c.count 20 { 21 //前缀和 22 c[i] += c[i-1] 23 } 24 //4.反向填充目标数组 25 for i in (0...arr.count - 1).reversed() 26 { 27 //按存取的方式取出c的元素 28 c[arr[i] - minNum] -= 1 29 b[c[arr[i] - minNum]] = arr[i] 30 } 31 return b 32 } 测试： 1 var arr:[Int] = [1,9,2,8,3,7,4,6,5,10,11,12] 2 print(countingSort(arr)) 3 //Print [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] |
请发表评论