学步园

快速排序由C.A.R.Hoare于1960年发明，快速排序的平均时间复杂度是nlogn，最坏时间复杂度是n^2，但实际上快速排序的性能是相当不错的，不然为啥叫快速排序。快速排序做原地排序（in-place sort），只需要一个额外的栈空间。算法的核心是做分划（partition），分划可以在线性时间内完成，每次分划都会把一个元素（我们经常称它为pivot）放到它最终的位置上，分划把所有小于等于pivot的元素放在了pivot的左边，所有大于等于pivot的元素放在了pivot的右边。分划的过程中整个数组的形状是这样的：[小于pivot的部分，大于pivot的部分，还未扫描到得数据]（这里假设元素各不相同）。我们从左往右扫描（其实可以右往左，或者从两头扫描，我不熟悉）时，当发现一个元素比pivot还小的时候，就扩大小于pivot部分，准备放刚刚扫描到得这个比较小的元素（i=i+1，i是小于pivot那部分的最右边的下标），然后交换a[i]与a[j]（j刚刚扫描到一个比pivot小的数，交换后j是大于pivot部分的最右边的数的下标），然后继续扫描，一直到结束，下面是partition函数：

int partition(int *a, int low, int high)<br /> {<br /> if(low<high)<br /> {<br /> int pivot = a[low];<br /> int i = low, j, tmp;<br /> for(j=low+1; j<=high; j++)<br /> {<br /> if(a[j]<=pivot)<br /> {<br /> i=i+1;<br /> tmp = a[i];<br /> a[i] = a[j];<br /> a[j] = tmp;<br /> }<br /> }<br /> if(i != low)<br /> {<br /> tmp = a[i];<br /> a[i] = a[low];<br /> a[low] = tmp;<br /> }<br /> return i;<br /> }<br /> return -1;<br /> }

所以可以这样快速排序，其实就是分治的思想。

void quick_sort(int *a, int low, int high)<br /> {<br /> if(low < high)<br /> {<br /> int i = partition(a, low, high);<br /> quick_sort(a, low, i-1);<br /> quick_sort(a, i+1, high);<br /> }<br /> }