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

冒泡排序

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

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

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

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

快速排序

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

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

选择排序

·直接选择排序

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

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

堆排序

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

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

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

[] [] [] [] [] [] [] [] [] [] [] []