本辑将会对笔试面试最常涉及到的12种排序算法(包括插入排序、二分插入排序、希尔排序、选择排序、冒泡排序、鸡尾酒排序、快速排序、堆排序、归并排序、桶排序、计数排序和基数排序)进行详解。每一种算法都有基本介绍、算法原理分析、图解演示、算法代码、笔试面试重点分析、笔试面试题等板块。
一、插入排序1）算法简介 插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。2）算法描述和分析一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
1、从第一个元素开始，该元素可以认为已经被排序
2、取出下一个元素，在已经排序的元素序列中从后向前扫描
3、如果该元素（已排序）大于新元素，将该元素移到下一位置
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5、将新元素插入到该位置后
6、重复步骤2~5
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。
最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。
最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数减去(n-1)次。
平均来说插入排序算法复杂度为O(n^2)。
因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。
3）算法图解
4）算法代码
// 插入排序（直接，折半，路插入，表插入）// 依次取出便利每一项 将每一项temp=a[j]和其之前的数进行比较，如果发现了比自己大的数 就将其放在当前j的位置 同时j–，继续用temp和之前的数进行比较，直到没有比自己大的数时结束。// 直接插入排序 void insertSort(int *a,int size) {if(size<2)return;int temp;int j;for(int i=1;i<size;i++){temp=a[i];for( j=i;j>0&&temp<a[j-1];j–){a[j]=a[j-1];}a[j]=temp;}print(a,size); } // 折半插入排序：// 折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。// 折半插入排序算法的具体操作为：在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low],末元素设置为a[high]，则轮比较时将待插入元素与a[m],其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。void binaryInsertSort(int *a,int size) {int low,high,m,temp,j;for (int i=1;i<size;++i){temp=a[i];low=0;high=i-1;/* if(a[i]>a[i-1]) //这句话可以稍微优化一下下速度 不影响结果continue;*/while (low<=high){m=(low+high)/2;if (temp<=a[m])high=m-1; //当程序跳出时 high指向的其实并不是 >=temp的值的位置 而是>=temp的值的左边的位置 所以….elselow=m+1;}for( j=i;j>high+1;–j)//所以 这里的high要加一哇a[j]=a[j-1];a[j]=temp;}print(a,size); }
5）考察点，重点和频度分析
把插入排序放在第一个的原因是因为其出现的频度不高，尤其是这里提到的直接排序算法，基本在笔试的选择填空问时间空间复杂度的时候才可能出现。毕竟排序速度比较慢，因此算法大题中考察的次数比较比较少。
6）笔试面试例题
例题1
请写出链表的插入排序程序
template<typename T> struct list_node {struct list_node<T> *next;T value; }; template<typename T> struct _list {struct list_node<T> *head;int size; }; template<typename T> void SortLink(struct _list<T> * link) {struct list_node<T> *pHead,*pRear,*p,*tp;if (!link) return;for (pHead=link->head,pRear=0;pHead;pHead=pHead->next) {for (tp=pHead,p=pHead->next;p;tp=p,p=p->next)if (pHead->value>=p->value)tp->next=p->next,p->next=pHead,pHead=p,p=tp;if (!pRear) link->head=pHead;else pRear->next=pHead;pRear=pHead;} } 例题2下列排序算法中最坏复杂度不是n(n-1)/2的是 DA.快速排序 B.冒泡排序 C.直接插入排序 D.堆排序二、二分插入排序1）算法简介 二分（折半）插入（Binary insert sort)排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。2）算法描述和分析一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下： 1、从第一个元素开始，该元素可以认为已经被排序 2、取出下一个元素，在已经排序的元素序列中二分查找到第一个比它大的数的位置 3、将新元素插入到该位置后 4、重复上述两步 1）稳定 2）空间代价：O(1) 3）时间代价：插入每个记录需要O(log i)比较，最多移动i+1次，最少2次。最佳情况O(n log n)，最差和平均情况O(n^2)。 二分插入排序是一种稳定的排序。当n较大时，总排序码比较次数比直接插入排序的最差情况好得多，但比最好情况要差，所元素初始序列已经按排序码接近有序时，直接插入排序比二分插入排序比较次数少。二分插入排序元素移动次数与直接插入排序相同，依赖于元素初始序列。3）算法图解『 不可能 』只存在於蠢人的字典里
