本文共 3755 字，大约阅读时间需要 12 分钟。

冒泡排序

冒泡排序作为最简单的排序算法、两行for循环即可搞定。

步骤：一、从前到后依次比较相邻两个数大小，若是前面比后面大则将两个数交换位置，这样第一轮最大的一个数便会被交换到最后面。

          二、重复一的步骤依次比较（但是最后一个数不需要参与比较，因为第一轮已经选出它最大），选出倒数第二大的。

                                。。。。

          三、直到所有的数都不需要比较则排序成功

例子就不举了，直接实现：

buddle.cc

#include
   
    #include
    
     using namespace std;template< class T >void buddle( vector
     
       &a ){    int length = a.size();    for ( int i = length-1 ; i > 0; --i)        for( int j = 0; j < i; j ++){            if ( a[j] > a[j+1] )                swap(a[j], a[j+1]);        }}int main(int argc, char **argv){    vector
      
        a = {10, 8, 9, 1, 7, 4, 11, 23, 3, 2, 5};    vector
       
        ::iterator iter;    buddle
        
         ( a ); for( iter = a.begin(); iter != a.end(); iter++){ cout<< *iter <<" "; } cout << endl; return 0;}
        
       
      
     
    
   

简单选择排序

1、从1——n个数中选择最小的数，将它放在第一位

2、从2——n个数中选择最小的数，将它放在最后一位

。。。

代码：select.cc

#include
   
    #include
    
     using namespace std;template< class T >void select_sort(vector
     
       &a){    int length = a.size();    int min = 0;    for ( int i = 0; i < length; i++){        for( int j = i; j < length; j++){            if ( a[j] < a[min] )                min = j;        }        if ( i != min )            swap(a[i], a[min]);    }}int main(int argc, char **argv){    vector
      
        a = {10, 8, 9, 1, 7, 4, 11, 23, 3, 2, 5};    vector
       
        ::iterator iter;    select_sort
        
         ( a ); for( iter = a.begin(); iter != a.end(); iter++){ cout<< *iter <<" "; } cout << endl; return 0;}
        
       
      
     
    
   

插入排序

类似于打斗地主时候的插牌程序。

每次将一个数插入一个已经排好的序列中，使之依然有序，插入的时候可以采用折半插入的形式（即采用二分查找的方式确定要插入的位置）

上代码:half_insert.cc

#include
   
    #include
    
     using namespace std;template< class T >void half_insert(vector
     
       &a){    int length = a.size();    int low,mid,high;    T tmp;    for ( int i = 1; i < length; ++i){        low = 0;        high = i-1;        while( low <= high ){            mid = (low + high)/2;            if ( a[i] > a[mid] )                 low = mid + 1;            else                high = mid-1;        }        tmp = a[i];        for(int j = i; j > low; --j)            a[j] = a[j-1];        a[low] = tmp;    }}int main(int argc, char **argv){    vector
      
        a = {10, 8, 9, 1, 7, 4, 11, 23, 3, 2, 5};    vector
       
        ::iterator iter;    half_insert
        
         ( a ); for( iter = a.begin(); iter != a.end(); iter++){ cout<< *iter <<" "; } cout << endl; return 0;}
        
       
      
     
    
   

归并排序

这里是二路归并排序

使用merge_sort递归地将序列分成两个子序列，然后再调用merge函数将两个子序列合并成一个有序的序列

代码实现：merge.cc

#include
   
    #include
    
     using namespace std;const int MAX = 0x7fffffff;template< class T >void merge(vector
     
       &a, int begin, int mid, int end){    int length1 = mid-begin+1;    int length2 = end-mid+1;    int tag1 = 0;    int tag2 = 0;    int tag = begin;    vector
      
        vec1(length1+1);    vector
       
         vec2(length2+1);    for ( int i = begin ; i <= mid; i++ )        vec1[tag1++] = a[i];    vec1[tag1] = MAX;    for ( int i = mid+1; i <= end; i++)        vec2[tag2++] = a[i];    vec2[tag2] = MAX;    tag1 = 0;    tag2 = 0;    while(tag <= end ){        if ( vec1[tag1] < vec2[tag2] )            a[tag++] = vec1[tag1++];        else            a[tag++] = vec2[tag2++];    }}template< class T >void merge_sort(vector
        
          &a, int begin, int end){ if ( begin < end ){ int mid = (begin + end)/2; merge_sort(a, begin, mid); merge_sort(a, mid+1, end); merge(a, begin, mid, end); }}int main(int argc, char **argv){ vector
         
           a = {10, 8, 9, 1, 7, 4, 11, 23, 3, 2, 5}; vector
          
           ::iterator iter; merge_sort(a, 0, a.size()-1); for( iter = a.begin(); iter != a.end(); iter++){ cout<< *iter <<" "; } cout << endl; return 0;}