寫在前邊：這篇文章又臭又長，純屬個(gè)人無聊總結(jié)之作，如果您恰好看見了锭亏，有恰好有興趣贷揽，建議您找個(gè)空閑時(shí)間閱讀。
[TOC]
排序算法在計(jì)算機(jī)界是很基礎(chǔ)赖钞，很重要的，對人類也是至關(guān)重要的，沒有排序算法般码，就難以把人類分成三六九等區(qū)別對待了，大家都平等了乱顾，比你窮的人還有沒有北京戶口的人都能跟你一起競爭高考名額和工作機(jī)會(huì)了板祝，那樣的世界是多么恐怖啊。
為了演示方便走净，此文排序的對象都是一個(gè)int類型的vector券时，其中交換兩個(gè)元素孤里，采用了位運(yùn)算，至于為什么橘洞，第一是我恰好會(huì)捌袜，第二是，我認(rèn)為這三行寫在一起有一種獨(dú)特的美感炸枣。
vec[i]=vec[j]^vec[i];
vec[j]=vec[j]^vec[i];
vec[i]=vec[j]^vec[i];
(看起來似乎有點(diǎn)畫蛇添足了虏等，還不如。sort()......)适肠。
1.菜鳥排序
這個(gè)排序算法博其，是所有學(xué)生最開始接觸編程的時(shí)候碰到的一個(gè)算法，其地位就像是>hello world迂猴！<在IT界的地位一般慕淡，所以必須放在開頭。
其思想相當(dāng)接近大多數(shù)常人的思維沸毁，從前向后峰髓，對每個(gè)位置，都從當(dāng)前位置開始息尺，向后面掃描携兵，如果發(fā)現(xiàn)一個(gè)元素比當(dāng)前位置的值大，就把它搂誉，交換過來徐紧。
這個(gè)算法，大約進(jìn)行（n到1求和）次比較操作炭懊，所以復(fù)雜度是O(n^2)并级。
/*
noob sort
*/
int noob_sort(vector<int>& vec )
{
int i,j;
for(i=0;i<vec.size()-1;i++)
{
for(j=i+1;j<vec.size();j++)
{
if(vec[j]>vec[i])
{
vec[i]=vec[j]^vec[i];
vec[j]=vec[j]^vec[i];
vec[i]=vec[j]^vec[i];
}
}
}
return 0;
}
2. 選擇排序（selected sort）
一般同學(xué)們學(xué)到了上面那個(gè)算法，老師們就會(huì)指出侮腹，其中的很多交換是不必要的嘲碧，如果我們先找出當(dāng)前元素后面最大或者最小的元素，就能只用一次交換將一個(gè)元素放到正確的位置父阻。于是就有了如下算法愈涩，用一個(gè)變量存儲(chǔ)，后邊的元素中最大或最小的元素下標(biāo)加矛，在遍歷完之后才進(jìn)行交換操作履婉，減少了交換的次數(shù)，提高了效率斟览。
不過它的復(fù)雜度依然是O(n^2)毁腿，因?yàn)檫@種優(yōu)化帶來的效果是操作次數(shù)常數(shù)倍的減少，決定這個(gè)算法效率的關(guān)鍵是比較的次數(shù)，這一類依賴于比較的算法狸棍，可以嚴(yán)格證明它們的復(fù)雜度是有下限的，稍后將會(huì)看到這樣的算法味悄。
/*
selected sort
*/
int selected_sort(vector<int>& vec )
{
int i,j,k;
for(i=0;i<vec.size()-1;i++)
{
k= i;
for(j=i+1;j<vec.size();j++)
{
if(vec[j]>vec[k])
{
k=j;
}
}
vec[i]=vec[k]^vec[i];
vec[k]=vec[k]^vec[i];
vec[i]=vec[k]^vec[i];
}
return 0;
}
3. 冒泡排序（bubble sort）
這個(gè)算法的思想是從左往右去遍歷數(shù)組草戈，每次比較相鄰兩個(gè)元素的大小，如果其大小和你需要的大小關(guān)系相反（假設(shè)需要從大到小排序侍瑟，那么你需要的排序結(jié)果左邊的元素一定大于等于右邊的元素）唐片，就交換兩個(gè)元素的位置，這樣一次從左到右的遍歷涨颜，就能把最小的元素放到最后面去费韭，這個(gè)最小的元素也就走到了它該去的地方，完成了歷史的使命庭瑰。第二次遍歷的時(shí)候也就不用考慮這個(gè)元素了星持，具體來講就是遍歷范圍的右邊界減去1.
這個(gè)過程類似于每次把一個(gè)比較輕的泡泡冒出水面，所以這個(gè)算法叫做冒泡法弹灭。對于一個(gè)長度為n的數(shù)組督暂，這個(gè)算法第i趟的時(shí)候需要比較n-i次，所以算法的復(fù)雜度依然是O(n^2)穷吮。
/*
bubble sort
*/
int bubble_sort(vector<int>& vec )
{
int i,j;
for(i=vec.size()-1;i>0;i--)
{
for(j=1;j<i+1;j++)
{
if(vec[j]>vec[j-1])
{
vec[j]=vec[j-1]^vec[j];
vec[j-1]=vec[j-1]^vec[j];
vec[j]=vec[j-1]^vec[j];
}
}
}
return 0;
}
3. 雞尾酒排序（cocktail sort）
這個(gè)算法是冒泡排序的一個(gè)變種逻翁，它的具體做法就是來回冒泡，每次把一個(gè)泡泡冒到右邊捡鱼，然后把一個(gè)石子沉到水底八回，代碼實(shí)現(xiàn)方面，用兩個(gè)變量存儲(chǔ)遍歷的左右邊界驾诈，每次從左向右遍歷到頭就將右邊界減一后向左遍歷缠诅，如此，直到左右邊界重合乍迄，排序就完成了滴铅。這個(gè)算法相比于冒泡排序，性能上沒有優(yōu)化就乓，復(fù)雜度依然是n^2只是過程顯得更加酷炫狂拽汉匙，估計(jì)也就因此得名雞尾酒，如果是中國人發(fā)明的估計(jì)應(yīng)該命名洗剪吹算法生蚁。
/*
cocktail sort
*/
int cocktail_sort(vector<int>& vec )
{
int i=0,j=vec.size()-1,k;
while(j>i)
{
for(k=i;k<=j-1;k++)
{
if(vec[k]<vec[k+1])
{
vec[k]=vec[k+1]^vec[k];
vec[k+1]=vec[k+1]^vec[k];
vec[k]=vec[k+1]^vec[k];
}
}
j--;
if(j>i)
{
for(k=j-1;k>=i;k--)
{
if(vec[k]<vec[k+1])
{
vec[k]=vec[k+1]^vec[k];
vec[k+1]=vec[k+1]^vec[k];
vec[k]=vec[k+1]^vec[k];
}
}
i++;
}
}
return 0;
}
4. 插入排序（insertion sort）
這個(gè)算法的思想依次選取待排數(shù)組中間的元素噩翠，插入到已經(jīng)有序的數(shù)組內(nèi)合適的位置，最終得到的元素序列就是有序的邦投。初始的時(shí)候伤锚，我們從待排數(shù)組左邊選擇一個(gè)元素當(dāng)作是已經(jīng)有序的數(shù)組。
分析它的復(fù)雜度我們主要看發(fā)生的比較的次數(shù)志衣，插入的時(shí)候我們是有序數(shù)列的從一側(cè)向另一側(cè)遍歷屯援，如果運(yùn)氣好猛们，比較一次就找到了它應(yīng)該在的位置，如果數(shù)組本身是反序的狞洋，你每次都要從左到右把已經(jīng)有序的部分比較完才能找到其應(yīng)該的位置弯淘。所以這個(gè)算法的復(fù)雜度和以上幾個(gè)有了不一樣的地方，有最好的和最壞的情況吉懊，這種情形用復(fù)雜度的期望來衡量復(fù)雜度是比較自然而然的做法庐橙。
總共需要插入n次，第i次插入操作平均會(huì)比較（i-1）2次借嗽，所以他的期望的復(fù)雜度為O（n2/2）==O(n2).
插入排序?qū)嶋H上可以優(yōu)化到O(nlog(n),插入的時(shí)候采用二分法插入即可态鳖。
/*
insertion sort
*/
int insertion_sort(vector<int>& vec )
{
int i,j;
for(i=1;i<vec.size();i++)
{
for(j=i;j>0;j--)
{
if(vec[j]>vec[j-1])
{
vec[j]=vec[j-1]^vec[j];
vec[j-1]=vec[j-1]^vec[j];
vec[j]=vec[j-1]^vec[j];
}
else{break;}
}
}
return 0;
}
5. 堆排序（heap sort）
堆排序是利用了堆的特性，根據(jù)大根堆的定義恶导，堆的根就是整個(gè)堆當(dāng)中最大的一個(gè)元素浆竭，那么我們不斷的去取出這個(gè)根（由于取出后會(huì)重建堆，導(dǎo)致新的根被選出來）惨寿，那么得到的數(shù)列就是有序的了兆蕉。
所以說這個(gè)算法關(guān)鍵在建一個(gè)堆，此處采用線性存儲(chǔ)結(jié)構(gòu)缤沦，直接用數(shù)組存儲(chǔ)堆虎韵，為了原地排序，我們?nèi)〕龆训母蟾追希亟ǘ寻叮@樣尾端就會(huì)空出一個(gè)位置，把取出的元素放到這個(gè)位置企量，等堆的元素個(gè)數(shù)為1的時(shí)候测萎，數(shù)組就有序了。
若我們不看堆的操作届巩，這個(gè)算法就需要n-1次操作就能完成任務(wù)啦硅瞧，現(xiàn)實(shí)是我們必須考慮每次取出堆頭后堆的重建。由于堆是完全二叉樹恕汇，所以這個(gè)樹的深度最多l(xiāng)og(n)+1,根據(jù)堆調(diào)整過程腕唧，最多l(xiāng)og(n)次的比較交換就能完成調(diào)整。所以算法復(fù)雜度為O（n*log(n)）瘾英，這個(gè)數(shù)字就是比較類算法的復(fù)雜度的下限枣接，可見它是一種很快的算法。
/*
heap sort
*/
int rebuild_heap(vector<int>& vec,int n,int size)
{
int largest=n;
if(2*n>size){return 0;}
if(2*n<=size)
{
if(vec[n]<vec[2*n])
{
largest=2*n;
}
else largest=n;
}
if(2*n+1<=size)
{
if(vec[2*n+1]>vec[largest])
{
largest=2*n+1;
}
}
if(largest!=n)
{
vec[n]=vec[n]^vec[largest];
vec[largest]=vec[n]^vec[largest];
vec[n]=vec[n]^vec[largest];
rebuild_heap(vec,largest,size);
}
return 0;
}
int build_heap(vector<int>& vec )
{
for(int i=vec.size()-1;i>0;i--)
{
rebuild_heap(vec,i,vec.size()-1);
}
return 0;
}
int heap_sort(vector<int>& vec )
{
int i,size;
size=vec.size()-1;
/*build heap*/
build_heap(vec);
for(i=size;i>1;i--)
{
vec[1]=vec[size]^vec[1];
vec[size]=vec[size]^vec[1];
vec[1]=vec[size]^vec[1];
/*1和size位置的值交換*/
size--;
rebuild_heap(vec, 1, size);
}
return 0;
}
桶排序（ bucket sort）
這個(gè)算法的思想是缺谴，給出一列有順序的桶但惶，每個(gè)桶編上號(hào)，從待排數(shù)列中取出一個(gè)元素，放到對應(yīng)標(biāo)號(hào)的桶里膀曾，這個(gè)操作在程序?qū)崿F(xiàn)的時(shí)候極其方便县爬，用數(shù)組的下標(biāo)作為桶號(hào)，只需要一個(gè)賦值語句即可添谊，對應(yīng)桶的位置上的數(shù)字财喳，用來標(biāo)記桶號(hào)在待排數(shù)組內(nèi)出現(xiàn)的次數(shù)。
輸出的時(shí)候碉钠，按順序掃描桶纲缓，若桶是空的卷拘，就跳過喊废，若不空就根據(jù)桶中的數(shù)字輸出相應(yīng)個(gè)數(shù)的元素。
根據(jù)原理栗弟，很顯然污筷，只需要一次遍歷就能把元素放進(jìn)桶內(nèi)，再一次便利桶即可輸出有序的元素乍赫，為保證每個(gè)元素都能找到屬于自己的桶瓣蛀，桶的個(gè)數(shù)需要包含待排數(shù)組的最小和最大值中間的所以情況。倘若待排數(shù)組長度n雷厂，桶個(gè)數(shù)m惋增，那么算法的空間復(fù)雜度就是O(m)，時(shí)間復(fù)雜度就是O(n+m).
這似乎打破了前述的nlog(n)的復(fù)雜度下限改鲫，其實(shí)不然诈皿，之前說的復(fù)雜度下限，是直的基于比較的排序算法像棘，而桶排序是不需要比較的稽亏。
/*
bucket sort
*/
int bucket_sort(vector<int>& vec )
{
vector<int> bucket;
bucket.resize(vec.size(),0);
/*造桶*/
int i;
for(i=0;i<vec.size();i++)
{
bucket[vec[i]]++;
}
vec.resize(0);
for(i=0;i<bucket.size();i++)
{
while(bucket[i]!=0)
{
vec.push_back(i);
bucket[i]--;
}
}
return 0;
}
proxmap sort
這東西沒找著中文翻譯，據(jù)我猜測 proximal是近似的意思缕题，map是映射截歉，它的中文應(yīng)該是近似映射排序吧。
這是桶排序的升級(jí)版烟零，桶排序最大的缺點(diǎn)就是浪費(fèi)空間瘪松，因?yàn)橥芭判蛑校蟛糠值耐岸际强罩南前ⅲ杂腥颂岢雒總€(gè)桶裝某個(gè)范圍內(nèi)的元素凉逛，所以它直接指定定一個(gè)桶的范圍，然后在入桶的時(shí)候采用插入排序群井，最后遍歷桶輸出状飞。
/*
proxmap sort
*/
int proxmap_sort(vector<int>& vec )
{
vector<vector<int> > bucket;
bucket.resize(vec.size()/10+1);
/*造桶*/
int i,j,k,* n,* m;
//入桶
for(i=0;i<vec.size();i++)
{
for(j=1;j<=bucket.size();j++)
{
if(vec[i]<10*j)
{
bucket[j-1].push_back(vec[i]);
for(k=bucket[j-1].size()-1;k>0;k--)
{
m=&bucket[j-1][k];
n=&bucket[j-1][k-1];
if(*n<*m)
{
*n=*n^(*m);
*m=*n^(*m);
*n=*n^(*m);
}
}
break;
}
}
}
//出桶
vec.resize(0);
for(j=0;j<bucket.size();j++)
{
while(bucket[j].size())
{
vec.push_back(bucket[j].back());
bucket[j].pop_back();
}
}
return 0;
}
基數(shù)排序（radix sort）
這個(gè)基數(shù)也就是數(shù)學(xué)中各種進(jìn)制數(shù)字表示法的基數(shù)，由于我們用的是十進(jìn)制，在此處诬辈，基數(shù)就是10酵使。
這個(gè)算法分配十個(gè)桶，標(biāo)號(hào)0到9焙糟，先按照個(gè)位數(shù)入桶口渔，然后從左到右遍歷桶，將元素取出穿撮，按照十位數(shù)字入桶缺脉，以此類推。
分析一下這個(gè)操作悦穿，就知道攻礼，按照個(gè)位數(shù)入桶的時(shí)候，個(gè)位數(shù)小的第二輪會(huì)先入桶栗柒，也就是說礁扮，第二輪完畢之后，每個(gè)桶內(nèi)十位數(shù)相同瞬沦，但是個(gè)位數(shù)小的被壓在下面太伊。繼續(xù)分析，到百位數(shù)入桶的時(shí)候逛钻，每個(gè)桶十位數(shù)小的被壓在下面僚焦，那這些被壓在下邊的十位數(shù)相同的一組，他們的個(gè)位數(shù)是否有序呢曙痘？顯然是有的芳悲，其大小方向，取決于我們上一層的桶的取出方式為保持小的壓在下面的性質(zhì)屡江，出桶應(yīng)該采用先進(jìn)先出的方式芭概。
/*
radix sort
*/
int radix_sort(vector<int>& vec )
{
int i,temp=vec.size();
vector< vector<int> > bucket;
bucket.resize(10);
/*造桶*/
for(i=vec.size()-1;i>=0;i--)
{
bucket[vec[i]%10].push_back(vec[i]);
}
vec.resize(0);
for(i=0;i<10;i++)
{
while(bucket[i].size()>0)
{
vec.push_back(bucket[i].back());
bucket[i].pop_back();
}
}
for(i=vec.size()-1;i>=0;i--)
{
bucket[(vec[i]/10)%10].push_back(vec[i]);
}
vec.resize(0);
for(i=0;i<10;i++)
{
while(bucket[i].size()>0)
{
vec.push_back(bucket[i].back());
bucket[i].pop_back();
}
}
return 0;
}
耐心排序（patience sort）
這個(gè)排序的思想是依次取出待排數(shù)組元素，從左往右查找桶惩嘉，只有小于桶底元素才能入桶罢洲，如果沒有桶或者元素不小于任何一個(gè)桶的桶底元素，就新建一個(gè)桶文黎，把這個(gè)元素放到桶底部惹苗。
這一邊操作結(jié)束的結(jié)果就是，把待排數(shù)組分成了很多段耸峭，在每個(gè)桶分別插入排序就能得到有序數(shù)組桩蓉。
插入排序的最壞情況是在反序的時(shí)候出現(xiàn)的，這個(gè)算法相比插入排序劳闹，將那些反序得太離譜的元素進(jìn)行了調(diào)整院究，減小了問題規(guī)模洽瞬。
/*
patience sort
*/
int patience_sort(vector<int>& vec)
{
vector< vector<int> > bucket;
int i,j,k,cur_bucket,len=vec.size();
for(i=0;i<len;i++)
{
cur_bucket=-1;
for(j=0;j<bucket.size();j++)
{
if(bucket[j][0]>=vec[i])
{
cur_bucket=j;break;
}
}
if(cur_bucket==-1)
{
bucket.push_back(*(new vector<int>));
bucket.back().push_back(vec[i]);
}
else
{
bucket[cur_bucket].push_back(vec[i]);
}
}
vec.resize(0);
for(k=0;k<bucket.size();k++)
{
while(bucket[k].size()!=0)
{
vec.push_back(bucket[k].back());
bucket[k].pop_back();
}
}
//插入排序
for(k=1;k<len;k++)
{
for(j=k;j>0;j--)
{
if(vec[j]<vec[j-1])
{
vec[j]=vec[j]^vec[j-1];
vec[j-1]=vec[j]^vec[j-1];
vec[j]=vec[j]^vec[j-1];
}
}
}
return 0;
}
閃電排序（flash sort）
這也是proximap排序的一種升級(jí)算法，對于長度為n的桶业汰，它把數(shù)組最大值和最小值之間分成n個(gè)區(qū)間伙窃，落在同個(gè)區(qū)間的放進(jìn)同一個(gè)桶，入桶的時(shí)候進(jìn)行插入排序样漆，最后按順序遍歷桶为障，得到的數(shù)組就是有序的。
/*
flash sort
*/
int flash_sort(vector<int>& vec )
{
vector<vector<int> > bucket;
bucket.resize(vec.size());
/*造桶*/
int i,j,max=0,min=0,*m,*n,k;
for(i=0;i<vec.size();i++)
{
if(vec[i]>max)max=vec[i];
if(vec[i]<min)min=vec[i];
}
for(i=0;i<vec.size();i++)
{
j=(vec.size()-1)*(vec[i]-min)/(max-min);
bucket[j].push_back(vec[i]);
for(k=bucket[j].size()-1;k>0;k--)
{
m=&bucket[j][k];
n=&bucket[j][k-1];
if(*n<*m)
{
*n=*n^(*m);
*m=*n^(*m);
*n=*n^(*m);
}
}
}
vec.resize(0);
for(j=0;j<bucket.size();j++)
{
while(bucket[j].size())
{
vec.push_back(bucket[j].back());
bucket[j].pop_back();
}
}
return 0;
}
計(jì)數(shù)排序（ counting sort）
這個(gè)算法的核心思想是放祟，如果待排數(shù)組中比一個(gè)元素小的有k個(gè)鳍怨，那么這個(gè)元素就該放在第k+1個(gè)位置上。
當(dāng)然對待重復(fù)的元素跪妥，需要特殊處理鞋喇，假設(shè)有m個(gè)元素都發(fā)現(xiàn)數(shù)組中有k個(gè)元素比自己小，他們肯定不能全部擠在k+1號(hào)坑骗奖，顯然确徙，它們應(yīng)該占據(jù)k+1到k+m這m個(gè)坑醒串。
由于對每個(gè)元素执桌，我們都需要遍歷整個(gè)數(shù)組來統(tǒng)計(jì)比它小的元素個(gè)數(shù)，所以這個(gè)算法復(fù)雜度應(yīng)該為O(n^2).
/*
counting sort
*/
int counting_sort(vector<int>& vec )
{
int i,j,count;
vector<int> bucket;
bucket.resize(vec.size(),-1000);
/*造桶*/
for(i=0;i<vec.size();i++)
{
count=0;
for(j=0;j<vec.size();j++)
{
if(vec[j]<vec[i]&&(j!=i))
{
count++;
}
}
while(bucket[count]!=(-1000))
{
count++;
}
bucket[count]=vec[i];
}
vec=bucket;
return 0;
}
圈排序（ cycle sort）
如果你看懂了計(jì)數(shù)排序芜赌，你也許會(huì)想到仰挣，它并不是原地算法，因?yàn)橥ㄟ^對某個(gè)元素計(jì)數(shù)之后缠沈，你知道了這個(gè)元素應(yīng)該去的位置膘壶，但是在原地那個(gè)位置上還占著一個(gè)不知該放在哪里的元素。所以我們的做法是建立一個(gè)新的數(shù)組來安放排好序的元素洲愤，最后賦值給原數(shù)組颓芭。當(dāng)然為了節(jié)約能源，你也可以建一個(gè)數(shù)組用于保存每個(gè)位置應(yīng)該放的元素的標(biāo)號(hào)（因?yàn)閷?shí)際排序不可能只排關(guān)鍵字柬赐，必然有數(shù)據(jù)域）亡问，最后再根據(jù)標(biāo)號(hào)去讓各個(gè)元素歸位，不過這樣操作依然不是最理想的肛宋。
圈排序解決了這個(gè)問題州藕，把計(jì)數(shù)排序升級(jí)成了原地排序。
它的思想是這樣的：當(dāng)你找到一個(gè)a元素應(yīng)該放在1號(hào)位酝陈，而1號(hào)位被另一個(gè)元素b占著床玻，你就把b元素取出，然后把a(bǔ)放到1號(hào)位沉帮，給a本來的位置放一個(gè)空標(biāo)記锈死。接著尋找b應(yīng)該放在哪里贫堰。最終你一定會(huì)找到一個(gè)元素應(yīng)該放在a原來的位置，由于這個(gè)位置是空的待牵，直接把元素放在此處就結(jié)束了严嗜，這樣的一系列操作構(gòu)成一個(gè)圈，每個(gè)元素移動(dòng)一次洲敢，就能讓一個(gè)圈上所有元素歸位漫玄。
這里有個(gè)confused的地方，就是压彭，你為什么知道能夠找到這樣的圈睦优？
這背后是有數(shù)學(xué)原理的，這種排序前和排序之后的映射關(guān)系在抽象代數(shù)中稱作置換壮不，而上述的圈稱作輪換汗盘，就是一個(gè)集合到自身的映射，可以嚴(yán)格證明询一，每個(gè)置換都能寫成幾個(gè)不相交的輪換乘積形式隐孽，此處只擺出結(jié)論，不做證明健蕊。
/*
cycle sort
*/
int cycle_sort(vector<int>& vec)
{
int i, j, temp,count;
/*造桶*/
for (i = 0; i<vec.size(); i++)
{
temp = vec[i];
while (1)
{
count = 0;
for (j = 0; j<vec.size(); j++)
{
if (vec[j]<temp && (j != i))
{
count++;
}
}
while (vec[count] == temp)
{
if (count == i)break;
count++;
}
temp = temp^vec[count];
vec[count] = temp^vec[count];
temp = temp^vec[count];
if (i == count)break;
}
}
return 0;
}
地精 排序（gnome sort）
這個(gè)算法我認(rèn)為跟他的名字很搭調(diào)菱阵，地精就是生活在花園里的一種精靈，他們喜歡在土里鉆來鉆去缩功。
這個(gè)算法具體操作概括為晴及，先從左往右進(jìn)行相鄰元素比較，當(dāng)發(fā)現(xiàn)一個(gè)元素不滿足需要的大小關(guān)系的時(shí)候嫡锌，就交換他們?nèi)缓笳{(diào)轉(zhuǎn)方向向左邊冒泡虑稼，直到相鄰元素滿足大小關(guān)系的時(shí)候，停止冒泡势木。
按照這個(gè)過程蛛倦，左邊的一部分元素總是有序的，每次地精抓住一個(gè)元素把它插入到有序的序列內(nèi)啦桌，所以這其實(shí)是插入排序的低配版溯壶，因?yàn)椴迦肱判驅(qū)嶋H上在插入操作的時(shí)候可以優(yōu)化到O(log(n),也就是二分法插入。
/*
gnome sort
*/
int gnome_sort(vector<int>& vec )
{
int i;
for(i=0;i<(int)(vec.size())-1;)
{
if(i==-1)i++;
if(vec[i]<vec[i+1])
{
vec[i]=vec[i+1]^vec[i];
vec[i+1]=vec[i+1]^vec[i];
vec[i]=vec[i+1]^vec[i];
i--;
}
else
{
i++;
}
}
return 0;
}
珠排序（bead sort）
這個(gè)算法有種讓人眼前一亮的感覺震蒋，維基百科頁面
講的會(huì)更加清楚茸塞，這個(gè)算法按照理論，只需要把珠子穿在一系列棍子上查剖，在‘duang’的一敲钾虐，排序就完成了。不過現(xiàn)實(shí)很骨感笋庄，它只能排整數(shù)列效扫，并且在編程的時(shí)候倔监，復(fù)雜度也是n^2級(jí)別，但是這種想法的確讓人驚嘆菌仁，發(fā)明這個(gè)算法的人真的是天才浩习。
這個(gè)算法實(shí)際上基本是不可用的，不過我還是寫了一個(gè)實(shí)現(xiàn)济丘。
/*
bead sort
*/
int bead_sort(vector<int>& vec)
{
int i,j;
vector<int> temp;
temp.resize(vec.size(),0);
/*下落*/
for (i = 0; i<vec.size();i++)
{
for (j=0;j<vec.size();j++)
{
if (vec[j] >= i + 1)temp[i]++;
}
}
vec.resize(0);
vec.resize(temp.size(),0);
for (i = 0; i<vec.size();i++)
{
for (j=0;j<vec.size();j++)
{
if (temp[j] >= i + 1)vec[i]++;
}
}
return 0;
}
快速排序（quick sort）
這個(gè)算法采用的是分治法的思想谱秽，選取一個(gè)元素，然后遍歷整個(gè)數(shù)組摹迷，小于等于這個(gè)元素的都放在這個(gè)元素左邊疟赊，其余的放在它右邊。這樣數(shù)組就被分為三部分峡碉，這個(gè)元素本身已經(jīng)處于正確的位置上近哟，不需要再移動(dòng)，而左右兩部分都是無序的鲫寄，但是左邊部分的元素的正確位置只可能在左邊吉执，所以只要將左右兩邊分別排序，整個(gè)數(shù)組都有序了地来。
實(shí)現(xiàn)的時(shí)候戳玫，數(shù)組頭尾各放一個(gè)指針（抽象意義的），左邊指針向右移動(dòng)直到有大于指定元素的時(shí)候停下來靠抑，右邊指針也類似量九，等兩邊指針都停下來了适掰，就進(jìn)行一次交換颂碧，最終兩個(gè)指針相遇的時(shí)候,再中間放上之前指定的那個(gè)元素，就完成了數(shù)組的分片操作类浪。
遞歸的調(diào)用這個(gè)過程载城，最終得到的數(shù)組就是有序的。
由于這個(gè)算法遞歸深度為log（n）到n之間费就，它的復(fù)雜度也在n2到nlogn之間诉瓦，實(shí)際上他的平均復(fù)雜度是O（nlogn），既然他的名字叫做快速排序它總不能打自己臉來個(gè)n2復(fù)雜度吧力细。
/*
quick sort
*/
int quick_sort(vector<int>& vec,int left,int right)
{
int i=left+1,j=right,k,temp;
if(left>=right)return 0;
temp=vec[left];
while(i<j)
{
while(vec[left]>=vec[i])
{
if(i==j)break;
vec[i-1]=vec[i];
i++;
}
while(vec[left]<vec[j])
{
if(i==j)break;
j--;
}
if(i<j)
{
vec[i]=vec[i]^vec[j];
vec[j]=vec[i]^vec[j];
vec[i]=vec[i]^vec[j];
}
}
vec[k]=temp;
quick_sort(vec,left,i-2);
quick_sort(vec,i,right);
return 0;
}
歸并排序（merge sort）
歸并排序的思想也是挺直觀的睬澡，對于已經(jīng)有序的兩個(gè)（或者n個(gè)）數(shù)列，我們只需要比較隊(duì)列頭部兩個(gè)元素就能找出最終合并后數(shù)列的最大or最小元素眠蚂。
假設(shè)我們需要從大到小排列煞聪，每次比較后把兩個(gè)隊(duì)頭中大的那個(gè)放到新的隊(duì)列，然后從待排隊(duì)列中剔除它逝慧，直到其中一個(gè)列沒有元素之后昔脯，就把另一列全部接到已經(jīng)排序好的數(shù)列后邊啄糙。
算法實(shí)現(xiàn)上，通過設(shè)置兩個(gè)隊(duì)頭指針（抽象意義）云稚，用移動(dòng)指針來表示元素的剔除隧饼，實(shí)現(xiàn)原地操作（當(dāng)然就增加了時(shí)間復(fù)雜度）。
同時(shí)也用了分治法静陈，先歸并排序左半個(gè)數(shù)列燕雁，再歸并排序右半邊數(shù)列，最后歸并排序整個(gè)數(shù)列鲸拥。
/*
merge sort
*/
int merge_sort(vector<int>& vec,int l,int h)
{
if(l>=h)return 0;
int i,j,k,m,n;
i=(h-l+1)/2;
j=h-l+1-i;
m=l;
n=l+i;
merge_sort(vec,l,l+i-1);
merge_sort(vec,l+i,h);
for(;(m<n)&&(n<=h);)
{
if(vec[m]>=vec[n])
{
m++;
}
else
{
for(k=n;k>m;k--)
{
vec[k]=vec[k]^vec[k-1];
vec[k-1]=vec[k]^vec[k-1];
vec[k]=vec[k]^vec[k-1];
}
n++;
m++;
}
}
return 0;
}
strand sort
這個(gè)算法首先給出一個(gè)有序數(shù)組（實(shí)際上選取待排數(shù)組中的第一個(gè)贵白，就是一個(gè)有序數(shù)組了），然后遍歷數(shù)組中余下的部分找到一個(gè)有序子列崩泡，具體做法是選一個(gè)元素作為子列開頭禁荒，往后遍歷若找到一個(gè)元素小于子列的尾部元素（這里是指的從大到小排列的情形），就從待排數(shù)組剔除這個(gè)元素角撞，然后將它接到子列尾部呛伴。
最后將有序數(shù)組和子列歸并排序，直到待排數(shù)組為空谒所。
/*
strand sort
*/
int strand_sort(vector<int>& vec)
{
vector<int> temp;//'有序列'
temp.push_back(vec[0]);
vec.erase(vec.begin());
vector<int>::iterator i;
int j,k,m,n;
while(1)
{
n=temp.size();
if (vec.size() == 0)break;
for(i=vec.begin();i!=vec.end();)
{
if(i==vec.begin())
{
temp.push_back(*i);
i++;
continue;
}
if(*i<=temp.back())
{
temp.push_back(*i);
i=vec.erase(i);
}
else
{
i++;
}
}
if(n==temp.size())break;
vec.erase(vec.begin());
m = 0;
for(;(m<n)&&(n<=temp.size()-1);)
{
if(temp[m]>=temp[n])
{
m++;
}
else
{
for(k=n;k>m;k--)
{
temp[k]=temp[k]^temp[k-1];
temp[k-1]=temp[k]^temp[k-1];
temp[k]=temp[k]^temp[k-1];
}
n++;
m++;
}
}
}
vec = temp;
return 0;
}
希爾排序（shell sort）
希爾排序是選擇一系列的間隔热康，對每個(gè)間隔把元素等距離的分為若干組，每組分別進(jìn)行插入排序劣领。
這個(gè)間隔序列的選取應(yīng)該是遞減的姐军，并且最后一個(gè)間隔是1.這個(gè)算法相比于插入排序，優(yōu)勢在于當(dāng)間隔不為1的時(shí)候進(jìn)行的排序尖淘，實(shí)際上相當(dāng)于在整個(gè)數(shù)列中奕锌，讓元素跨過多元素進(jìn)行移動(dòng)，這樣解決了逆序帶來的復(fù)雜度的提升村生。
/*
shell sort
*/
int shell_sort(vector<int>& vec)
{
int interval=10,i,j,k,len=vec.size(),cur_len;
while(interval>0)
{
for(i=0;i<interval;i++)
{
cur_len=(len/interval)+(i<len%interval?1:0);
for(j=0;j<cur_len-1;j++)
{
for(k=0;k<cur_len-1-i;k++)
{
if(vec[i+interval*k]<vec[i+interval*(k+1)])
{
vec[i+interval*k]=vec[i+interval*k]^vec[i+interval*(k+1)];
vec[i+interval*(k+1)]=vec[i+interval*k]^vec[i+interval*(k+1)];
vec[i+interval*k]=vec[i+interval*k]^vec[i+interval*(k+1)];
}
}
}
}
interval=interval/1.3;
}
return 0;
}
梳子排序（comb sort）
這個(gè)算法就是希爾排序的冒泡版本惊暴，因?yàn)樗凑盏染嚯x的方法把元素分為很多組，分別冒泡排序趁桃，就像梳子的齒一樣辽话，所以得名comb sort。
/*
comb sort
*/
int comb_sort(vector<int>& vec)
{
int interval=10,i,j,k,len=vec.size(),cur_len;
while(interval>0)
{
for(i=0;i<interval;i++)
{
cur_len=(len/interval)+(i<len%interval?1:0);
for(j=1;j<cur_len;j++)
{
for(k=j;k>0;k--)
{
if(vec[i+interval*k]<vec[i+interval*(k-1)])
{
vec[i+interval*k]=vec[i+interval*k]^vec[i+interval*(k-1)];
vec[i+interval*(k-1)]=vec[i+interval*k]^vec[i+interval*(k-1)];
vec[i+interval*k]=vec[i+interval*k]^vec[i+interval*(k-1)];
}
}
}
}
interval=interval/1.3;
}
return 0;
}
奇偶排序（odd_even sort）
這個(gè)算法將元素按照下標(biāo)的奇偶分為兩組卫病，首先在第一組進(jìn)行相鄰兩個(gè)元素的比較油啤，然后在第二組進(jìn)行相鄰兩個(gè)元素比較（相鄰的定義要一致，可以都用后一個(gè)相鄰蟀苛，也可以都用前一個(gè)鄉(xiāng)鄰益咬，絕對不能一個(gè)前一個(gè)后），如此循環(huán)屹逛。直到某一次進(jìn)行完檢查后础废，第一組和第二組都沒有改動(dòng)汛骂，這時(shí)候就說明元素已經(jīng)有序了。
這個(gè)算法一看就知道只是花拳繡腿评腺，改變一下冒泡排序的順序而已帘瞭，性能沒有任何變化。
/*
odd_even sort
*/
int odd_even_sort(vector<int>& vec)
{
int odd_len,even_len,len,j,flag=1;
len=vec.size();
odd_len=len/2+(len%2==0?(-1):0);
even_len=len/2+(len%2==0?0:0);
while(flag==1)
{
flag=0;
for(j=0;j<even_len;j++)
{
if(vec[2*j]<vec[2*j+1])
{
vec[2*j]=vec[2*j]^vec[2*j+1];
vec[2*j+1]=vec[2*j]^vec[2*j+1];
vec[2*j]=vec[2*j]^vec[2*j+1];
flag=1;
}
}
for(j=0;j<odd_len;j++)
{
if(vec[2*j+1]<vec[2*j+2])
{
vec[2*j+2]=vec[2*j+2]^vec[2*j+1];
vec[2*j+1]=vec[2*j+2]^vec[2*j+1];
vec[2*j+2]=vec[2*j+2]^vec[2*j+1];
flag=1;
}
}
}
return 0;
}
圖書館排序（library sort）
這個(gè)算法是二十一世紀(jì)才提出的蒿讥，由此便看出計(jì)算機(jī)科學(xué)的活力蝶念，在數(shù)學(xué)上，那些讓你覺得深不可測的東西芋绸，你一看年代媒殉，往往在幾百年前就被大師上課的時(shí)候在草稿紙上解決了，等你學(xué)到21世紀(jì)的數(shù)學(xué)摔敛，你就是大師了廷蓉。
這個(gè)算法靈感源于在圖書館放書的時(shí)候在書之間留下空隙，當(dāng)你需要插入一本書的時(shí)候就不必移動(dòng)整個(gè)架子的書马昙。
所以我們在數(shù)組元素間留一些空隙桃犬，插入的時(shí)候就能夠減少對其他元素的移動(dòng)。
/*
library sort
*/
int library_sort(vector<int>& vec)
{
const int empty_flag = -1000;
vector<int> temp;
temp.resize(vec.size()*2,empty_flag);
int i, j, k,l, indicator;
for (i=0;i<vec.size();i++)
{
for (j=2*i;j>=-1;j--)
{
if ( j == -1||(temp[j] >= vec[i]&&temp[j]!= empty_flag))
{
indicator = 0;
for(l=2*i;l>j;l--)
{
if (temp[l] != empty_flag)
{
indicator = 1; break;
}
}
if (indicator == 1)
{
if (temp[j + 1] != empty_flag)
{
k = j + 1;
while (temp[k] != empty_flag)
{
k++;
}
for (; k > j + 1; k--)
{
temp[k] = temp[k - 1];
}
temp[k] = vec[i];
}
else
{
temp[j + 1] = vec[i];
}
}
else
{
temp[i * 2] = vec[i];
}
break;
}
}
}
vec.resize(0);
for (i = 0; i < temp.size(); i++)
{
if (temp[i] != empty_flag)
{
vec.push_back(temp[i]);
}
}
return 0;
}
bogo sort
這個(gè)算法也沒有中文翻譯行楞，不過我把它作為壓軸算法攒暇，它必然有過人之處，它的過人之處就是子房，超級(jí)慢形用。
這個(gè)算法思想類似于把一副牌扔向空中，掉到地上后去看看它是不是有序的证杭，如果不是田度，再扔一次。
它的復(fù)雜度是O（n!）,這個(gè)東西和n^n是同階的躯砰∶勘遥可見其相當(dāng)恐怖。
數(shù)學(xué)說起來太抽象琢歇，假設(shè)排十個(gè)數(shù)需要時(shí)間t，那么排20個(gè)就需要220*1010*t梦鉴，也就是大約2*10^16*t李茫，我實(shí)測了一下，半分鐘才能排11個(gè)數(shù)字肥橙。
這個(gè)算法存在的意義估計(jì)是挑戰(zhàn)運(yùn)算的極限吧魄宏，等有朝一日，這個(gè)算法能用于生產(chǎn)生活存筏，人類文明估計(jì)就會(huì)進(jìn)入新紀(jì)元了宠互。
/*
bogo sort
*/
int bogo_sort(vector<int>& vec)
{
int randa=1, randb=2,count=0,i,flag=1;
while (true)
{
while (true)
{
randa = (time(NULL)+rand())%vec.size();
randb = (time(NULL)+rand())% vec.size();
if (randb != randa)break;
}
vec[randa] = vec[randa] ^ vec[randb];
vec[randb] = vec[randa] ^ vec[randb];
vec[randa] = vec[randa] ^ vec[randb];
count++;
if (count >= 1)
{
count = 0;
flag = 0;
for ( i = 0; i < vec.size()-1; i++)
{
if (vec[i] < vec[i + 1])
{
flag = 1;
break;
}
}
}
if (flag == 0)break;
}
return 0;
}
