精通八大排序算法系列一快速排序算法(8)

请各位自行，思考以下这个版本，对应于上文哪个版本?

HOARE-PARTITION(A, p, r)

1 x ← A[p]

2 i ← p - 1

3 j ← r + 1

4 while TRUE

5 do repeat j ← j - 1

6 until A[j] ≤ x

7 repeat i ← i + 1

8 until A[i] ≥ x

9 if i < j

10 then exchange A[i] A[j]

11 else return j

我常常思考，为什么有的人当时明明读懂明白了一个算法，

而一段时间过后，它又对此算法完全陌生而不了解了列?

我想，究其根本，还是没有彻底明白此快速排序算法的原理，与来龙去脉...

那作何改进列，只能找发明那个算法的原作者了，从原作者身上，再多挖掘点有用的东西出来。 =========================================

最后，再给出一个快速排序算法的简洁示例：

Quicksort函数

void quicksort(int l, int u)

{ int i, m;

if (l >= u) return;

swap(l, randint(l, u));

m = l;

for (i = l+1; i <= u; i++)

if (x[i] < x[l])

swap(++m, i);

swap(l, m);

quicksort(l, m-1);

quicksort(m+1, u);

}

如果函数的调用形式是quicksort(0, n-1)，那么这段代码将对一个全局数组x[n]进行排序。 函数的两个参数分别是将要进行排序的子数组的下标：l是较低的下标，而u是较高的下标。 函数调用swap(i,j)将会交换x[i]与x[j]这两个元素。

第一次交换操作将会按照均匀分布的方式在l和u之间随机地选择一个划分元素。

ok，更多请参考我写的关于快速排序算法的第二篇文章：一之续、快速排序算法的深入分析，第三篇文章：十二、一之再续：快速排序算法之所有版本的c/c++实现。

July、二零一一年二月二十日更新。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库精通八大排序算法系列一快速排序算法(8)在线全文阅读。