关于稳定性计数排序的研究

一、介绍

我们一开始接触的排序算法大都是如冒泡排序、插入排序和选择排序这类的基于比较的排序算法，这类基于比较的排序算法的时间复杂度限制在了$O(nlogn)$。那么有没有时间复杂度更优的排序算法呢，当然是有的，有这么一些算法不需要通过比较就进行排序，如计数排序、桶排序和基数排序，这些算法牺牲了空间复杂度换取了时间复杂度。在本文中，我们主要研究的是计数排序及其的排序稳定性。

二、算法介绍

计数排序是一种非基于比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的算法复杂度为$O(n+k)$，其中k是整数的范围，此时计数排序快于任何比较排序算法。假定给定的排序数组为A，在计数排序中我们定义一个大小为数组A中最大值减去最小值的值的数组B，该数组B就是计数排序的关键，总的来说这个数组B的下标对应要求排序数组A中的元素值，而该数组B中的元素对应相应元素在数组A中出现次数的信息。定义完了数组B之后，我们该如何在数组B中记录信息来完成对于数组A的排序呢？这里的操作方式就涉及了计数排序的算法稳定性的问题，算法的稳定性是指相同大小的元素在经过排序后其相对位置不发生改变。

我们首先介绍一下不稳定的排序方式，我们遍历数组A中的元素，对于相应数组B下标的元素数值加1，那么我们就记录下了A中各个元素的出现次数。排序的过程就是我们新建一个空的数组，正序遍历数组B，发现一个元素值不为空，就往空的数组中加入该下标对应的大小的A中元素，之后B相应的元素减1，循环往复直到该元素变为1，下标加一进行下一次查找，直到B中元素全为0。我们可以很容易地发现，这种算法没有考虑相同大小元素原先的位置关系，排序得到的结果原本相同大小的元素的相对位置关系可能是错误的，因此这是一种不稳定的排序方式，那么怎么才能做到保证稳定性呢？

其实很简单，我们只需要在记录数组A中元素信息的数组B中加入记录相同大小元素的位置关系的信息就可以了。我们在上述不稳定排序给数组B赋值的基础上，使B中所有元素的值都等于其自身加上所有下标小于它元素的值，这相当于是记录了不同大小元素在排序完的数组中的位置。之后为了保证稳定性，也就是使相同大小元素的相对位置不发生改变，我们倒着遍历数组A中的下标，对于A中的元素找到数组B中其排序完时应所处的位置，找到后将数组B中相应元素的值减去1，这就实现了排序的稳定性。

三、代码实现

本文使用python实现了两种计数排序，分别定义了两种函数，其中counting_sort_unstable为不稳定的计数排序，counting_sort为稳定的计数排序，最终给出一个列表进行测试。我用这个例子解释一下为什么稳定的计数排序要倒序遍历数组A，可以发现A中有两个5，而通过计算可以发现在遍历开始前数组B中5对应的元素值为9，那么我们倒着遍历数组A，找到了下标较大的那个5，将其放在了SA的下标8的位置，此时数组B中的5对应的元素值减1变为8，而我们继续遍历会遍历到另一个下标较小的5，此时将其放在SA中下标为7的位置，可见如果顺着遍历就无法实现该算法的稳定性。

#不稳定的计数排序
def counting_sort_unstable(A):
    if A==[]:
        return []
    
    lenA=len(A)
    maxA=max(A)
    minA=min(A)
    SA=[]
    B=[0 for i in range(minA,maxA+1)]
    
    for num in A:
        B[num-minA]+=1
    for i in range(len(B)):
        while B[i]>0:
           SA.append(i+minA)
           B[i]-=1
    return SA

#稳定的计数排序
def counting_sort(A):
    if A==[]:
        return []
    
    lenA=len(A)
    maxA=max(A)
    minA=min(A)
    SA=[0 for i in range(len(A))]
    B=[0 for i in range(minA,maxA+1)]
    
    for num in A:
        B[num-minA]+=1
    for i in range(1,len(B)):
        B[i]=B[i]+B[i-1]
    for i in reversed(range(0,len(A))): #reversed表示逆序遍历，为了使排序稳定
        SA[B[A[i] - minA]-1] = A[i]#-1是因为下标从0开始的
        B[A[i] - minA] -= 1 #每归位一个元素，就少一个元素

    return SA

四、结论

在本文中，我实现了计数排序并且研究了稳定的计数排序和不稳定的计数排序，我总结得出计数排序的本质是记录数组的元素的位置信息来将其进行重构，而为了实现稳定的计数排序其本质就是不光要记录不同大小元素的位置信息还要记录相同大小元素的位置信息。