三种快速排序算法的实现（递归算法、非递归算法、三路划分快速排序）.doc

三种快速排序算法的实现（递归算法、非递归算法、三路划分快速排序）
快速排序的三个步骤：
1、分解：将数组A[l...r]划分成两个（可能空）子数组A[l...p-1]和A[p+1...r]，使得A[l...p-1]中的每个元素都小于等于A(p)，而且，小于等于A[p+1...r]中的元素。下标p也在这个划分过程中计算。
2、解决：通过递归调用快速排序，对数组A[l...p-1]和A[p+1...r]排序。
3、合并：因为两个子数组时就地排序，将它们的合并并不需要操作，整个数组A[l..r]已经排序。

：
QUICKSORT(A, l, r)
if l < r
then q = PARTION(A, l, r)
QUICKSORT(A, l, p-1)
QUICKSORT(A, p+1, r)
两路PARTION算法主要思想：
move from left to find an element that is not less
move from right to find an element that is not greater
stop if pointers have crossed
exchange

实现代码：
[cpp] view plaincopy
1. int partition(double* a, int left, int right)
2. {
3. double x = a[right];
4. int i = left-1, j = right;
5. for (;;)
6. {
7. while(a[++i] < x) { }
8. while(a[--j] > x) { if(j==left) break;}
9. if(i < j)
10. swap(a[i], a[j]);
11. else break;
12. }
13. swap(a[i],a[right]);
14. return i;
15. }
16.
17. void quickSort1(double* a, int left, int right)
18. {
19. if (left
20. {
21. int p = partition(a, left, right);
22.
23. quickSort1(a, left, p-1);
24. quickSort1(a, p+1, right);
25. }
26. }

：其实就是手动利用栈来存储每次分块快排的起始点，栈非空时循环获取中轴入栈。
实现代码：
[cpp] view plaincopy
1. void qui