4.快速排序
其根本机制在于划分:划分数据就是把数据分为两组,使所有关键字大于特定值的数据项在一组,使所有关键字小于特定值的数据项在另一组。
public int partitionIt(int left, int right, long pivot) { int leftPtr = left - 1; // right of first elem int rightPtr = right + 1; // left of pivot while(true) { while(leftPtr < right && // find bigger item theArray[++leftPtr] < pivot) ; // (nop) while(rightPtr > left && // find smaller item theArray[--rightPtr] > pivot) ; // (nop) if(leftPtr >= rightPtr) // if pointers cross, break; // partition done else // not crossed, so swap(leftPtr, rightPtr); // swap elements } // end while(true) return leftPtr; // return partition } // end partitionIt() |
快速排序算法本质上通过把一个数组划分为两个子数组,然后递归地调用自身为每一个子数组进行快速排序。
综上所述,常用的排序算法的时间性能对比如表2.1所示。
2.1.6 时间复杂度
算法的时间复杂度计算方法。
算法的时间复杂度是数据结构中的重要理论基础,但也是最难理解和掌握的问题之一。本节总结了计算时间复杂度的方法供大家参考。
解算法的时间复杂度的具体步骤如下。
(1)找出算法中的基本语句。
算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。
(2)计算基本语句的执行次数的数量级。
只算最高次幂的,忽略所有低次幂和最高次幂的系数。
(3)用O记号表示算法的时间性能。
将基本语句执行次数的数量级放入O记号中。
对于并列循环,忽略。对于嵌套循环,相乘。比如,一层循环为 ,两层循环就是 ,依此类推。
常见的算法时间复杂度由小到大依次如下。
Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)
版权声明:51Testing软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。
相关文章: