本文是作者原创文章，欢迎转载，请注明出处 from:@Eric_Lai

今天学习了一个在排序界颇具声名的排序算法“快速排序”。此算法据说是实际排序应用当中最好的选择，在最坏情况下它的时间复杂度是（n²），期望时间复杂度是（nlgn），其中的常数因子非常小。另外，它还能进行原址排序。

这个算法，同样使用了分治法的思想，以一个数组A[p…r]为例来研究它的分治三步曲：

1. 分解：数组A被划分为两个（可能为空）子数组A1[p…q-1]和A2[q+1…r],使得A1当中的所有元素都不大于A[q]，而A[q]也不大于A[q+1…r]当中的任何元素；
2. 解决：通过递归调用快速排序，对子数组A1,A2进行重复上面的操作；
3. 合并：；因为子数组都是原址排序，所以不需要进行合并操作，数组A[p…r]已经有序；

整个算法的主要核心很明显在于第一步分解，怎么才能使这个分解达到上述的要求。下面给出一段伪码来描述这个算法：

// A是数组，p是数组第一个元素的下标，r是数组的最后一个元素的下标
partition(A, p, r){
	x = A[r];
	i = p - 1; 
	for(j = p; j < r; j++){
		if(A[j] > x){
			i++;
			tmp = A[i];
			A[i] = A[j];
			A[j] = tmp;
		}else {
    i++;
  }
	}
	tmp = A[r];
	A[r] = A[i+1];
	A[i+1] = tmp;
	return i+1;
}

分析一下以上的代码，它的主要思想是这样的：取传入数组的最后的元素为key，把整个数组分成三部分，前面部分是不大于key的元素，中间是key，后面是比key大的数。最后返回key元素换位后对应的下标。这样，利用这个下标前后两个部分的子数组可以进入下一轮的递归。

具体上，怎么把一个数组分成这么三拨呢？首先，把数组的最后一个元素存到一个叫x的变量里面。然后，弄两个指针，一个指向数组的第一个元素（即上述代码的j），另一个指针比j落后一位（也就是上述的i）。j从数组的的头开始向数组的尾部移动直到倒数第二个原色（r-1）为止（因为最后一个元素是key，不需要进行比较）。在j移动过程中，每遇到一个比key小的元素，就让i往前移动一位。若i和j并非指向同一个元素，则交换i和j所指向的元素（把小的元素放到数组的左边）。最后，交换key与i+1指向的元素。这样，就实现了上一段所说的把一个数组分成3拨（这样key所在的位置就必定是正确的，大的都在后面，小的都在前面）。

有了上面这一段，递归部分就很好写了。==每当递归一次，就把一个元素移动到了它所在的正确位置上==。下面给出一段伪码：

// A是数组，p是数组第一个元素的下标，r是数组的最后一个元素的下标
quick_sort(A, p, r){
	if(p < r){
		q = partition(A, p, r);
		quick_sort(A, p, q-1);
		quick_sort(A, q+1, r);
	}
}

由于这个算法的实现思想比较好理解，编写实际语言环境下的代码也比较简单就不在给出具体的代码了。