计数排序的原地排序

---

    本文介绍计数排序算法的原地排序实现，对应于《算法导论》（第二版）P105，思考题8-2 e)。

    作者：tyc611.cublog.cn，2008-03-02

---

问题描述

 

    假设n个记录中每一个的关键字都界于1到k之间。说明如何修改计数排序，使得可以在O(n+k)时间内对n个记录原地排序。除输入数组外，可以另用O(k)的存储空间。你给出的算法是稳定的吗？

 

算法思想

 

    修改基本的计数排序算法，实现原地排序。由于不再使用辅助空间来存放排序结果，因此只能通过对原数组的元素进行置换，以完成排序。由于是使用置换完成排序，因此算法不再是稳定的。

    比起原计数排序算法，新算法将使用另一个大小为k的空间来存放当前值为i（1≤i≤k）的数组元素的当前个数。当该数组中所有元素值为0时，排序完成。

 

算法实现

 

    本文使用C++实现算法如下：

 

 

/**
 * CountingSort.cpp
 * @Author Tu Yongce
 * @Created 2008-2-28
 * @Modified 2008-2-28
 * @Version 0.1
 */

// 《算法导论》（第二版）P105，思考题8-2 e)：计数排序的原地排序版本

/**
 * 假设n个记录中每一个的关键字都界于1到k之间。说明如何修改计数排序，使得可以在O(n+k)时间内
 * 对n个记录原地排序。除输入数组外，可以另用O(k)的存储空间。你给出的算法是稳定的吗？
 */

#include <iostream>
#include <utility>
using namespace std;

/**
 * 计数排序算法的原地排序版本，时间复杂度仍为O(n+k)，但不再是稳定排序
 * @param arr: 待排序数组
 * @param size: 待排序数组大小
 * @param k: 数组元素取值范围为[0, k]
 */
void counting_sort_in_place(int *arr, size_t size, int k)
{
    int *count = new int[ k + 1]; // count[i]包含等于i的元素个数
    int *pos = new int[k + 1]; // pos[i]包含小于等于i的元素个数减一

    for (int i = 0; i <= k; ++i)
        count[i] = 0;

    for (size_t i = 0; i < size; ++i)
        ++count[arr[i]];
    
    pos[0] = count[0] - 1; // 减一，与C风格数组下标保持一致
    for (int i = 1; i <= k; ++i)
        pos[i] = pos[i - 1] + count[i];

    int index = 0;
    while (true) {
        while (index <= k && count[index] == 0)
            ++index;
        if (index > k)
            break; // 所有数组元素都已置换到正确的位置，排序完毕
        int srcPos = pos[index];

        int curValue = arr[srcPos];
        int destPos = pos[curValue];

        while (srcPos != destPos) {
            --count[curValue];
            --pos[curValue];
            swap(curValue, arr[destPos]);
            destPos = pos[curValue];
        }
        arr[srcPos] = curValue;
        --count[curValue];
        --pos[curValue];
    }

    delete [] count;
    delete [] pos;
}

// 这里也提供原版计数排序算法实现，为稳定排序，方便比较
/**
 * 计数排序算法，时间复杂度为O(n+k)，稳定排序
 * @param arr: 待排序数组
 * @param size: 待排序数组大小
 * @param k: 数组元素取值范围为[0, k]
 */
void counting_sort(int *arr, size_t size, int k)
{
    int *count = new int[ k + 1];

    // count[i]包含等于i的元素个数 
    for (int i = 0; i <= k; ++i)
        count[i] = 0;
    for (size_t i = 0; i < size; ++i)
        ++count[arr[i]];
    
    // pos[i]包含小于等于i的元素个数减一
    --count[0]; // 减一，与C风格数组下标保持一致
    for (int i = 1; i <= k; ++i)
        count[i] += count[i - 1];

    int *tmpArr = new int[size];
    for (int i = size - 1; i >= 0;--i) {
        tmpArr[count[arr[i]]] = arr[i];
        --count[arr[i]];
    }
    copy(tmpArr, tmpArr + size, arr);

    delete [] tmpArr;
    delete [] count;
}

void counting_sort_test()
{

    int arr1[] = {2, 5, 3, 0, 2, 3, 0, 3};
    int arr2[] = {6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2};

    int* arr[] = {arr1, arr2};
    const size_t NUM[] = {
        sizeof(arr1) / sizeof(arr1[0]),
        sizeof(arr2) / sizeof(arr2[0]),
    };
    int k[] = {5, 6};

    for (size_t l = 0; l < sizeof(arr) / sizeof(arr[0]); ++l) {
        cout << "原序列：" << endl;
        for (size_t i = 0; i < NUM[l]; ++i)
            cout << arr[l][i] << " ";
        cout << endl;

        counting_sort_in_place(arr[l], NUM[l], k[l]);
        //counting_sort(arr[l], NUM[l], k[l]);
        
        cout << "排序后的序列：" << endl;
        for (size_t i = 0; i < NUM[l]; ++i)
            cout << arr[l][i] << " ";
        cout << "\n" << endl;
    }
}


    算法运行结果如下：

原序列：
2 5 3 0 2 3 0 3
排序后的序列：
0 0 2 2 3 3 3 5

原序列：
6 0 2 0 1 3 4 6 1 3 2
排序后的序列：
0 0 1 1 2 2 3 3 4 6 6

请按任意键继续. . .

---