基数排序和计数排序一样，是非基于比较的排序算法，它借助“分配”和“收集”两种操作对单逻辑关键字进行排序（基于箱/桶排序），它的排序速度很快，时间复杂度为线性，但由于需要的辅助空间太大（n(radix+1)），因此长期无法应用。直到1954年有人提出用“计数”代替“分配”才得以使它能在计算机上实现。此后，又有人提出用链表作为存储数据的结构，这样又能减少一些辅助空间，这也是一种比较好的实现方法（只是算法要较复杂）。

基数排序分为MSD（最高位优先）基数排序和LSD（最低位优先）基数排序，MSD从左到右处理关键字的位数，首先处理最重要的数字。它比较符合常规的思维，所需处理的信息量也较少。但按MSD进行排序，必须将序列逐层分割成若干个子序列，然后对各子序列分别进行排序；而LSD则从右到左先处理最不重要的数字，这样虽然可能花费了一些时间来处理不会影响结果的信息，但它不用分子序列，对每个关键字都是整个序列参加排序，而且对具体的应用还可以对其进行改进。因此在很多排序应用中都选择这种方法。

基数排序（LSD/用计数排序）的C/C++代码实现：

void radix_sort(int a[], int length)
{
    int i, j, digit;
    int c[16];
    int tmp[ARRAY_SIZE];
    for (i = 0; i < HEX; ++i) {
        for (j = 0; j < 16; ++j) c[j] = 0;
        for (j = 0; j < length; ++j) c[a[j]>>4*i&0xf]++;
        for (j = 1; j < 16; ++j) c[j] += c[j-1];
        for (j = length - 1; j >= 0; --j) {
            digit = a[j] >> 4 * i & 0xf;
            tmp[ c[digit]-1] = a[j];
            c[digit]--;
        }
        for (j = 0; j < length; ++j) a[j] = tmp[j];
    }
}

Continue reading →

计数排序(Counting Sort)是一种非基于比较的排序方法，它要求所有的待排元素都必须是≥0的整数。它的排序步骤是首先根据数组中最大的元素值加1作为长度来定义一个计数数组C。然后统计待排数组中每个值为i的元素出现的次数，存入C的第i项中。再对所有的计数累加（从C中的第一项开始，每一项和前一项相加）。最后再反向填充辅助数组：将每个元素i放在辅助数组的第C(i)项，每放一个元素就将C(i)减去1。这样完成之后排序就已完毕，有序序列已存储在辅助数组中。如果结果想用原数组输出，则将它们从辅助数组考回到原数组即可。

计数排序的C/C++代码实现：

void counting_sort(int a[], int length)
{
    int i;
    int c[MAX_VALUE] = {0};
    int tmp[ARRAY_SIZE] = {0};
    for (i = 0; i < length; ++i) c[a[i]]++;
    for (i = 1; i < MAX_VALUE; ++i) c[i] += c[i-1];
    for (i = length - 1; i >= 0; --i) {
        tmp[ c[a[i]]-1] = a[i];
        c[a[i]]--;
    }
    for (i = 0; i < length; ++i) a[i] = tmp[i];
}

Continue reading →

归并排序是建立在归并操作（Merging）上的一种排序方法，它是采用分治法的一个非常典型的应用。归并是指将两个或两个以上的有序表合并成一个新的更大的有序表，归并排序则是递归的先将待排序列分割成n个序列，然后从最小的有序序列（只含一个元素）开始不断调用归并操作进行合并直到最后都合并成一个大的完整的有序表为止。

归并排序的C/C++代码实现：

void merge(int array[], int low, int m, int high)
{
    int i, j, k;
    static int temp[ARRAY_SIZE];
    for (i = low, j = m + 1, k = 0; k < high - low + 1; ++k) {
        if (i > m) {
            temp[k] = array[j++];
            continue;
        }
        if (j > high) {
            temp[k] = array[i++];
            continue;
        }
        temp[k] = array[i] < array[j] ? array[i++] : array[j++];
    }
    for (k = 0; k < high - low + 1; ++k)
        array[low+k] = temp[k];
}

void merge_sort(int sort_array[], int low, int high)
{
    if (low < high) {
        int i = (low + high) / 2;
        merge_sort(sort_array, low, i);
        merge_sort(sort_array, i + 1, high);
        merge(sort_array, low, i, high);
    }
}

Continue reading →