[Swift]计数排序 | Counting sort【用微信查看本文链接可查看到引用图片】

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

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.

//MARK:计数排序
func countingSort(_ arr:[Int]) -> [Int]
{
    //1.找出待排序的数组中最大和最小的元素
    let maxNum:Int = arr.max()!
    let minNum:Int = arr.min()!
    //初始化一个与arr同样大小的数组
    var b:[Int] = [Int](repeating: 0, count: arr.count)
    //k的大小是要排序的数组中最大值和最小值之差 + 1
    let k:Int = maxNum - minNum + 1
    var c:[Int] = [Int](repeating: 0, count: k)
    //2.统计数组中每个值为的元素出现的次数，存入数组的第项
    for i in 0..<arr.count
    {
        //优化减小数组的大小,统计每个元素有几个
        c[arr[i] - minNum] += 1
    }
    //3.对所有的计数累加（从中的第一个元素开始，每一项和前一项相加）
    for i in 1..<c.count
    {
        //前缀和
        c[i] += c[i-1]
    }
    //4.反向填充目标数组
    for i in (0...arr.count - 1).reversed()
    {
        //按存取的方式取出c的元素
       c[arr[i] - minNum]  -= 1
        b[c[arr[i] - minNum]] = arr[i]
    }
    return b
}

测试：

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