转载

快速排序

快速排序是排序算法中比较出名的一位角儿了。为什么出名呢？因为是它首先把排序算法突破O(n ² )，而后一大批优秀的排序算法如雨后春笋般涌现出来。这就告诉我们，做事情呢不需要为自己定位一个上限，一个十分明确的上限。因为一旦上限确定，你只能在上限之下，你的成就也好，能力也罢，充其量也就是最好的上限。正是这样，在不设上限的努力之下，你完全可以突破既有的规则约定，达到一个永恒的成就。在人们都认为排序算法不可能突破O(n ² )的原有规则下，排序算法的作者（抱歉我不记得名字，致敬）无视规则突破了这一限制。后人才想到，哦，原来排序可以更快哈。

废话少说，下面来深入探究一下快速排序的基本思路。核心思想是递归分治。

首先是计算主元所在的位置。什么是主元呢？你可以选取第一个元素或者最后一个元素作为主元，然后循环所有的元素找出它所在的位置，返回他的下标。也就是可以这么说，在主元之前的元素都是比主元小的元素，在主元之后的元素都是比主元小的元素。通过有限次数的递归分治，将一个大的数组分成多个比较小的数组，每次都保证大的在后小的在前。然后合并起来。在这里我们选取最后一个元素作为主元，从开始到倒数第二个不断比较大小，小的与大的交换，而后将主元（最后一个元素）插入到合适的位置，并且返回他的下标。这就保证了此下标前面的比他小，后面的比他大。

然后呢，再对第一步分成的前后两个部分进行排序。这里要有一个控制条件，即什么时候停止。就是小的下标小于大的下标。

程序（C++）的完整代码在下，已在CB完美运行。

  1 #include <iostream>  2 using namespace std;  3   4 void exchange(int &a, int &b) {  5     int temp = a;  6     a = b;  7     b = temp;  8 }  9  10 int partition(int a[], int l, int h) { 11     int pivot = a[h]; 12     int i = l - 1; 13  14     for(int j = l; j != h-1; ++j) { 15         if(a[j] <= pivot) { 16             ++i; 17             exchange(a[j], a[i]); 18         } 19     } 20  21     exchange(a[i + 1], a[h]); 22  23     return i+1; 24 } 25  26 void quickSort(int a[], int l, int h) { 27     if(l < h){ 28         int q = partition(a, l, h); 29         quickSort(a, l, q-1); 30         quickSort(a, q+1, h); 31     } 32 } 33  34 int main() { 35     int a[10] = {2,8,7,1,3,5,6,4,12,0}; 36     quickSort(a, 0, 9); 37     for(int i = 0; i != 10; ++i){ 38         cout<<a[i]<<" "; 39     } 40 }

原文 http://www.cnblogs.com/zhaoyansheng/p/5165734.html

正文到此结束