作者：寒小陽 時間：2013年9月。
出處：http://blog.csdn.net/han_xiaoyang/article/details/11596001渣慕。
聲明：版權所有逊桦，轉載請注明出處，謝謝匿情。
0炬称、前言
從這一部分開始直接切入我們計算機互聯(lián)網筆試面試中的重頭戲算法了据德，初始的想法是找一條主線棘利，比如數(shù)據(jù)結構或者解題思路方法善玫，將博主見過做過整理過的算法題逐個分析一遍(博主當年自己學算法就是用這種比較笨的刷題學的，囧)只洒，不過又想了想毕谴，算法這東西，博主自己學的過程中一直深感舀武，基礎還是非常重要的银舱，很多難題是基礎類數(shù)據(jù)結構和題目的思想綜合發(fā)散而來。比如說作為最基本的排序算法就種類很多诚欠，而事實上筆試面試過程中發(fā)現(xiàn)掌握的程度很一般粉寞，有很多題目唧垦，包括很多算法難題野芒，其母題或者基本思想就是基于這些經典算法的狞悲，比如說快排的partition算法丹拯，比如說歸并排序中的思想乖酬，比如說桶排序中桶的思想。
這里對筆試面試最常涉及到的12種排序算法(包括插入排序县昂、二分插入排序倒彰、希爾排序、選擇排序创淡、冒泡排序、雞尾酒排序汁针、快速排序施无、堆排序瑞躺、歸并排序、桶排序捞镰、計數(shù)排序和基數(shù)排序)進行了詳解岸售。每一種算法都有等板塊，希望能幫助大家真正理解這些排序算法酷鸦，并能使用這些算法的思想解決一些題臼隔。不多說了寄狼，下面就進入正題了。
一删咱、插入排序
1）算法簡介
插入排序（Insertion Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過。插入排序在實現(xiàn)上莺丑，通常采用in-place排序（即只需用到O(1)的額外空間的排序）著蟹，因而在從后向前掃描過程中梢莽，
。
2）算法描述和分析
一般來說昏名，插入排序都采用in-place在數(shù)組上實現(xiàn)涮雷。具體算法描述如下：
如果目標是把n個元素的序列升序排列，那么采用插入排序存在最好情況和最壞情況俱济。最好情況就是司蔬，序列已經是升序排列了，在這種情況下姨蝴，需要進行的比較操作需(n-1)次即可俊啼。最壞情況就是，序列是降序排列左医，那么此時需要進行的比較共有n(n-1)/2次授帕。插入排序的賦值操作是比較操作的次數(shù)減去(n-1)次。平均來說浮梢。因而跛十，插入排序不適合對于數(shù)據(jù)量比較大的排序應用。但是秕硝，如果需要排序的數(shù)據(jù)量很小芥映，例如，量級小于千远豺，那么插入排序還是一個不錯的選擇奈偏。 插入排序在工業(yè)級庫中也有著廣泛的應用，在STL的sort算法和stdlib的qsort算法中躯护，都將插入排序作為快速排序的補充惊来，用于少量元素的排序（通常為8個或以下）。
3）算法圖解棺滞、視頻演示
圖解：
視頻：插入排序舞蹈
)
4）算法代碼
void insertion_sort(int array[], int first, int last)
{
int i,j;
int temp;
for (i = first+1; i<=last;i++)
{
temp = array[i];
j=i-1;
//與已排序的數(shù)逐一比較裁蚁，大于temp時，該數(shù)后移
while((j>=first) && (array[j] > temp)) //當first=0继准，j循環(huán)到-1時枉证，由于[[短路求值]]，不會運算array[-1]
{
array[j+1] = array[j];
j--;
}
array[j+1] = temp; //被排序數(shù)放到正確的位置
}
}
5）考察點移必，重點和頻度分析
把插入排序放在第一個的原因是因為其出現(xiàn)的頻度不高室谚，尤其是這里提到的直接排序算法，基本在筆試的選擇填空問時間空間復雜度的時候才可能出現(xiàn)避凝。畢竟排序速度比較慢舞萄，因此算法大題中考察的次數(shù)比較比較少。
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倒脓、
A.快速排序 B.冒泡排序 C.直接插入排序
二、二分插入排序
1）算法簡介
二分（折半）插入（Binary insert sort)排序是一種在直接插入排序算法上進行小改動的排序算法含思。其與直接排序算法最大的區(qū)別在于崎弃，在速度上有一定提升甘晤。
2）算法描述和分析
一般來說，插入排序都采用in-place在數(shù)組上實現(xiàn)饲做。具體算法描述如下：
1）穩(wěn)定
2）空間代價：O(1)
3）時間代價：插入每個記錄需要O(log i)比較游沿，最多移動i+1次，最少2次肮砾。最佳情況O(n log n)诀黍，最差和平均情況O(n^2)。
二分插入排序是一種穩(wěn)定的排序仗处。，
。二分插入排序元素移動次數(shù)與直接插入排序相同旷档，依賴于元素初始序列模叙。
3）算法圖解、視頻演示
圖解：
視頻：二分插入排序
4）算法代碼
void BinInsertSort(int a[], int n)
{
int key, left, right, middle;
for (int i=1; i<n; i++)
{
key = a[i];
left = 0;
right = i-1;
while (left<=right)
{
middle = (left+right)/2;
if (a[middle]>key)
right = middle-1;
else
left = middle+1;
}
for(int j=i-1; j>=left; j--)
{
a[j+1] = a[j];
}
a[left] = key;
}
}
5）考察點鞋屈，重點和頻度分析
這個排序算法在筆試面試中出現(xiàn)的頻度也不高，但畢竟是直接排序算法的一個小改進算法故觅，同時二分查找又是很好的思想厂庇，有可能會在面試的時候提到，算法不難输吏，留心一下就會了权旷。
6）筆試面試例題
例題1、
A拄氯、二分插入排序 C它浅、冒泡排序 D译柏、快速排序
例題2、
(1)冒泡排序鄙麦；(2)選擇排序典唇；(3)插入排序；(4)二分插入排序胯府；(5)快速排序介衔；(6)堆排序；(7)歸并排序骂因；
三炎咖、希爾排序
1）算法簡介
希爾排序，也稱遞減增量排序算法寒波，因DL．Shell于1959年提出而得名乘盼，是插入排序的一種高速而穩(wěn)定的改進版本。
2）算法描述
希爾排序的時間復雜度與增量序列的選取有關议忽，例如希爾增量時間復雜度為O(n2)，而Hibbard增量的希爾排序的時間復雜度為O(N(5/4))十减，但是現(xiàn)今仍然沒有人能找出希爾排序的精確下界栈幸。
3）算法圖解、視頻演示
圖解：
視頻：希爾排序Shell Sort 舞蹈
4）算法代碼
#include <stdio.h>
int main()
{
const int n = 5;
int i, j, temp;
int gap = 0;
int a[] = {5, 4, 3, 2, 1};
while (gap<=n)
{
gap = gap * 3 + 1;
}
while (gap > 0)
{
for ( i = gap; i < n; i++ )
{
j = i - gap;
temp = a[i];
while (( j >= 0 ) && ( a[j] > temp ))
{
a[j + gap] = a[j];
j = j - gap;
}
a[j + gap] = temp;
}
gap = ( gap - 1 ) / 3;
}
}
5）考察點帮辟，重點和頻度分析
事實上希爾排序算法在筆試面試中出現(xiàn)的頻度也不比直接插入排序高速址，但它的時間復雜度并不是一個定值，所以偶爾會被面試官問到選擇的步長和時間復雜度的關系由驹，要稍微有點了解吧芍锚。算法大題中使用該方法或者其思想的題也不多。
6）筆試面試例題
例題1蔓榄、
程序略甥郑，需要O(n^2)次的比較
例題2逃魄、
，則：
冒泡排序一趟掃描的結果是 壹若；
初始步長為4的希爾（shell）排序一趟的結果是 嗅钻；
二路歸并排序一趟掃描的結果是 ；
快速排序一趟掃描的結果是 秃流；
堆排序初始建堆的結果是 柳弄。
四舶胀、選擇排序
1）算法簡介
選擇排序(Selection sort)是一種簡單直觀的排序算法。它的工作原理如下碧注。萍丐，
基茵。以此類推，直到所有元素均排序完畢壳影。
2）算法描述和分析
n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
掺栅。
，
氧卧。
選擇排序的交換操作介于0和(n-1)次之間假抄。選擇排序的比較操作為n(n-1)/2次之間。選擇排序的賦值操作介于0和3(n-1)次之間丽猬。比較次數(shù)O(n^2),比較次數(shù)與關鍵字的初始狀態(tài)無關宿饱，總的比較次數(shù)N=(n-1)+(n-2)+...+1=n*(n-1)/2。 交換次數(shù)O(n),最好情況是脚祟，已經有序谬以，交換0次；最壞情況是由桌，逆序为黎，交換n-1次邮丰。 交換次數(shù)比冒泡排序少多了，由于交換所需CPU時間比比較所需的CPU時間多铭乾，n值較小時剪廉，選擇排序比冒泡排序快。
| 最差時間復雜度 | О(n2) |
| 最優(yōu)時間復雜度 | О(n2) |
| 平均時間復雜度 | О(n2) |
| 最差空間復雜度 | О(n) total, O(1) |
3）算法圖解炕檩、視頻演示
圖解：
視頻：選擇排序Select Sort排序舞蹈
4）算法代碼
void selection_sort(int *a, int len)
{
register int i, j, min, t;
for(i = 0; i < len - 1; i ++)
{
min = i;
//查找最小值
for(j = i + 1; j < len; j ++)
if(a[min] > a[j])
min = j;
//交換
if(min != i)
{
t = a[min];
a[min] = a[i];
a[i] = t;
}
}
}
5）考察點斗蒋，重點和頻度分析
就博主看過的筆試面試題而言，選擇算法也大多出現(xiàn)在選擇填空中笛质，要熟悉其時間和空間復雜度泉沾，最好最壞的情況分別是什么，以及在那種情況下妇押，每一輪的比較次數(shù)等跷究。
6）筆試面試例題
例題1、
:
（到尾部） ；
:
潭袱。
例題2、
Ａ. 插入排序 Ｃ. 歸并排序 Ｄ. 選擇排序
五屯换、冒泡排序
1）算法簡介
冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數(shù)列与学，一次比較兩個元素彤悔，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復地進行直到沒有再需要交換索守，也就是說該數(shù)列已經排序完成晕窑。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數(shù)列的頂端。
2）算法描述
冒泡排序是與插入排序擁有相等的執(zhí)行時間，但是兩種法在需要的交換次數(shù)卻很大地不同谴忧。在最壞的情況很泊，冒泡排序需要O(n2)次交換，而插入排序只要最多O(n)交換沾谓。冒泡排序的實現(xiàn)（類似下面）通常會對已經排序好的數(shù)列拙劣地執(zhí)行（O(n2)）委造，而插入排序在這個例子只需要O(n)個運算。因此很多現(xiàn)代的算法教科書避免使用冒泡排序均驶，而用插入排序取代之昏兆。冒泡排序如果能在內部循環(huán)第一次執(zhí)行時，使用一個旗標來表示有無需要交換的可能妇穴，也有可能把最好的復雜度降低到O(n)爬虱。在這個情況，在已經排序好的數(shù)列就無交換的需要腾它。若在每次走訪數(shù)列時跑筝，把走訪順序和比較大小反過來，也可以稍微地改進效率瞒滴。有時候稱為往返排序曲梗，因為算法會從數(shù)列的一端到另一端之間穿梭往返。
| 最差時間復雜度 | O(n^2) |
| 最優(yōu)時間復雜度 | O(n) |
| 平均時間復雜度 | O(n^2) |
| 最差空間復雜度 | 總共O(n)妓忍，需要輔助空間O(1) |
3）算法圖解虏两、視頻演示
圖解：
視頻：舞動的排序算法 冒泡排序
4）算法代碼
#include <stdio.h>
void bubbleSort(int arr[], int count)
{
int i = count, j;
int temp;
while(i > 0)
{
for(j = 0; j < i - 1; j++)
{
if(arr[j] > arr[j + 1])
{ temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
i--;
}
}
int main()
{
//測試數(shù)據(jù)
int arr[] = {5, 4, 1, 3, 6};
//冒泡排序
bubbleSort(arr, 5);
//打印排序結果
int i;
for(i = 0; i < 5; i++)
printf("%4d", arr[i]);
}
5）考察點，重點和頻度分析
一般我們學到的第一個排序算法就是冒泡排序世剖，不得不說定罢，這個還真是一個很常見的考點，平均時間空間復雜度旁瘫，最好最壞情況下的時間空間復雜度祖凫，在不同情況下每一趟的比較次數(shù)，以及加標志位減少比較次數(shù)等酬凳，都是需要注意的地方蝙场。
6）筆試面試例題
例題1、
例題2、
事實上鳍咱，這道題放到冒泡排序這里不知道是不是特別合適降盹，只是有一種解法是類似冒泡的思想，如下解法一
每次遇到大寫字母就往后冒蓄坏，最后結果即為所求
#include <stdio.h>
#include <string.h>
//題目以及要求：把一個字符串的大寫字母放到字符串的后面，
//各個字符的相對位置不變丑念，不能申請額外的空間涡戳。
//判斷是不是大寫字母
int isUpperAlpha(char c){
if(c >= 'A' && c <= 'Z'){
return 1;
}
return 0;
}
//交換兩個字母
void swap(char *a, char *b){
char temp = *a;
*a = *b;
*b = temp;
}
char * mySort(char *arr, int len){
if(arr == NULL || len <= 0){
return NULL;
}
int i = 0, j = 0, k = 0;
for(i = 0; i < len; i++){
for(j = len - 1 - i; j >= 0; j--){
if(isUpperAlpha(arr[j])){
for(k = j; k < len - i - 1; k++){
swap(&arr[k], &arr[k + 1]);
}
break;
}
//遍歷完了字符數(shù)組，但是沒發(fā)現(xiàn)大寫字母脯倚，所以沒必要再遍歷下去
if(j == 0 && !isUpperAlpha(arr[j])){
//結束;
return arr;
}
}
}
//over:
return arr;
}
int main(){
char arr[] = "aaaaaaaaaaaaaaaaaaaaaaaAbcAdeBbDc";
printf("%s\n", mySort(arr, strlen(arr)));
return 0;
}
渔彰。
步驟如下
1、兩個指針p1和p2挠将，從后往前掃描
2胳岂、p1遇到一個小寫字母時停下， p2遇到大寫字母時停下舔稀，兩者所指向的char交換
3乳丰、p1， p2同時往前一格
代碼如下：
#include <stdio.h>
#include <string.h>
//判斷是不是大寫字母
int isUpperAlpha(char c){
if(c >= 'A' && c <= 'Z'){
return 1;
}
return 0;
}
//交換兩個字母
void swap(char *a, char *b){
char temp = *a;
*a = *b;
*b = temp;
}
char * Reorder(char *arr, int len){
if(arr == NULL || len <= 0){
return NULL;
}
int *p1 = arr;
int *p2 = arr;
While(p1<arr+len && p2<arr+len){
While( isUpperAlpha(*p1) ){
P1++;
}
While( !isUpperAlpha(*p2) ){
P2++;
}
swap(p1, p2)
}
//結束
return arr;
}
int main(){
char arr[] = "aaaaaaaaaaaaaaaaaaaaaaaAbcAdeBbDc";
printf("%s\n", Reorder(arr, strlen(arr)));
return 0;
}
六内贮、雞尾酒排序/雙向冒泡排序
1）算法簡介
雞尾酒排序等于是冒泡排序的輕微變形产园。不同的地方在于，而冒泡排序則僅從低到高去比較序列里的每個元素夜郁。他可以得到比冒泡排序稍微好一點的效能什燕，原因是冒泡排序只從一個方向進行比對(由低到高)，每次循環(huán)只移動一個項目竞端。
2）算法描述和分析
技俐；
。
啡邑。
。
雞尾酒排序最糟或是平均所花費的次數(shù)都是O(n^2)仇穗，但如果序列在一開始已經大部分排序過的話流部，會接近O(n)。
| 最差時間復雜度 | O(n^2) |
| 最優(yōu)時間復雜度 | O(n) |
| 平均時間復雜度 | O(n^2) |
3）算法圖解仪缸、視頻演示
圖解：
4）算法代碼
void CocktailSort(int *a,int nsize)
{
int tail=nsize-1;
for (int i=0;i<tail;)
{
for (int j=tail;j>i;--j) //第一輪贵涵，先將最小的數(shù)據(jù)排到前面
{
if (a[j]<a[j-1])
{
int temp=a[j];
a[j]=a[j-1];
a[j-1]=temp;
}
}
++i; //原來i處數(shù)據(jù)已排好序，加1
for (j=i;j<tail;++j) //第二輪恰画，將最大的數(shù)據(jù)排到后面
{
if (a[j]>a[j+1])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
tail--; //原tail處數(shù)據(jù)也已排好序宾茂，將其減1
}
}
5）考察點，重點和頻度分析
雞尾酒排序在博主印象中出現(xiàn)的頻度也不高拴还，用到它的算法題大題很少跨晴，選擇填空出現(xiàn)的話多以雙向冒泡排序的名稱出現(xiàn)，注意注意時間空間復雜度片林，理解理解算法應該問題就不大了端盆。
6）筆試面試例題
考點基本類似冒泡排序，請參考上一節(jié)
