第八章_排序资料.ppt

第二个for循环中调用了n-1次FilterDown( )算法, 该循环的计算时间为O(nlog2n)。因此, 堆排序的时间复杂性为O(nlog2n)。 该算法的附加存储主要是在第二个for循环中用来执行对象交换时所用的一个临时对象。因此，该算法的空间复杂性为O(1)。 堆排序是一个不稳定的排序方法。 各种排序方法的比较 第i趟对待排序对象序列V[i-1],V[i],?,V[n-1]进行排序, 结果将该序列中排序码最小的对象交换到序列的第一个位置(i-1), 其它对象也都向排序的最终位置移动。在个别情形, 对象可能在排序中途向相反的方向移动。 最多做n-1趟起泡就能把所有对象排好序。 在对象的初始排列已经按排序码从小到大排好序时,此算法只执行一趟起泡,做n-1次排序码比较,不移动对象。这是最好的情形。 最坏的情形是算法执行n-1趟起泡,第i趟 (1? i? n) 做 n- i 次排序码比较, 执行 n-i 次对象交换。这样在最坏情形下总的排序码比较次数KCN和对象移动次数RMN为： 起泡排序需要一个附加对象以实现对象值的对换。 起泡排序是一个稳定的排序方法。 快速排序 (Quick Sort) 基本思想是任取待排序对象序列中的某个对象 (例如取第一个对象) 作为基准, 按照该对象的排序码大小, 将整个对象序列划分为左右两个子区间： 左侧子区间中所有对象的排序码都小于或等于基准对象的排序码 右侧子区间中所有对象的排序码都大于基准对象的排序码 基准对象则排在这两个子区间中间(这也是该对象最终应安放的位置)。 然后分别对这两个子区间重复施行上述方法，直到所有的对象都排在相应位置上为止。 QuickSort ( List ) { if ( List的长度大于1) { 将序列List划分为两个子区间 LeftList 和 Right List; QuickSort ( LeftList ); QuickSort ( RightList ); } （回溯时会自动将两个子区间 LeftList 和 RightList合并 为一个序列List;） } 算法描述 pivot 60 55 48 37 10 90 84 36 0 1 2 3 4 5 6 7 标准纪录 初始 60 i j 60 36 55 48 37 10 90 84 36 状态1 i j 60 j i 36 55 48 37 10 90 84 36 状态2 60 第i个关键字要小于标准纪录，第j个关键字要大于标准纪录。否则，就要移动到腾空的位置，得到一个新的空位置。 快速排序算法图解 将第1个纪录移入标准纪录，得到一个空位置 0 1 2 3 4 5 6 7 标准纪录 j i 36 55 48 37 10 90 84 36 状态3 60 j i 36 55 48 37 10 90 84 36 状态4 60 j i 36 55 48 37 10 90 84 36 状态5 60 快速排序算法图解 pivot 0 1 2 3 4 5 6 7 标准纪录 j i 36 55 48 37 10 90 84 36 状态6 60 j i 36 55 48 37 10 90 84 90 状态7 60 j i 36 55 48 37 10 90 84 90 状态8 60 快速排序算法图解 0 1 2 3 4 5