博主欢迎转载，但请给出本文链接，我尊重你，你尊重我，谢谢~

特别不喜欢那些随便转载别人的原创文章又不给出链接的

所以不准偷偷复制博主的博客噢~~

 

最近适当复习了下基本的排序算法，虽然做题的时候一般都直接用sort了事，但基本的排序原理还是要了解的，所以把常见的排序又重新写了下。

基本的插入、选择、冒泡就不说了，归并排序、快速排序可以网上搜算法导论的学习，也很简单。

1.插入排序

void insertSort(int a[],int len){    for(int i=1;i
      
       =0 && tmp
      

 

2.选择排序

void selectSort(int a[],int len){    for(int i=0;i
      
       a[minidx]){            int tmp=a[i];            a[i]=a[minidx];            a[minidx]=tmp;        }    }}
      

 

3.冒泡排序

void bubbleSort(int a[],int len){    int tmp;    for(int i=0;i
      
       a[j+1]){                tmp=a[j+1];                a[j+1]=a[j];                a[j]=tmp;                flag=false;            }        }        if(flag)            break;    }}
      

 

4.归并排序O(NlgN)

#define INF 0x3f3f3f3f/*将[l,mid]和[mid+1,r]两个区间进行合并，每次取两个开头最小的那个*/void merges(int a[],int l,int mid,int r){    int len1=mid-l+1;    int len2=r-mid;    int L[len1+1],R[len2+1];    for(int i=0;i

 

5.快速排序O(NlgN)

/*以最后a[r]为划分点，将数组a划分成两个部分前部分<=a[r],后部分>a[r]最后返回a[r]的索引*/int quick_partition(int a[],int l,int r){    int x=a[r];    int i=l-1;    for(int j=l;j

 

6.最大堆排序O(NlgN)

//----------------堆排序O(NlgN)最大堆的实现--------------------------/*将最大堆的根节点和末尾交换后，可能破坏了最大堆的性质，所以要进行更新*/void heap_update(int a[],int i,int heap_size){    int l=i*2+1;    int r=i*2+2;    int large=i;    if(l
      
       a[large])        large=l;    if(r
       
        a[large])        large=r;    if(large!=i){        swap(a[i],a[large]);        heap_update(a,large,heap_size);    }}/*将val插入到数组a的末尾，并进行最大堆的维护*/void heap_insert(int a[],int val,int heap_size){    heap_size++;    a[heap_size-1]=val;    int idx=heap_size-1;    while(idx>0 && a[idx/2]
        
         >1;    }}void heapSort(int a[],int len){    //构建最大堆    for(int i=0;i
         
          =0;i--){        swap(a[0],a[i]);        heap_update(a,0,i);  //每次heap_size减小1的    }}
         
        
       
      

 

7.希尔排序

最近突然遇到希尔排序，之前没听过，所以就了解一下，不专门写介绍了，给一篇链接吧，讲得挺详细的

希尔排序对于增量序列（即gap）的选择很重要，会影响到排序的性能，通常都采用gap=length/2。

希尔排序是可以突破O(N^2)的，但gap/=2的情况下最坏时间复杂度依然为O(N^2)，一些优化过后的序列最坏情况可以到O(N^3/2)。

/*https://www.cnblogs.com/chengxiao/p/6104371.html希尔排序*/void shellsort(int a[],int len){    //划分成gap个组    for(int gap=len/2;gap>0;gap/=2){        //从第gap个元素，逐个对其所在组进行插入排序操作        //而不需要for每个组进行操作        for(int i=gap;i
      
       =0 && a[j]>a[j+gap]){                swap(a[j],a[j+gap]);                j-=gap;            }        }        /*        printf("gap:%d\n",gap);        for(int i=0;i
      

 

完整的测试代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;//----------------插入排序--------------------------void insertSort(int a[],int len){ for(int i=1;i
            
             =0 && tmp
             
              a[minidx]){ int tmp=a[i]; a[i]=a[minidx]; a[minidx]=tmp; } }}//----------------冒泡排序--------------------------void bubbleSort(int a[],int len){ int tmp; for(int i=0;i
              
               a[j+1]){ tmp=a[j+1]; a[j+1]=a[j]; a[j]=tmp; flag=false; } } if(flag) break; }}//----------------归并排序O(NlgN)--------------------------#define INF 0x3f3f3f3f/*将[l,mid]和[mid+1,r]两个区间进行合并，每次取两个开头最小的那个*/void merges(int a[],int l,int mid,int r){ int len1=mid-l+1; int len2=r-mid; int L[len1+1],R[len2+1]; for(int i=0;i
               
                a[r]最后返回a[r]的索引*/int quick_partition(int a[],int l,int r){ int x=a[r]; int i=l-1; for(int j=l;j
               
              
             
            
           
          
         
        
       
      

 

最后，当然排序最省力的就是C++中的自定义排序了，直接用algorithm中的sort即可。

#include 
     
      bool cmp(int a,int b){    return a>b; }sort(a,a+n); //a为数组，n为数组的长度，默认是从小到大排序sort(a,a+n,cmp);//cmp即为自定义比较函数，此处是从大到小排序。