这节,我们介绍基数排序和归并排序。 一、基数排序 基数排序(Radix Sort)的设计思想与前面介绍的各种排序方法完全不同。前面介绍的排序方法主要是通过关键码的比较和记录的移动这两种操作来实现排序的,而基数排序不需要进行关键码的比较和记录的移动。基数排序是一种借助于多关键码排序的思想,是将单关键码按基数分成多关键码进行排序的方法,是一种分配排序。 下面用一个具体的例子来说明多关键码排序的思想。 其中,k1称为最主位关键码,kd称为最次位关键码。 多关键码排序方法按照从最主位关键码到最次位关键码或从最次位关键码到最主位关键码的顺序进行排序,分为两种排序方法: 基数的源代码如下: //基数排序的方法 public int[] RadixSort(int[] ArrayToSort, int digit,int len) { // 从低位到高位的方法 for (int k = 1; k <= digit; k++) { // 临时的数组存储里面的十进制的排序的结果 int[] tmpArray = new int[ArrayToSort.Length]; //临时的数组存储计数的结果 int[] tmpCountingSortArray = new int[len]; //基数的数组1 如图所示: 基数排序是稳定的排序,时间的复杂度是O(n2). 二、归并排序 归并排序(merge Sort)主要是二路归并排序。二路归并排序的基本思想是:将两个有序表合并为一个有序表。 对于n个记录的顺序表,将这n个记录看作叶子结点,若将两两归并生成的子表看作它们的父结点, 则归并过程对应于由叶子结点向根结点生成一棵二叉树的过程。所以,归并趟数约等于二叉树的高度减1,即log2n,每趟归并排序记录关键码比较的次数都约为n/2,记录移动的次数为2n(临时顺序表的记录复制到原顺序表中记录的移动次数为n) 。 因此, 二路归并排序的时间复杂度为O (nlog2n) 。 一趟二路归并排序算法的实现如下所示, 算法中记录的比较代表记录关键码的比较,顺序表中只存放了记录的关键码,相应的源代码如下: public void Merge(SeqList<int> sqList, int len) { int m = 0; //临时顺序表的起始位置 int l1 = 0; //第1个有序表的起始位置 int h1; //第1个有序表的结束位置 int l2; //第2个有序表的起始位置 int h2; //第2个有序表的结束位置 int i = 0; int j = 0; //临时表,用于临时将两个有序表合并为一个有序表 SeqList<int> tmp = new SeqList<int>(sqList.GetLength()); //归并处理 while (l1 + len < sqList.GetLength()) { l2 = l1 + len; //第2个有序表的起始位置 h1 = l2 - 1; //第1个有序表的结束位置 //第2个有序表的结束位置 h2 = (l2 + len - 1 < sqList.GetLength()) ? l2 + len - 1 : sqList.Last; j = l2; i = l1; //两个有序表中的记录没有排序完 while ((i<=h1) && (j<=h2)) { //第1个有序表记录的关键码小于第2个有序表记录的关键码 if (sqList[i] <= sqList[j]) { tmp[m++] = sqList[i++]; } //第2个有序表记录的关键码小于第1个有序表记录的关键码 else { tmp[m++] = sqList[j++]; } } //第1个有序表中还有记录没有排序完 while (i <= h1) { tmp[m++] = sqList[i++]; } //第2个有序表中还有记录没有排序完 while (j <= h2) { tmp[m++] = sqList[j++]; } l1 = h2 + 1; } i = l1; //原顺序表中还有记录没有排序完 while (i < sqList.GetLength()) { tmp[m++] = sqList[i++]; } //临时顺序表中的记录复制到原顺序表,使原顺序表中的记录有序 for (i = 0; i < sqList.GetLength(); ++i) { sqList[i] = tmp[i]; } } 二路归并排序算法的实现如下: public void MergeSort(SeqList<int> sqList) { int k = 1; //归并增量 while (k < sqList.GetLength()) { Merge(sqList, k); k *= 2; } } 对于n个记录的顺序表,将这n个记录看作叶子结点,若将两两归并生成的子表看作它们的父结点, 则归并过程对应于由叶子结点向根结点生成一棵二叉树的过程。所以,归并趟数约等于二叉树的高度减1,即log2n,每趟归并排序记录关键码比较的次数都约为n/2,记录移动的次数为2n(临时顺序表的记录复制到原顺序表中记录的移动次数为n) 。 因此, 二路归并排序的时间复杂度为O (nlog2n)。而二路归并排序使用了n个临时内存单元存放记录,所以,二路归并排序算法的空间复杂度为O(n) 。 C#数据结构,就此结束了,这是我的一点总结。
|
|