算法技术手册（原书第2 版）

排序算法

｜

69

排序算法

if (cmp (ar[idx], pivot) <= 0) {

tmp = ar[idx];

ar[idx] = ar[store];

ar[store] = tmp;

store++;

}

}

tmp = ar[right];

ar[right] = ar[store];

ar[store] = tmp;

return store;

}

快速排序

算法由

C.A.R.Hoare

于

1960

年提出，它的思想是从集合中挑选一个元素（可以

随机挑选元素、可以挑选最左边的元素或者中间的元素），来将数组切分成两个子数组。

因此，

快速排序

有两个步骤：先将数组进行切分，之后递归调用对每个子数组进行排序。

快速排序算法小结

最好情况和平均情况：

O

(

n

log

n

)

最坏情况：

O

(

n

2

)

sort (A)

quicksort (A, 0, n-1)

end

quicksort (A, left, right)

if left < right then

pi = partition (A, left, right)

quicksort (A, left, pi-1)

quicksort (A, pi+1, right)

end

上述伪代码特意没有给出选择中枢值下标的策略。假定在相关联的代码中，存在一个

selectPivotIndex

函数用于选择适当的下标。这里不打算证明

快速排序

拥有

O(

n

log

n

)

的平均性能行为，关于这个话题的详细讨论可以参见 ...