开放教育数据结构历年真题 09年自考《数据结构》各章要点二[7]

09年自考《数据结构》各章要点二[7]  

　　冒泡排序

　　·自下向上确定最轻的一个

　　·自上向下确定最重的一个

　　·自下向上确定最轻的一个 后自上向下确定最重的一个

　　·冒泡排序是就地的稳定排序 时间复杂度为O(n^ ) 比较次数为n(n )/ ;移动次数为 n(n )/

　　快速排序

　　·以第一个元素为参考基准 设定 动两个指针 发生交换后指针交换位置 直到指针重合 重复直到排序完成

　　·快速排序是非就地的不稳定排序 时间复杂度为O(nlog n) 比较次数为n(n )/

　　选择排序

　　·直接选择排序

　　·选择最小的放在比较区前

　　·直接选择排序就地的不稳定排序 时间复杂度为O(n^ ) 比较次数为n(n )/

　　堆排序

　　·建堆 按层次将数据填入完全二叉树 从int(n/ )处向前逐个调整位置

　　·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆 直到全断开

　　·堆排序是就地不稳定的排序 时间复杂度为O(nlog n) 不适宜于记录数较少的文件