计数排序(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];
}

继续阅读 →

归并排序是建立在归并操作（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);
    }
}

继续阅读 →

堆排序是对树形选择排序的改进，它首先将整个待排序列构建成一个堆，然后将堆顶元素与最后一个元素交换，由此得到一个有序元素和一个长度减1的堆。由于交换后新的堆顶元素可能不满足堆的定义，因此需要将新的堆重新进行堆化（堆化无需重新建堆，只需做少许调整），在堆化完成之后再次将堆顶元素与堆的最后一个元素交换，由此再得到一个新的有序元素和一个长度减1的堆。然后再重新进行堆化，再交换。。。这样一直下去，直到整个堆只有一个元素为止。这样也就完成了对序列的排序。由这个排序的过程也可以知道，堆排序和简单选择排序不同，不是从前往后慢慢有序，而是从后往前慢慢有序。

堆排序的C/C++代码实现：

void heapify(int sort_array[], int k, int m)
{
    int temp = sort_array[k];
    for (int j = 2 * k; j <= m; j *= 2) {
        if (j < m && sort_array[j] < sort_array[j+1]) ++j;
        if (!(temp < sort_array[j])) break;
        sort_array[k] = sort_array[j];
        k = j;
    }
    sort_array[k] = temp;
}

void heap_sort(int sort_array[], int length)
{
    int i, temp;
    for (i = (length - 1) / 2; i >= 0; --i)
        heapify(sort_array, i, length - 1);

    for (i = length - 1; i > 0; --i) {
        temp = sort_array[0];
        sort_array[0] = sort_array[i];
        sort_array[i] = temp;
        heapify(sort_array, 0, i - 1);
    }
}

继续阅读 →

快速排序是应用最广泛的排序算法，也是目前认为最好的一种内部排序方法（就平均时间而言）。它采用分治（divide-and-conquer）的策略，通过一趟排序将待排记录分割成独立的两个部分，使其中的一部分记录关键字均比另一部分记录关键字小（大），然后分别对两个部分继续进行排序，以达到整个序列有序。

快速排序的C/C++代码实现：

int partition(int sort_array[], int low, int high)
{
    int pivotkey = sort_array[low];
    while (low < high) {
        while (low < high && pivotkey <= sort_array[high]) --high;
        sort_array[low] = sort_array[high];
        while (low < high && pivotkey >= sort_array[low]) ++low;
        sort_array[high] = sort_array[low];
    }
    sort_array[low] = pivotkey;
    return low;
}

void quick_sort(int sort_array[], int low, int high)
{
    if (low < high) {
        int i = partition(sort_array, low, high);
        quick_sort(sort_array, low, i - 1);
        quick_sort(sort_array, i + 1, high);
    }
}

继续阅读 →

希尔排序是插入排序的扩展。希尔排序的一个特点是：子序列的构成不是简单的逐段分割，而是将相隔某个增量的记录组成一个子序列。希尔排序的一个关键是：其步长（也就是增量）的取法，通常认为步长序列中的数字互质很重要。

希尔排序的C/C++代码实现：

void shell_insert(int sort_array[], int length, int h)
{
    int i, j, tmp;
    for (i = h; i < length; ++i)
        if (sort_array[i] < sort_array[i-h]) {
            tmp = sort_array[i];
            sort_array[i] = sort_array[i-h];
            for (j=i-h*2; j>=0 && tmp<sort_array[j]; j-=h)
                sort_array[j+h] = sort_array[j];
            sort_array[j+h] = tmp;
        }
}

void shell_sort(int sort_array[], int length)
{
    int h;
    for (h = 1; h < (length - 1) / 9; h = h * 3 + 1);
    while (h >= 1) {
        shell_insert(sort_array, length, h);
        h /= 3;
    }
}

和直接插入排序相比，这里的shell_insert只做了两处修改：
1. 前后记录位置的增量不再是1，而是h；
2. sort_array[0]已不能再作为监视哨，而只能作为一个暂存单元，因为式子j -= h并不一定能使j值到达0。因此，这里干脆用一个temp来代替sort_array[0]做为暂存单元，而让sort_array[0]也加入排序，这样的做法也更通用。
继续阅读 →