强烈推荐数据结构排序.ppt

讨论2. 快速排序是否真的比任何排序算法都快 设每个子表的支点都在中间比较均衡则 第1趟比较可以确定1个元素的位置 第2趟比较2个子表可以再确定2个元素的位置 第3趟比较4个子表可以再确定4个元素的位置 第4趟比较8个子表可以再确定8个元素的位置 只需?log2n? 1趟便可排好序 基本上是因为每趟可以确定的数据元素是呈指数增加的 而且每趟需要比较和移动的元素也呈指数下降加上编程时使用了交替逼近技