本文对各类排序算法的实现、优化、复杂度、稳定性、适用场景作以总结，为了突出算法的简洁、易懂，去除了模板与仿函数的冗余，默认为升序进行模拟。
《插入排序》
基本思想：每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的合适位置上去，直到元素插完。
直接插入排序
基本思想：当我们插入第i（i=1）个元素时，前面的所有元素已经排好序，此时我们使用当前元素从后向前比较，直到找到一个小于array的节点（若没有，则插在数组下标为0的地方），从下一个节点顺序后移，将array插入进来。
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定
适用场景：1.数据量较小；2.基本接近有序
voidInsrtSort(int*arr,int_siz){if(arr==NULL
_siz=0)rturn;for(intidx=1;idx_siz;++idx){intnd=idx-1;//nd为插入之前最后一个节点的下标whil(nd=0arr[nd]arr[nd+1]){inttmp=arr[nd+1];//保存待插入的结点arr[nd+1]=arr[nd];//将待插入结点之前的元素后移arr[nd]=tmp;//插入待插入结点nd--;}}}
二分插入排序（优化）
基本思想：在直接插入排序的基础上进行优化，因为待插入元素之前的元素已经有序，我们没必要每个都遍历，借助而二分法的思想可以有效降低查找的时间。
voidBinaryInsrtSort(int*arr,intsiz){if(arr==NULL
siz=0)rturn;intindx=0;for(intidx=1;idxsiz;++idx){inttmp=arr[idx];//保存待插入元素intlft=0;intright=idx-1;intmid=(lftright)+((lft^right)1);//二分法查找插入位置whil(lft=right){if(tmparr[mid]){right=mid-1;indx=mid;//更新插入位置}lsif(tmp=arr[mid]){lft=mid+1;indx=mid+1;//更新插入位置}mid=(lftright)+((lft^right)1);//缩小空间}//后移元素for(intj=idx;jindx;j--){arr[j]=arr[j-1];}//插入新元素arr[indx]=tmp;}}
《希尔排序》
基本思想：希尔排序是插入排序的一个变种。不同之处在于我们按步长gap分组，对每组的记录采用直接插入排序，随着步长的逐渐减少，分组包含的记录越来越多，直到gap=1时，构成了一个有序记录。
时间复杂度：O(n^1.25)~1.6*O(n^1.25)
空间复杂度：O(1)
稳定性：不稳定
适用场景：数据量较大
下图中为了方便，对gap以gap/2来计算，但最优的算法是gap/3+1。
voidShllSort(int*arr,intsiz){if(arr==NULL
siz=0)rturn;intgap=siz;//gap为增量whil(gap1){gap=gap/3+1;//这样给是最优的for(intidx=gap;idxsiz;++idx){intnd=idx-gap;//分组后，当前元素的前一个元素intky=arr[idx];//保存当前元素//按升序排序whil(nd=0arr[nd]ky){arr[nd+gap]=arr[nd];nd-=gap;}arr[nd+gap]=ky;}}}
《选择排序》
基本思想：每一趟(例如第i趟，i=0,1，…，n-2)在后面n-i个待排序的数据元素集合中选出关键码最小的数据元素，作为有序元素序列的第i个元素，待到第n-2趟做完，待排序元素集合中只剩下1个元素，排序结束。
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
适用场景：数据量较小，交换次数比较少
选择排序（单边缩小空间）
基本思想：我们定义一个maxIndx来标记区间内最大值的下标，第一次遍历完数组后，更新maxIndx的指向，与下标为nd（最后一个元素）的元素交换，nd--缩小空间，继续遍历更新maxIndx。
voidSlctSort(int*arr,intsiz){if(arr==NULL
siz=0)rturn;for(intnd=siz-1;nd0;--nd){intmaxIndx=nd;//最大下标for(intidx=0;idxnd;++idx){//比最大的元素还大，更新最大下标if(arr[idx]arr[maxIndx])maxIndx=idx;}//交换nd与最大元素的值std::swap(arr[maxIndx],arr[nd]);}}
选择排序（双边缩小空间1.0）
基本思想：每一趟遍历我们需要找出最大元素的下标与最小元素的下标，然后用处于最小下标的元素与bgin（首元素下标）交换，用最大下标的元素与nd（尾元素下标），最后bgin++，nd--同时缩短区间，直到bgin与nd相等。
注意：如果bgin与maxIndx相同，bgin与minPos交换之后，maxPos也应该指向minPos。
voidSlctSort(int*arr,intsiz){if(arr==NULL
siz=0)rturn;intbgin=0;intnd=siz-1;whil(bginnd){intmaxPos=bgin;//最大元素下标intminPos=bgin;//最小元素下标for(intidx=bgin+1;idx=nd;++idx){//比最大的元素还大，更新最大下标if(arr[idx]arr[maxPos])maxPos=idx;//比最小的元素还小，更新最大下标if(arr[idx]arr[minPos])minPos=idx;}//交换bgin与最小元素的值std::swap(arr[bgin],arr[minPos]);//如果最大元素下标与bgin相同，上面bgin与minPos已经交换，因此maxPos也应该指向minPosif(maxPos==bgin)maxPos=minPos;//交换nd与最大元素的值std::swap(arr[nd],arr[maxPos]);//缩小区间++bgin;--nd;}}
选择排序（双边缩小空间2.0）
基本思想：1.0版本中，我们需要考虑最大下标与bgin的重合问题，为了避免这样的问题出现，我们将不再使用maxPos和minPos，而改用直接交换数据，然后缩小空间，直到左右空间重合。
voidSlctSort(int*arr,intsiz){if(arr==NULL
siz=0)rturn;intlft=0;intright=siz-1;whil(lftright){for(intidx=lft;idx=right;++idx){//比lft小的交换if(arr[idx]arr[lft])std::swap(arr[idx],arr[lft]);//比right大的交换if(arr[idx]arr[right])std::swap(arr[idx],arr[right]);}//缩小左右区间++lft;--right;}}
《堆排序》
基本思想：大堆对应升序序列，小堆对应降序队列，我们从最后一个非叶子结点建堆，步骤如下：
⑴将堆顶元素与当前最大堆的最后一个节点交换
⑵最大堆节点-1，即调整剩下的n-1个节点
⑶从堆顶继续向下调整，试之满足最大堆，循环⑴和⑵，直至剩下一个节点。
时间复杂度：NlogN
稳定性：不稳定
适用场景：topK等问题
voidAdjustDown(int*arr,introot,intsiz)//建大堆{intparnt=root;intchild=parnt*2+1;whil(childsiz){//保证child指向较大节点if(child+1sizarr[child+1]arr[child])child+=1;if(arr[child]arr[parnt]){std::swap(arr[child],arr[parnt]);parnt=child;//下滤child=parnt*2+1;}lsbrak;}}//堆排序递归voidHapSort(int*arr,intsiz){assrt(arrsiz1);//从最后一个非叶子节点建堆for(intidx=(siz-2)/2;idx=0;--idx){AdjustDown(arr,idx,siz);//下滤调整}intnd=siz-1;whil(nd0){//堆顶与最后一个节点交换，升序std::swap(arr[0],arr[nd]);AdjustDown(arr,0,nd);//下滤调整--nd;}}
篇幅原因，下面几种排序方式不再详细介绍，附上代码，欢迎大家参考和总结，不足之处还望指正。
《快速排序（优化）》
+#includiostram+usingnamspacstd;+#includstack+tmplatclassT+intGtMidIndx(T*arr,intlft,intright)+{+intmid=(lftright)+((lft^right)1);+if(arr[lft]arr[mid])+{+if(arr[right]arr[mid])+rturnmid;+if(arr[right]arr[lft])+rturnlft;+rturnright;+}+ls+{+if(arr[right]arr[lft])+rturnlft;+if(arr[right]arr[mid])+rturnmid;+rturnright;+}+}+tmplatclassT+intPartSort(T*arr,intbgin,intnd)+{+intCur=bgin;+intPrv=Cur-1;+intkyIndx=GtMidIndx(arr,bgin,nd);+std::swap(arr[kyIndx],arr[nd]);+Tky=arr[nd];+whil(Curnd)+{+if(arr[Cur]ky++Prv!=Cur)+std::swap(arr[Prv],arr[Cur]);+++Cur;+}+++Prv;+std::swap(arr[Prv],arr[Cur]);+rturnPrv;+}+tmplatclassT+voidQuickSort_Nor(T*arr,intlft,intright)+{+if(arr==NULL
lft=right)+rturn;+stackint_s;+_s.push(lft);+_s.push(right);+whil(!_s.mpty())+{+intnd=_s.top();+_s.pop();+intbgin=_s.top();+_s.pop();+intdiv=PartSort(arr,bgin,nd);+if(div-1bgin)+{+_s.push(bgin);+_s.push(div-1);+}+if(div+1nd)+{+_s.push(div+1);+_s.push(nd);+}+}+}+intmain()+{+intarr[]={3,2,1,9,7,6,4,0,8};+QuickSort_Norint(arr,0,sizof(arr)/sizof(arr[0])-1);+for(intidx=0;idxsizof(arr)/sizof(arr[0]);++idx)+coutarr[idx]"";+coutndl;+systm("paus");+rturn0;+}
《计数排序》
+#includiostram+usingnamspacstd;+voidCountSort(int*arr,intsiz)+{+if(arr==NULL
siz=0)+rturn;+intmax=arr[0];+intmin=arr[0];+for(intidx=0;idxsiz;++idx)+{+if(maxarr[idx])+max=arr[idx];+if(minarr[idx])+min=arr[idx];+}+intrang=max-min+1;+int*tmp=nwint[rang];+mmst(tmp,0,rang*sizof(int));+for(intidx=0;idxsiz;++idx)+{+tmp[arr[idx]-min]++;+}+intindx=0;+for(intidx=0;idxrang;++idx)+{+whil(tmp[idx]--)+{+arr[indx++]=idx+min;+}+}+dlt[]tmp;+}+intmain()+{+intarr[]={3,7,5,2,1,3,7,4};+CountSort(arr,sizof(arr)/sizof(arr[0]));+systm("paus");+rturn0;+}
《基数排序》
intMaxDigit(int*arr,intsiz)+{+intdigit=0;+intmax=0;+intnumbr=1;+for(intidx=0;idxsiz;++idx)+{+if(maxarr[idx])+max=arr[idx];+}+whil(numbr=max)+{+digit++;+numbr*=10;+}+rturndigit;+}+void_MSDSort(int*arr,intlft,intright,intdigit,int*tmp)+{+intsiz=right-lft;+intradix=(int)pow(10,digit-1);+if(digit=0)+rturn;+intcount[10]={0};+for(intidx=lft;idxright;++idx)+{+count[arr[idx]/radix%10]++;+}++intstartAddr[10]={lft};+for(intidx=1;idx10;++idx)+{+startAddr[idx]=startAddr[idx-1]+count[idx-1];+}++for(intidx=lft;idxright;++idx)+{+tmp[startAddr[arr[idx]/radix%10]++]=arr[idx];+}+mmcpy(arr+lft,tmp+lft,siz*sizof(int));+for(intidx=0;idxsiz;++idx)+{+if(count[idx]=1)+continu;+intbgin=startAddr[idx]-count[idx];+intnd=startAddr[idx];+_MSDSort(arr,bgin,nd,digit-1,tmp);+}+}+voidMSDSort(int*arr,intsiz)+{+if(arr==NULL
siz=0)+rturn;+int*tmp=nwint[siz];+intdigit=MaxDigit(arr,siz);+_MSDSort(arr,0,siz,digit,tmp);+dlt[]tmp;+}
《归并排序》
//递归版本#includiostramusingnamspacstd;voidMrg(int*arr,int*tmp,intlft,intmid,intright){intbgin_1=lft;intnd_1=mid;intbgin_2=mid+1;intnd_2=right;intindx=bgin_1;whil(bgin_1=nd_1bgin_2=nd_2){if(arr[bgin_1]arr[bgin_2])tmp[indx++]=arr[bgin_1++];lstmp[indx++]=arr[bgin_2++];}whil(bgin_1=nd_1)tmp[indx++]=arr[bgin_1++];whil(bgin_2=nd_2)tmp[indx++]=arr[bgin_2++];}void_MrgSort(int*arr,int*tmp,intlft,intright){
//非递归版本voidMrg(int*arr,intlft,intmid,intright,int*tmp){intbgin_1=lft;intnd_1=mid;intbgin_2=mid+1;intnd_2=right;intindx=bgin_1;whil(bgin_1=nd_1bgin_2=nd_2){if(arr[bgin_1]arr[bgin_2])tmp[indx++]=arr[bgin_1++];lstmp[indx++]=arr[bgin_2++];}whil(bgin_1=nd_1)tmp[indx++]=arr[bgin_1++];whil(bgin_2=nd_2)tmp[indx++]=arr[bgin_2++];}void_MrgSort(int*arr,int*tmp,intsiz){intgap=1;whil(gapsiz)
个人觉得多写多练才是最重要的，所有的技巧都是基于代码量之上的，不要好高骛远，只有学会了造轮子才能更好地去利用。
感谢小伙伴们百忙之中
