Posted in 2009-12-15 8:37 PMJulius Chen
希尔排序是插入排序的扩展。希尔排序的一个特点是：子序列的构成不是简单的逐段分割，而是将相隔某个增量的记录组成一个子序列。希尔排序的一个关键是：其步长（也就是增量）的取法，通常认为步长序列中的数字互质很重要。
希尔排序的C/C++代码实现：
- void shell_insert(int sort_array[], int length, int h)
- {
- int i, j, temp;
- for (i = h; i < length; ++i)
- if (sort_array[i] < sort_array[i-h]) {
- temp = sort_array[i];
- sort_array[i] = sort_array[i-h];
- for (j = i - h * 2; j >= 0 && temp < sort_array[j]; j -= h)
- sort_array[j+h] = sort_array[j];
- sort_array[j+h] = temp;
- }
- }
-
- 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]也加入排序，这样的做法也更通用。
继续阅读 »
Posted in 2009-12-14 11:03 PMJulius Chen
简单的排序方法主要是指直接插入排序、冒泡排序和简单选择排序。他们都是稳定的排序方法，平均时间复杂度都为O(n2)，并且空间复杂度都为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著）。而且虽然它可以设置一个标志位以对某种情况下的排序效率进行改进（即判断文件是否已排好序，当其中一步已没有进行任何交换操作，即文件已排好序，就可以中断外部循环。这个改进可以提高冒泡排序对于已排好序的数据的运行效率），但是通常来说它的效率的提高还是比不上能中断内部循环的插入排序。
继续阅读 »
