以下是个人总结的排序算法，它分为以下几个类：

交换排序：冒泡排序（BubbleSort）和快速排序（QuickSort）。

插入排序：直接插入排序和希尔排序（ShellSort）。

选择排序：选择排序（SelectSort）和堆排序（HeapSort）。

归并排序：分治的思想。

基数排序：稳定快速的排序。

计数排序：对于待排序元素分布较集中的序列有优势。

（一）交换排序：

voidBubbleSort(int*arry,intsize){for(inti=0;i<size-1;i++){for(intj=0;j<size-i-1;j++){if(arry[j]>arry[j+1]){swap(arry[j],arry[j+1]);}}}}//冒泡排序第一次优化（设置一个标志）voidBubbleSort(int*arry,intsize){boolswaped=false;for(inti=0;i<size;i++){swaped=false;for(intj=0;j<size-i-1;j++){if(arry[j]>arry[j+1]){swap(arry[j],arry[j+1]);swaped=true;}}if(!swaped){break;}}}//冒泡排序第二次优化（去除已经有序的区间）voidBubbleSort(int*arry,intsize){intlastswappos=size-1;intlastswappos_temp=size-1;for(inti=0;i<size;i++){lastswappos=lastswappos_temp;for(intj=0;j<lastswappos;j++)//每次冒泡到最后一次交换的位置{if(arry[j]>arry[j+1]){swap(arry[j],arry[j+1]);lastswappos_temp=j;}}if(lastswappos==lastswappos_temp){break;}}}

冒泡排序是最简单的交换排序，在这里我们给出了2种优化方式。第一种是设置一个标志位标志在一趟排序中是否有过排序，如果没有则就排序完成，这种优化方式对于在一个数组的后半部分是有序的情况下提高了效率。第二种方式也相当于设置一个标志位，只是这个标志位是标志最后一次交换的数的下标。这种方法是有效的去除了已经有序的区间。

不管怎么优化，对于一般的数组冒泡排序的时间复杂度为O（N^2）。

快速排序：

//挖坑法voidQuickSort(vector<int>&arry,intleft,intright){if(left>=right)return;intlflag=left;intrflag=right-1;inttmp=arry[left];while(lflag<rflag){while((lflag<rflag)&&arry[rflag]>=tmp){rflag--;}arry[lflag]=arry[rflag];while((lflag<rflag)&&arry[lflag]<=tmp){lflag++;}arry[rflag]=arry[lflag];}swap(arry[lflag],tmp);QuickSort(arry,left,rflag-1);//左子区间QuickSort(arry,rflag+1,right);//右子区间}//prev/cur法[left,right]voidQuickSort(vector<int>&arry,intleft,intright){//递归结束条件if(left>=right)return;intcur=left;intprev=cur-1;intkey=arry[right];while(cur!=right){if(arry[cur]<key&&cur!=(++prev)){swap(arry[cur],arry[prev]);}cur++;}swap(arry[++prev],arry[right]);QuickSort(arry,left,prev-1);QuickSort(arry,prev+1,right);}//三数取中法//三数取中法（选取left，right，mid中不大不小的那个值作为key，和arry[right]交换）intFindMidValue(vector<int>&arry,intleft,intright)//[p,q]{intmid=left-(left-right)/2;if(arry[left]>arry[mid]){if(arry[mid]>arry[right]){swap(arry[right],arry[mid]);}elseif(arry[right]>arry[left]){swap(arry[right],arry[left]);}}elseif(arry[left]>arry[right]){swap(arry[right],arry[left]);}returnarry[right];}voidQuickSort(vector<int>&arry,intleft,intright){if(left>=right)return;intlflag=left;intrflag=right;intkey=FindMidValue(arry,lflag,rflag);while(lflag<rflag){while(lflag<rflag&&arry[lflag]<=key){lflag++;}if(lflag<rflag){arry[rflag]=arry[lflag];rflag--;}while(lflag<rflag&&arry[rflag]>=key){rflag--;}if(lflag<rflag){arry[lflag]=arry[rflag];lflag++;}}arry[lflag]=key;QuickSort(arry,left,lflag-1);QuickSort(arry,lflag+1,right);}

快速排序是利用了划分子问题的思想。每次选取区间的第一个数据作为中间值，将大于中间值的数据放在右边，否则放在左边。再将中间值的左右边看成一个子区间，递归的划分子区间，直到区间的左边下标大于或者等于右边下标结束。

prev/cur法是利用两个指针，prev和cur，cur一直找小于key值得下标和prev下标的值交换。

而三数取中法是对于快速排序的优化，有时候常常会出现很尴尬的情况：我们选取最左或最右的值为key值，偏偏这个值是整个待排序列的最小或最大的值，这种情况下快速排序就是效率最慢的情况，变成了慢速排序。这时候三数取中法就帮助我们避免这种情况。

快速排序是效率比大部分排序算法的速度要快。快排一般情况下是最快的排序，而且具有稳定性。但是快速排序是一个递归思想，显然，对于内存有限的机器来说它不是一个好的选择。对于很长很长的数组来说也不是一个好的选择，递归的额层数越多，效率越低。

（二）选择排序：

一般的选择排序

voidSelectSort(int*arry,intsize){assert(arry);intflag=0;while(flag!=size-1){intmin=flag;for(inti=flag+1;i<size;i++){if(arry[i]<arry[min]){min=i;}}swap(arry[min],arry[flag]);flag++;}}

一般的选择排序算法的时间复杂度为O（N^2）。

堆排序

voidAdjustDown(int*a,size_tsize,size_tparent)//下调函数{size_tchild=parent*2+1;while(child<size){if(child+1<size&&a[child]<a[child+1])++child;if(a[parent]<a[child]){swap(a[parent],a[child]);parent=child;child=parent*2+1;}elsebreak;}}voidHeapSort(int*a,size_tsize){//建堆for(inti=(size-2)/2;i>=0;--i)//i不能定义为size_t除法会溢出，翻转成一个很大的数{AdjustDown(a,size,i);}for(size_ti=0;i<size;++i){swap(a[0],a[size-1-i]);AdjustDown(a,size-i-1,0);}}

堆排序是利用大顶堆的性质，可以快速的找出最大值。依次找出最大值，排序完成。时间复杂度为

O（N*lgN）。

（三）插入排序

直接插入排序：

voidInsertSort(int*a,size_tsize){assert(a);for(size_ti=1;i<size;++i){inttmp=a[i];size_tj=i;while(j>0&&tmp<a[j-1]){a[j]=a[j-1];j--;}a[j]=tmp;}}

在数组前面的有序序列里找到合适的位置将待插入数据插入，时间复杂度为O（N^2）。

希尔排序：

//gap为gap/2voidShellSort(int*a,intsize){intgap=size/2;while(1<=gap){//把距离为gap的元素编为一个组，扫描所有组for(inti=gap;i<size;i++){intj=0;inttemp=a[i];//对距离为gap的元素组进行排序for(j=i-gap;j>=0&&temp<a[j];j=j-gap){a[j+gap]=a[j];}a[j+gap]=temp;}gap=gap/2;//减小增量}}//gap为gap/3+1voidHellSort(vector<int>&a,intsize){intgap=size;while(gap>1){gap=gap/3+1;for(size_ti=0;i<size-gap;++i){intend=i;inttmp=a[end+gap];while(end>=0&&a[end]>a[end+gap]){a[end+gap]=a[end];a[end]=tmp;end-=gap;}}}}

gap是间隔增量。它控制序列向有序发展。

我们分割待排序记录的目的是减少待排序记录的个数，并使整个序列向基本有序发展。因此，我们需要采取跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

希尔排序的时间复杂度是在O（N^1.25）~O（N^1.66）之间。希尔排序在逆序时效果最好，有序时效果最差，还不如直接排序。

（四）归并排序

归并排序是建立在分治思想上的一种排序方法，将大的问题划分成小问题，逐个解决。我们在排序的时候也时常用到这种思想，比如一个待排序序列很大很大的时候，我们需要将这个大序列划分成一个个的小序列，归并排序将是一个非常好的选择。

voidMergeCell(int*arry,int*tmp,intleft1,intright1,intleft2,intright2){intindex=0;intbegin=left1;while(left1<=right1&&left2<=right2){if(arry[left1]<arry[left2]){tmp[index++]=arry[left1++];}else{tmp[index++]=arry[left2++];}}while(left1>right1&&left2<=right2){tmp[index++]=arry[left2++];}while(left2>right2&&left1<=right1){tmp[index++]=arry[left1++];}for(inti=0;i<index;++i){arry[begin++]=tmp[i];}}voidMerge_(int*arry,int*tmp,intleft,intright){if(left<right){intmid=left-(left-right)/2;Merge_(arry,tmp,left,mid);Merge_(arry,tmp,mid+1,right);MergeCell(arry,tmp,left,mid,mid+1,right);}}voidMergeSort(int*arry,intsize){intleft=0;intright=size-1;int*tmp=newint[size];Merge_(arry,tmp,left,right);for(inti=0;i<size;++i){cout<<arry[i]<<"";}}

（五）计数排序

计数排序的方法就有点简单粗暴了，计数排序适合那种待排序序列元素分布比较叫集中的序列，如果序列的最大值和最小值相差很大的话，效率实在是低。

voidCountSort(int*arry,intsize){//找出最大和最小的值，max-min作为开辟空间的大小intmin=arry[0],max=arry[0];for(inti=0;i<size;++i){if(arry[i]<min)min=arry[i];if(arry[i]>max)max=arry[i];}int*count=newint[max-min+1];memset(count,0,(max-min+1)*sizeof(int));//统计数组中出现数字的次数for(inti=0;i<size;++i){++count[arry[i]-min];}intindex=0;//遍历计数数组，只要值不为一，就将数组的下标+min拷贝进原始数组，原始数组已经没用了for(inti=0;i<max-min+1;++i){while(count[i]--){arry[index++]=min+i;}}}

（六）基数排序：

基数排序有LSD和MSD两种方法，LSD是从低位向高位排序。MSD是从高位向地位排序。这里以LSD实现

//LSD法适合位数少的排序(此程序排不了含有负数的序列)voidRadixSort(int*arry,intsize){inttime=1;intradix=10;//统计最大的位数for(inti=0;i<size;++i){if(arry[i]>radix){time++;radix*=10;}}int*count=newint[10];int*bucket=newint[size];radix=1;//控制排序的次数，从低位排到高位for(inti=0;i<time;++i){memset(count,0,10*sizeof(int));memset(bucket,0,size*sizeof(int));for(intj=0;j<size;++j){//统计每个桶中有多少个数据++count[(arry[j]/radix)%10];}for(intk=1;k<10;++k){count[k]=count[k]+count[k-1];}for(intk=0;k<size;++k){intindex=count[(arry[k]/radix)%10-1];while(bucket[index]!=0){index++;if(index>=size){index=0;}}bucket[index]=arry[k];}for(intk=0;k<size;++k){arry[k]=bucket[k];}radix*=10;}}

计数排序和基数排序是非比较排序，他们都有适用的场合，熟练掌握多种排序算法是有必要的。

博主的知识有限，文章难免会有纰漏，请多多指正。