快速排序法是一种非常快的对比排序方法。它也Divide-And-Conquer思想的实现之一。自从其产生以来,快速排序理论得到了极大的改进,然而在实际中却十分难以编程出正确健壮的代码。
方法/步骤
1
因为该算法是Divide-And-Conquer思想的一个实现,所以本文将以Divide-And-Conquer思想对其进行分析。
2
首先,假设所要排序的数字存储在数组S中,则该算法的操作可以拆分为两部分:
3
在S中选出一个元素v;将S数组分为三个子数组。其中v这个元素单独形成子数组1,比v小的元素形成子数组2,比v大的元素形成自数组3.
5
该程序具有平均运行时间T(n) = O(nlgn), 最差运行时间T(n) = O(n^2);
6
本文将对快速排序算法的基本理论和编程实践方面做作一个全面的讲解。在本文讲解中,将忽略很多细枝末节,试图给读者形成一个非常具体的快速排序形象。
上一篇:XP与Win7系统快速共享打印机