1.快速排序
快速排序(Quick Sort)的基本思想是:通过不断比较关键码,以某个记录为
界(该记录称为支点) ,将待排序列分成两部分。其中,一部分满足所有记录的关键码都大于或等于支点记录的关键码,另一部分记录的关键码都小于支点记录的关键码。把以支点记录为界将待排序列按关键码分成两部分的过程,称为一次划分。对各部分不断划分,直到整个序列按关键码有序为止。设待排序的顺序表 sqList 中有 n 个记录,一般地,第一次划分把第一个记
录作为支点。首先,把支点复制到一个临时存储空间中,并设两个指示器,一个指示器 low,指向顺序表的低端(第一个记录所在位置),一个指示器 high,指向顺序表的高端(最后一个记录所在位置)。然后,从 high 所指向的记录开始,将记录的关键码与支点(在临时存储空间中)的关键码进行比较,如果 high 所指向的记录的关键码大于支点的关键码,high 指示器向顺序表的低端方向移动一个记录的位置,否则,将 high 所指的记录复制到 low 所指的存储空间中。接着,又将 low 移到下一个记录,从 low 所指向的记录开始,将记录的关键码与临时存储空间的记录的关键码进行比较,如果 low 所指向的记录的关键码小于临时存储空间的记录的关键码,low 指示器向顺序表的高端方法移动一个记录的位置,否则,将 low 所指的记录复制到 high 所指的存储空间中,high 指示器向顺序表的低端移动一个记录的位置。如此重复,直到 low 和 high 指示器指向同一个记录,将临时空间的记录赋给 low 所指向的存储空间,第一次划分结束。快速排序的算法实现如下所示,算法中记录的比较表示记录关键码的比较,顺序表中只存放了记录的关键码:public void QuickSort(SeqList sqList, int low, int high) { int i = low; int j = high; int tmp = sqList[low]; while (low < high) { while ((low < high) && (sqList[high] >= tmp)) { --high; } sqList[low] = sqList[high]; ++low; while ((low < high) && (sqList[low] <= tmp)) { ++low; } sqList[high] = sqList[low]; --high; } sqList[low] = tmp; if (i < low-1) { QuickSort(sqList, i, low-1); } if (low+1 < j) { QuickSort(sqList, low+1, j); } }
2.堆排序 在直接选择排序中,顺序表是一个线性结构,要从有n个记录的顺序表中选择出一个最小的记录需要比较n-1 次。如能把待排序的n个记录构成一个完全二叉树结构,则每次选择出一个最大(或最小)的记录比较的次数就是完全二叉树的高度,即log2n次,则排序算法的时间复杂度就是O(nlog2n)。 这就是堆排序(Heap Sort)的基本思想。 堆分为最大堆和最小堆两种。最大堆的定义如下: 设顺序表sqList中存放了n个记录,对于任意的i(0≤i≤n-1),如果2i+1<n时有 sqList[i]的关键码不小于 sqList[2i+1]的关键码;如果 2i+2<n 时有sqList[i] 的关键码不小于 sqList[2i+2] 的关键码,则这样的堆为最大堆。 如果把这 n 个记录看作是一棵完全二叉树的结点,则 sqList[0]对应完全二叉树的根,sqList[1]对应树根的左孩子结点,sqList[2]对应树根的右孩子结点, sqList[3]对应 sqList[1]的左孩子结点,sqList[4]对应 sqList[2]的右孩子结点,如此等等。在此基础上,只需调整所有非叶子结点满足:sqList[i] 的关键码不小于 sqList[2i+1] 的关键码和 sqList[i] 的关键码不小于 sqList[2i+2] 的关键码,则这样的完全二叉树就是一个最大堆。
public void CreateHeap(SeqList sqList, int low, int high) { if ((low < high) && (high <= sqList.Last)) { int j = 0; int tmp = 0; int k = 0; for (int i = high / 2; i >= low; --i) { k = i; j = 2 * k + 1; tmp = sqList[i]; while (j <= high) { if ((j < high) && (j + 1 <= high) && (sqList[j] < sqList[j + 1])) { ++j; } if (tmp < sqList[j]) { sqList[k] = sqList[j]; k = j; j = 2 * k + 1; } else { j = high + 1; } } sqList[k] = tmp; } } } public void HeapSort(SeqList sqList){ int tmp = 0; CreateHeap(sqList, 0, sqList.Last); for (int i = sqList.Last; i > 0; --i){ tmp = sqList[0]; sqList[0] = sqList[i]; sqList[i] = tmp; CreateHeap(sqList, 0, i-1); } }