堆排序是对树形选择排序的改进，它首先将整个待排序列构建成一个堆，然后将堆顶元素与最后一个元素交换，由此得到一个有序元素和一个长度减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);
    }
}

继续阅读 →

简单的排序方法主要是指直接插入排序、冒泡排序和简单选择排序。他们都是稳定的排序方法，平均时间复杂度都为O(n²)，并且空间复杂度都为O(1)。

直接插入排序

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。直接插入排序的运行时间和数据原始排列顺序密切相关。对于已经排好序（或已几乎排好序）的数据，插入排序的效率会比较高。

直接插入排序的C/C++代码实现：

void insert_sort(int sort_array[], int length)
{
    int i, j;
    for (i = 2; i < length; ++i)
        if (sort_array[i] < sort_array[i-1]) {
            sort_array[0] = sort_array[i];
            sort_array[i] = sort_array[i-1];
            for (j = i - 2; sort_array[0] < sort_array[j]; --j)
                sort_array[j+1] = sort_array[j];
            sort_array[j+1] = sort_array[0];
        }
}

其中第6行在sort_array[0]处设置监视哨，避免在查找插入位置的过程中数组下标出界。

冒泡排序

冒泡排序（Bubble Sort）算法简洁，也很容易理解，因此经常被用来作为介绍排序算法的入门方法。但它对于除少数元素之外的数列排序很没有效率。在这三种简单排序算法当中也是最慢的一种（参考《算法I-IV（C++实现）》Robert Sedgewick著）。而且虽然它可以设置一个标志位以对某种情况下的排序效率进行改进（即判断文件是否已排好序，当其中一步已没有进行任何交换操作，即文件已排好序，就可以中断外部循环。这个改进可以提高冒泡排序对于已排好序的数据的运行效率），但是通常来说它的效率的提高还是比不上能中断内部循环的插入排序。
继续阅读 →