数据结构定义和算法--排序--快速排序

算法原理

1. 如果要排序下标为p到r之间的一组数组；
2. 选择p到r之间任意一个元素做pivot（分区点），将小于pivot的元素放在左边，大于pivot的放在右边，pivot放在中间。这样数组就被分为三个部分，小于pivot的区间A[p, q-1]、等于pivot的区间A[q]、大于pivot的区间A[q+1, r]；
3. 根据分治思想和递归编程技巧，我们可以用递归排序区间A[p, q-1]和区间A[q+1, r]，直到区间缩小为1，就说明数组有序了；

如何实现

1. 递推公式：quick_sort(p, r) = quick_sort(p, q-1) + quick_sort(q+1, r);
2. 终止条件：p >= r;