数据结构 第9章 排序.ppt

对于有n个数据元素的链表，若每个关键字有d位，算法需要重复执行d趟“分配”与“收集”。每趟进行“分配”的循环需要执行n次，把n个数据元素分配到radix个队列中去；进行“收集”的循环需要执行radix次，把radix个队列中的数据元素收集起来按顺序链接。所以总的时间复杂度为0(d(n十radix))。 算法所需要的附加存储空间是为每个是数据元素结点增设的链接指针，及为每一个队列设置的队头和队尾指针，总共为n+2*radix。 在基数排序中不需要移动数据元素，并且它是一种稳定的排序方法。 各种排序方法的选择和使用 以上这些排序方法各有其优缺点，各有其适用的情况，无法笼统地说哪种方法最好，只能说在某种情况下哪种方法更适用。因此，在实际应用中，应根据不同的情况选择不同的算法。在选择排序方法时，主要需考虑以下因素： （1）排序表的大小，即待排序数据元素的个数； （2）关键字的分布情况； （3）对排序的稳定性要求。 考虑上述因素，在此提出下列建议供参考。 （1）若排序表的长度较小（如n＜50）时，可采用简单的排序方法，如直接插入排序或选择排序。但要注意插入排序的数据元素移动次数比选择排序的次数多，因此，当数据元素个数较多时，用选择排序较好。 （2）若排序表的长度较大时，应选用执行时间与nlog2n成正比的排序方法，如快速排序、希尔排序、堆排序和归并排序等。 当排序表中数据元素的关键字分布随机时，快速排序的平均运行时间最少；堆排序只需1个记录的辅助空间，并且不会出现快速排序可能出现的最坏情况；希尔排序由于也是一种插入排序，故排序过程中移动记录的次数较多，但当记录接近有序时，希尔排序较快。上述三种排序方法都是不稳定的。利用归并排序可满足对排序结果稳定性的要求。还可将归并排序与直接插入排序联合使用，即先用直接插入排序得到长度小于50的有序段，然后再两两归并。 （3）若待排序记录已基本有序，可采用插入类排序方法或冒泡排序。 （4）当n很大而关键字位数较小时，可考虑采用基数排序方法。 在第二个for循环中，调用了n-1次FilterDown( )算法，每次调用总是将位于根上的数据元素最多下调到当前堆的最底层。所以该循环的计算时间为O(nlog2n)。因此，堆排序的时间复杂性为O(nlog2n)。 该算法的空间复杂性为O(1)。堆排序是一种不稳定的排序方法。 归并排序 所谓归并，就是将两个或两个以上的有序表合并成一个新的有序表。如下图所示，有两个已经排好序的有序表A[1]?A[n]和B[1]?B[m]（在图中只给出了它们的关键字），通过归并把它们合成一个有序表C[1]?C[m+n]。 两路归并算法的C++描述 ： template class Type void merge ( sortlistType sourceTable, sortlist Type mergedTable, const int left, const int mid, const int right ) { int i = left, j = mid+1, k =left;//指针初始化 while ( i = mid j = right ) if ( sourceTable.Arr[i].getKey() = sourceTable.Arr[j].getKey()) { mergedTable.Arr[k] = sourceTable.Arr[i]; i++; k++; } else { mergedTable.Arr[k] = sourceTable.Arr[j]; j++; k++; } if ( i = mid ) for ( int p = k, q = i; q = mid; p++, q++ ) mergedTable.Arr[p] = sourceTable.Arr[q]; else for ( int p = k, q = j; q = right; p++, q++) mergedTable.Arr[q] = sourceTable.Arr[p]; } 两路归并排序 两路归并排序就是利用两路归并算法进行排序。其算法基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为1的首尾相接的n个有序子表(以后称它们为归