数据结构——C++实现 作者 缪淮扣 顾训穰 沈俊 数据结构-第九章.pptVIP

else { table.Arr[pq].setLink ( table.Arr[q].getLink()); table.Arr[q].setLink ( table.Arr[0].getLink()); table.Arr[0].setLink ( q ); } p = h ; //准备下一次选择 } } 与在顺序表上的直接插入排序一样。在链表上进行直接选择排序，关键字比较次数与数据元素的初始排列无关，总的关键字比较次数为: 比较次数=(n-1)+(n-2)+…+1=n(n-1)/2 在链表上进行直接选择排序不需要进行数据元素的移动，每一趟选出数据元素后只需将其插入到有序表的第一个数据元素之前。可见在链表上进行直接选择排序总的时间复杂度也为O(n2）。 链表上的直接选择排序也是一种不稳定的排序方法。 锦标赛排序 锦标赛排序的算法思想与体育比赛类似。 首先将n个数据元素两两分组，分别按关键字进行比较，得到n／2个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来， 然后对这n／2个数据元素再两两分组，分别按关键字进行比较，…，如此重复，直到选出一个关键字最小的数据元素为止。 锦标赛排序示例： 锦标赛排序构成的树是完全二叉树，其高度为?Log2n?+1，其中n为排序表中数据元素个数。 因此，除第一次选出具有最小关键字的数据元素需要进行n-1次关键字比较外，重构优胜者树，选出具有次小、再次小、…关键字的数据元素所需的关键字比较次数均为0(Log2n)。 所以，总的关键字比较次数为0(nLog2n)。数据元素的移动次数与关键字的比较次数相当，所以锦标赛排序总的时间复杂度为0(nlog2n)。 锦标赛排序也是一种不稳定的排序方法。 堆排序 堆排序的算法基本思想是： （1）对排序表中的数据元素，利用堆的调整算法形成初始堆。 （2）输出堆顶元素。 （3）对剩余元素重新调整形成堆。 （4）重复执行第（2)、(3)步，直到所有数据元素被输出。 堆排序的示例 建立最大堆的调整算法： template class Type void MinHeapType :: FilterDown ( const int start , const int EndOfHeap) { //向下调整使从start开始到EndOfHeap为止的子表成为最大堆 int i = start, j = 2*i+1; // j为i的左孩子 Type temp = heapArr[i]; while ( j = EndOfHeap ) { if ( j EndOfHeap table.Arr[j].getkey() table.Arr[j+1].getkey()) j++; //在两个孩子中选关键字较小者 if ( temp.getkey() = table.Arr[j].getkey()) break; else { table.Arr[i] = table.Arr[j]; i = j; j = 2*j+1; } } table.Arr[i] = temp; } 堆排序算法的C++描述如下： template class Type void HeapSort (sortlist Type table ) { for ( int i = (table.CurrentSize-2 ) / 2; i = 0; i-- ) FilterDown ( i, table.CurrentSize-1 ); //初始建堆 for ( i = table.CurrentSize-1; i = 1; i--) { Swap(table.Arr[0],table.Arr[i]); FilterDown ( 0, i-1 ); //重建最大堆 } } 堆排序算法的时间复杂性可用关键字的比较次数来测度。 若设堆中有n个结点，且2k-1?n?2k，则对应的完全二叉树有k层。 在第一个形成初始堆的for循环中对每一个非叶结点调用了一次堆调整算法Fi