有一本像小說(shuō)一樣有趣的算法入門(mén)書(shū)裸违，我不會(huì)告訴你，它的封面是下面那樣本昏。
一.二分查找
? ? ? ? 在大學(xué)畢業(yè)之際供汛，室友聚餐，在等菜的時(shí)候，為了打發(fā)無(wú)聊的時(shí)間怔昨，大家又不想各看手機(jī)雀久，最后決定玩猜數(shù)字游戲。每個(gè)人輪流各出一個(gè)數(shù)字趁舀，然后大家猜赖捌，在一百以內(nèi)，
? ? ? ? 大家沒(méi)有從1開(kāi)始去一個(gè)一個(gè)往上猜(不過(guò)這樣的確可以打發(fā)時(shí)間)矮烹，大家都是從中間50開(kāi)始猜的越庇。
? ? ? 不管是小了還是大了，首先會(huì)排除一半的數(shù)字奉狈，假設(shè)猜小了卤唉，那下一個(gè)人就會(huì)猜50到100中間的數(shù)字75，
大了仁期，那又排除了一半的數(shù)字桑驱，接下來(lái)的人就去猜50到75之間的數(shù)字63。
是的蟀拷，沒(méi)錯(cuò)碰纬，這就是二分查找，每次猜測(cè)排除的數(shù)字個(gè)數(shù)如下问芬，
不管這個(gè)數(shù)字是多少悦析，輪流到第7個(gè)人的時(shí)候一定會(huì)猜到。
? ? ? ? 一般而言，對(duì)于包含n個(gè)元素的列表鸯旁，用二分查找最多需要log2n(這里的2是底)步肩钠，而簡(jiǎn)單查找(前面所說(shuō)的從1開(kāi)始一個(gè)一個(gè)猜的情況)最多需要n步。
下面看看用python寫(xiě)的完整代碼(書(shū)中的)：
我用c語(yǔ)言給大家也給出了一個(gè)接口：
int SearchFun(int a[], int n, int x)
{
int mid,low,high;
low=0;
high=n-1;
while(low <= high)
{
mid=(low+high)/2;
if(a[mid] ==x)
? ? ? return mid;
else if(a[mid] >x)
? ? high = mid-1;
else
? ? low = mid+1;
}
return -1;
}
運(yùn)行時(shí)間
? ? ? 每次介紹算法時(shí)骑歹，我都將討論其運(yùn)行時(shí)間。一般而言墨微，應(yīng)選擇效率最高的算法道媚，以最大限度地減少運(yùn)行時(shí)間或占用空間。
? ? ? ? 回到前面的二分查找翘县。使用它可節(jié)省多少時(shí)間呢最域？簡(jiǎn)單查找逐個(gè)地檢查數(shù)字，如果列表包含100個(gè)數(shù)字锈麸，最多需要猜100次镀脂。如果列表包含40億個(gè)數(shù)字，最多需要猜40億次忘伞。換言之薄翅，最多需要猜測(cè)的次數(shù)與列表長(zhǎng)度相同沙兰，這被稱為線性時(shí)間（linear time）。
? ? ? ? 二分查找則不同翘魄。如果列表包含100個(gè)元素鼎天，最多要猜7次；如果列表包含40億個(gè)數(shù)字熟丸，最多需猜32次训措。厲害吧？二分查找的運(yùn)行時(shí)間為對(duì)數(shù)時(shí)間（或log時(shí)間）光羞。下表總結(jié)了我們發(fā)現(xiàn)的情況绩鸣。
常見(jiàn)的大O運(yùn)行時(shí)間
下面按從快到慢的順序列出了你經(jīng)常會(huì)遇到的5種大O運(yùn)行時(shí)間。
? O(log n)纱兑，也叫對(duì)數(shù)時(shí)間呀闻，這樣的算法包括二分查找。
? O(n)潜慎，也叫線性時(shí)間捡多，這樣的算法包括簡(jiǎn)單查找。
? O(n ＊ log n)铐炫，這樣的算法包括第4章將介紹的快速排序——一種速度較快的排序算法垒手。
? O(n2)，這樣的算法包括第2章將介紹的選擇排序——一種速度較慢的排序算法倒信。
? O(n! )科贬，這樣的算法包括接下來(lái)將介紹的旅行商問(wèn)題的解決方案——一種非常慢的算法。
二鳖悠、排序算法
二分查找法的前提是榜掌，查找的這一系列數(shù)字串必須是有序的。
在學(xué)習(xí)查找算法前我們簡(jiǎn)單的了解一下數(shù)組和鏈表乘综。
數(shù)組鏈表
假設(shè)你要編寫(xiě)一個(gè)
管理待辦事項(xiàng)的應(yīng)用程序憎账，為此你需要將這些待辦事項(xiàng)儲(chǔ)存在內(nèi)存中，是使用數(shù)組還是鏈表呢卡辰？
我們先說(shuō)使用數(shù)組吧胞皱，使用數(shù)組意味著所有待辦事項(xiàng)在內(nèi)存中都是相連的（緊靠在一起的）。
如果你要添加第四個(gè)待辦事項(xiàng)九妈，但是第四個(gè)被別人給占了
就相當(dāng)于你和朋友一起去看電影朴恳，你們先左下，如果再來(lái)一個(gè)朋友允蚣，發(fā)現(xiàn)坐的地方?jīng)]有空位置了，但你們必須要坐到一起呆贿，因此你們都要起來(lái)去找一個(gè)可以左下你們且椅子連著的位置嚷兔。一個(gè)解決的辦法是"預(yù)留座位"森渐，即使只有三個(gè)人，但預(yù)留十個(gè)座位冒晰，這樣一來(lái)同衣，如果后面還有人來(lái)就不用再去占位置了，就相當(dāng)于在圖書(shū)館里占座位壶运，不過(guò)這樣一來(lái)有兩個(gè)缺點(diǎn)
1.浪費(fèi)內(nèi)存
2.如果超過(guò)了10個(gè)還得移位子
鏈表
鏈表中的元素可存儲(chǔ)在內(nèi)存的任何地方耐齐。
鏈表的每個(gè)元素都存儲(chǔ)了下一個(gè)元素的地址，從而使一系列隨機(jī)的內(nèi)存地址串在一起蒋情。
使用鏈表試埠况，根本不需要移動(dòng)元素。假設(shè)你與五位朋友去看一部很火的電影棵癣。你們六人想坐在一起辕翰，但看電影的人較多，沒(méi)有六個(gè)在一起的座位狈谊。這個(gè)時(shí)候不需要坐在一起喜命，鏈表相當(dāng)于來(lái)說(shuō)，"我們分開(kāi)坐"河劝，這也就是鏈表的優(yōu)勢(shì)——插入壁榕。
數(shù)組
鏈表在讀取最后一個(gè)元素的時(shí)候，你不能直接去讀取赎瞎，因?yàn)槟悴恢浪幍牡刂放评铮仨氁粋€(gè)一個(gè)訪問(wèn)，直到訪問(wèn)最后一個(gè)元素煎娇。需要同時(shí)讀取所有元素時(shí)二庵，鏈表的效率很高：你讀取第一個(gè)元素，根據(jù)其中的地址再讀取第二個(gè)元素缓呛，以此類推催享。但如果你需要跳躍，鏈表的效率真的很低哟绊。
數(shù)組與此不同:你知道其中每個(gè)元素的地址因妙。例如，假設(shè)有一個(gè)數(shù)組票髓，它包含五個(gè)元素攀涵，起始地址為00，那么元素#5的地址是多少呢洽沟？
只需執(zhí)行簡(jiǎn)單的數(shù)學(xué)運(yùn)算就知道：04以故。需要隨機(jī)地讀取元素時(shí)，數(shù)組的效率很高裆操，因?yàn)榭裳杆僬业綌?shù)組的任何元素怒详。
總結(jié)
鏈表的優(yōu)勢(shì)：插入炉媒、刪除
數(shù)組的優(yōu)勢(shì)：讀取
下面是常見(jiàn)數(shù)組和鏈表操作的運(yùn)行時(shí)間。
選擇排序
看看書(shū)中的講解昆烁。
你的計(jì)算機(jī)中儲(chǔ)存了很多歌曲
你要將這個(gè)列表按照從多到少的順序排序吊骤，一種辦法是我們遍歷整個(gè)數(shù)組，找到聽(tīng)的次數(shù)最多的那首歌曲放到一個(gè)新列表中
再次這樣做静尼，找到第二多
繼續(xù)這樣做白粉，你將得到一個(gè)這樣的列表
以上的排序方法就是選擇排序，選擇排序是一種靈巧的算法鼠渺，但其速度不是很快鸭巴。
python代碼
我在此給出了c語(yǔ)言接口：
void SelectionSort(int *a,int len)
{
int i,j,k;
int temp;
for(i=0;i < len-1;i++)
{
? ? ? k=i;
? ? ? for(j=i+1;j<len;j++)
? ? ? {
? ? ? ? ? ? if(a[j] < a[k])
? ? ? ? ? ? ? ? ? ? k=j;
? ? ? }
? ? ? if(k!=i)
? ? {
? ? ? ? ? ? temp=a[i];
? ? ? ? ? ? a[i]=a[k];
? ? ? ? ? ? a[k]=temp;
? ? ? }
}
}
注:文章中的圖片均是來(lái)自本書(shū)。
