排序，重要性不言而喻。 今天练手了快排，堆排序，和插入排序， 二分查找。 快排参考了 http://blogread.cn/it/article/612?f=sr ，写的不错！ 可以看看。

先总结下： 边界值很重要，一定要考虑到。

说下快排，这个排序自诞生起，就引起了轰动，也名列十大经典算法之一。它主要分为两个步骤，划分和递归， 其中划分是算法的核心，递归是重要的思想。递归部分伪代码如下：

1 quicksort(A[], p, r)2    if p < r3        q = partition(a, p, r)4        quicksort(a, p, q-1)5        quicksort(a, q+1, r)

划分，就是选取一个主元（中间数）, 把小的放在它左边，大的放在它右边； 接着递归左边，右边，直到条件终止退出。盗用下算法导论中的图，划分就是把区间分为四块，小于，大于，未定和主元。

 

主元的选取一般来说有三种： 两端，随机，三数取中， 这里我们使用了是两端(尾端)，先实现下算法导论中的方法：

1 template
     
       2 int partition_ia(T a[], int beg, int last) 3 { 4     T piot = a[last]; 5     int i = beg-1; 6     for(int j=beg; j
      
        piot) 8             swap(a[++i], a[j]); 9     }10     swap(a[++i], a[last]); 11     return i;12 }
      
     

这种方法貌似不是很好，在前面给的链接里，提出了一个从两端开始的方法：

template
     
      int partition_double(T a[], int beg, int last){    T piot = a[last];    int i = beg-1;    int j = last;    while(1){       do ++i; while(i<=last && a[i] <= piot);       do --j; while(a[j]>piot);       if(i>j) break;       swap(a[i], a[j]);    }    swap(a[i], a[last]);     return i;  }
     

另外，还有改进的双端扫描，采用尾递归手段减少栈的大小等等。

现在说下堆排序，之前的博文中用类实现堆排序，现在使用函数形式实现

int heap_size = 0;template
     
      void maxheapify(T a[], int index){    int l = index*2+1;    int r = (index+1)*2;    int large = index;    if(l < heap_size){        if(a[l] > a[index]) large = l;    }    if(r < heap_size){        if(a[r] > a[large])  large = r;    }    if(index != large) {        swap(a[large], a[index]);        maxheapify(a, large);    }}template
      
       void build_heap(T a[], int len){     heap_size = len;     for(int i=(heap_size-1)/2; i>=0; --i){         maxheapify(a, i);    }}template
       
        void heapsort(T a[], int len){    for(int i=1; i
       
      
     

插入排序：  这个思想很经典，都是拿扑克牌举例的。。我们可以这么认为，数组被分为两部分，一部分是已排好的，另一部分是乱序的； 每次排序从乱序中拿出一张（头）, 插入到合适位置。

template
     
      void insertsort(T a[], int len){      T key;       int j, i;      for(ii=1; i
      
       =0; --j){              if(a[j]<=key) break;              a[j+1] = a[j];          }          a[j+1] = key;     }}
      
     

二分查找：  有句话说，90%的程序员一次写不对二分查找。。我试了下，我也是属于90%的。

二分查找有两种解题思路，一种是递归，一种是循环。参考文章： http://www.kuqin.com/algorithm/20120911/330495.html

先说递归，这个思想好理解：

1 template
     
       2 int bisearch_d(T a[], int beg, int last, const T& x) 3 { 4      int mid = beg + （last-beg）/2; 5      if(mid<=last){ 6          if(a[mid] == x) return mid+1; 7          else if(a[mid]>x) return bisearch_d(a, beg, mid-1,x); 8          else return bisearch_d(a,mid+1, last, x); 9      }10      return 0;11 }
     

这个可以用循环很简单的实现

template
     
      void bisearch_cy(T a[], int low, int high, const T& x){      int mid = low + (high-low)/2;      while(low <= high){           if(a[mid-1] == x) return mid;           else if(a[mid-1] > x) high = mid-1;           else low = mid + 1；           mid = low + (high-low) / 2;      }      return 0；}