快速排序、线性时间选择
摘要: 快速排序是运用了分治思想的排序方式，具有O(NlogN)的平均时间复杂度，极端情况下时间复杂度为O(N^2)，跟冒泡排序一样，但是快排的实际效率远比最坏情况好很多。它的关键部分是一轮选择（由Partition()函数完成）……所谓线性时间就是在平均O(N)的时间内找出无序序列中第k大的元素。它是以Partition()函数的划分为依据的……
阅读全文
posted @
2012-07-17 16:46 小鼠标 阅读(3630) |
评论 (1) 编辑
堆排序
摘要: 堆排序是一种比较常用的排序方式，具有O(NlogN)的时间复杂度，它只需要一个记录大小的空间，算法的核心是“筛选”。
堆的存储方式是一维数组，因为它是一棵完全二叉树，孩子与双亲下标有简单直接的计算方式……
阅读全文
posted @
2012-07-16 11:18 小鼠标 阅读(1162) |
评论 (0) 编辑