Day-13 线性时间演算法 : Counting sort

Counting sort

Input :
Output :
Aux(auxiliary) array :

Counting sort假设一个阵列中有个整数，每一个整数都是在0到k范围内。

对於每一个输入的元素x，确认小於x的元素个数，就可以把x放在阵列中正确的位置上了

COUNTING-SORT(A, B, k)
    let C[0...k] be a new array
    for i = 0 to k
        C[i] = 0
    for j = 1 to A.length
        C[A[j]] = C[A[j]] + 1
    //C[i] now contains the number of elements equal to i.
    for i = 1 to k
        C[i] = C[i] + C[i - 1]
    //C[i] now contains the number of elements less than or equal to i.
    for j = A.length downto 1
        B[C[A[j]]] = A[j]
        C[A[j]] = C[A[j]] - 1

Example:

A = 4,1,3,4,3    C = 0,0,0,0
i = 1,2,3,4,5    i = 1,2,3,4(A阵列中最大值为4，因此k = 4)
___________________________________________________
A = 4,1,3,4,3    C = 0,0,0,1
    ^
    j            从A[0]开始走访，发现出现4，因此在C[4]的地方加1，表示4出现过一次
___________________________________________________
A = 4,1,3,4,3    C = 1,0,0,1
      ^
      j
___________________________________________________
A = 4,1,3,4,3    C = 1,0,1,1
        ^
        j
___________________________________________________
A = 4,1,3,4,3    C = 1,0,1,2
          ^
          j
___________________________________________________
A = 4,1,3,4,3    C = 1,0,2,2
            ^
            j
___________________________________________________
接着，为了方便演示，我们产生出一个新的阵列C'
C = 1,0,2,2
C' = 1,0+1,2+0+1,2+2+0+1

阵列C'表示和前一个数字的加总
C' = 1,1,3,5
C'[1]意义为有1个数字小於等於1
C'[2]意义为有1个数字小於等於2
C'[3]意义为有3个数字小於等於3
C'[4]意义为有5个数字小於等於4

C会被C'所取代
___________________________________________________
接着将元素依序放入B，产生出完成排序的阵列
先取出A的最後一个元素A[j]，并看到C[A[j]]，也就是在计数器中对应的数值，
这个数值表示A[j]在B阵列中的位置，将该数值放到B阵列中
    A = 4,1,3,4,3    C = 1,1,3,5     B = 0,0,3,0,0
index = 1 2 3 4 5        1 2 3 4         1 2 3 4 5
                ^            ^               ^
                j           A[j]          C[A[j]]
___________________________________________________
    A = 4,1,3,4,3    C = 1,1,2,5     B = 0,0,3,0,4
index = 1 2 3 4 5        1 2 3 4         1 2 3 4 5
              ^                ^                 ^
              j               A[j]            C[A[j]]
___________________________________________________
    A = 4,1,3,4,3    C = 1,1,2,4     B = 0,3,3,0,4
index = 1 2 3 4 5        1 2 3 4         1 2 3 4 5
            ^                ^             ^  
            j               A[j]         C[A[j]]
___________________________________________________
    A = 4,1,3,4,3    C = 1,1,1,4     B = 1,3,3,0,4
index = 1 2 3 4 5        1 2 3 4         1 2 3 4 5
          ^              ^               ^
          j             A[j]          C[A[j]]
___________________________________________________
    A = 4,1,3,4,3    C = 0,0,2,4     B = 1,3,3,4,4
index = 1 2 3 4 5        1 2 3 4         1 2 3 4 5
        ^                      ^               ^    
        j                     A[j]          C[A[j]]

得到B，即完成排序。

阵列的作用基本上是一个计数器，这个计数器告诉我们应该摆放在B的位置，也就是B的index。

以来说，表示任何为数值为4的元素他摆放的位置应该要在B的index 5或是更前面的位置。

，这个计数器的意义
如果出现元素数值为1，他所在的位置为B阵列中 index 1或以前的位置
如果出现元素数值为2，他所在的位置为B阵列中 index 1或以前的位置
如果出现元素数值为3，他所在的位置为B阵列中 index 3或以前的位置
如果出现元素数值为4，他所在的位置为B阵列中 index 5或以前的位置

使用C++进行实作

#include <iostream>

using namespace std;
void counting_sort(int *, int *, int, int);
int main(void)
{
    int array_1[5] = {4, 1, 3, 4, 3};
    int *array_2 = (int *)malloc(sizeof(int) * 6);
    counting_sort(array_1, array_2, 4, 5);
    for (int i = 1; i < 6; i++)
    {
        printf("%d ", array_2[i]);
    }
}

void counting_sort(int *A, int *B, int k, int a_lenght)
{
    int *C = (int *)malloc(sizeof(int) * (k + 1)); //index 0 ~ k
    for (int i = 0; i < (k + 1); i++)
    {
        C[i] = 0;
    }
    for (int j = 0; j < a_lenght; j++)
    {
        C[A[j]] = C[A[j]] + 1;
    }
    for (int i = 1; i <= k; i++)
    {
        C[i] = C[i] + C[i - 1];
    }
    for (int j = a_lenght - 1; j >= 0; j--)
    {
        B[C[A[j]]] = A[j];
        C[A[j]] = C[A[j]] - 1;
    }
}

效率分析

在counting_sort主体中，第一个for需要的时间，第二个for需要的时间(n表示阵列长度)，第三个for需要的时间，第四个for需要的时间，整个counting_sort所需要的时间为，当时，整个counting_sort为，即为线性时间。

我们得知如果要使counting_sort十分的高效，需要确保阵列中的元素在某一个不会太大的整数范围内，如果阵列中的数字最多只会到阵列长度，也就是的概念，那麽阵列的长度也会为，即可实现出线性时间的演算法。

由於我们跳脱出了比较排序的演算法模型，即为元素和元素之间需要比较大小，我们使用计数器去确认元素所需要摆放的位置，因此，counting_sort的时间下界要比比较排序模型的时间下界来得好。

演算法稳定性

演算法稳定性指的是如果在一个待排序的阵列中，有两个相同的元素，如果在排序後这两个元素相对位置保持不变，那麽该演算法就是稳定的，像是上面的例子出现了两个4和两个3，他们在排序後相对次序皆没有改变，因此我们可以说counting_sort是稳定的演算法。

参考资料:Introduction to algorithms