快速排序方法过程 JS实现随机化快速排序的实例代码

JS实现随机化快速排序的实例代码  

　　算法的平均时间复杂度为O(nlogn) 但是当输入是已经排序的数组或几乎排好序的输入 时间复杂度却为O(n^ ) 为解决这一问题并保证平均时间复 杂度为O(nlogn)的方法是引入预处理步骤 它惟一的目的是改变元素的顺序使之随机排序 这种预处理步骤可在O(n)时间内运行 能够起到同样作用的 另一种简单方法是在算法中引入一个随机元素 这可以通过随机地选择拆分元素的主元来实现 随机选择主元的结果放宽了关于输入元素的所有排列的可能性相同的 步骤 引入这一步来修正原先的快速排序 可得到下面所示的随机化快速排序 新算法只是在区间[low…high]中一致随机地选择一个索引v 并将 A[v]和A[low]交换 然后按照原来的快速排序算法继续 这里 parseInt(Math random()*(high low+ ) + low)返回一个在low和high之间的数