Tag Archives: 快速排序

算法技术手册 – 排序 – 快速排序

待补充:非递归版本。

快速排序和前面的中值排序非常类似。

分为partition和sort主体两个部分。

1.partition
和前面求第k大的数用到的思路非常类似。
(0)确定一个pivotIndex
(1)交换a[right]和a[pivotIndex]
(2)i=store=left,i从left到right-1,注意要包含right-1!!(不用包含right,因为里面是pivot)
(3)在(2)过程中,如果a[i] (4)完成上述步骤后,交换a[stor[……]

继续阅读