专题三数据结构与算法 ZhejiangUniversity.ppt

3 堆排序思想 对一组待排序的记录按堆的定义建立堆 将堆顶记录和最后一个记录交换位置则前n-1个记录是无序的而最后一个记录是有序的 堆顶记录被交换后前n-1个记录不再是堆需将前n-1个待排序记录重新组织成为一个堆然后将堆顶记录和倒数第二个记录交换位置即将整个序列中次小关键字值的记录调整(排除)出无序区 重复上述步骤直到全部记录排好序为止 结论排序过程中若采用小根堆排序后得到的是非递减序列若采用大根