Posted in 2009-12-22 6:27 PMJulius Chen
归并排序是建立在归并操作（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);
- }
- }
继续阅读 »
Posted in 2009-12-21 6:12 PMJulius Chen
堆排序是对树形选择排序的改进，它首先将整个待排序列构建成一个堆，然后将堆顶元素与最后一个元素交换，由此得到一个有序元素和一个长度减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);
- }
- }
继续阅读 »
Posted in 2009-12-20 3:50 PMJulius Chen
快速排序是应用最广泛的排序算法，也是目前认为最好的一种内部排序方法（就平均时间而言）。它采用分治（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);
- }
- }
继续阅读 »
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著）。而且虽然它可以设置一个标志位以对某种情况下的排序效率进行改进（即判断文件是否已排好序，当其中一步已没有进行任何交换操作，即文件已排好序，就可以中断外部循环。这个改进可以提高冒泡排序对于已排好序的数据的运行效率），但是通常来说它的效率的提高还是比不上能中断内部循环的插入排序。
继续阅读 »
