這個(gè)我也不知道能寫(xiě)多少瘫拣，只是最近快放假了實(shí)在懶得看DSP了,而且卡在一個(gè)地方了陕赃，什么都不干又感覺(jué)心慌的很省艳，所以又回頭看看算法的東西亲茅。一些測(cè)試程序放在這里
1.排序
正好看到分治法關(guān)于歸并排序的這塊回铛，所以想把排序做一個(gè)總結(jié)。主要包括冒泡克锣，計(jì)數(shù)茵肃，插入，選擇袭祟，歸并排序验残，堆排序和插入排序。寫(xiě)的時(shí)候可能沒(méi)有什么順序榕酒。
排序算法是最常用的一種算法胚膊，給定一個(gè)數(shù)組，把這個(gè)數(shù)組排序是最基本的需求想鹰，所以排序算法有很多種紊婉，性能也不移，比較快的堆排序辑舷，歸并排序和快速排序喻犁，其他的都很慢。下面這個(gè)表可以看一下：
| 排序算法 | 最壞情況下的性能 | 平均性能 |
|---|---|---|
| 冒泡排序 | n^2 | n^2 |
| 計(jì)數(shù)排序 | n^2 | n^2 |
| 插入排序 | n^2 | n^2 |
| 選擇排序 | n^2 | n^2 |
| 堆排序 | nlog(n) | nlog(n) |
| 歸并排序 | nlog(n) | nlog(n) |
| 快速排序 | n^2 | nlog(n) |
這個(gè)是在《數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用-c++描述》的書(shū)上的p462何缓，sartaj sahni著肢础。
1.1 歸并排序
因?yàn)檫@次我先看的歸并排序，就來(lái)先寫(xiě)這個(gè)了碌廓，歸并排序是分治法的一個(gè)典型應(yīng)用传轰，其主要思想是把數(shù)據(jù)分組排序，然后兩兩一組進(jìn)行歸并（歸并的同時(shí)對(duì)這兩組進(jìn)行排序）谷婆，直到合并成一個(gè)大的數(shù)組慨蛙。
這個(gè)是遞歸的實(shí)現(xiàn)辽聊，思路就是分解成單個(gè)元素，然后兩兩歸并期贫，無(wú)法分組的直接復(fù)制下來(lái)跟匆，直到歸并成一個(gè)數(shù)組，這個(gè)時(shí)候就是一個(gè)排好序的數(shù)組了通砍。
為了程序下標(biāo)簡(jiǎn)單玛臂，我們數(shù)組下標(biāo)從1開(kāi)始，也就是說(shuō)0位置空下來(lái)封孙，不把數(shù)據(jù)放進(jìn)去
先來(lái)寫(xiě)一個(gè)歸并函數(shù)迹冤，就是把兩個(gè)排序數(shù)組合并成一個(gè)排序數(shù)組，這個(gè)是在歸并排序中要經(jīng)常用到的：
l是表示第一個(gè)數(shù)組的下標(biāo)起點(diǎn)敛瓷，m表示第一個(gè)數(shù)組的最后一個(gè)數(shù)據(jù)下標(biāo)叁巨，n表示第二個(gè)數(shù)組的最后一個(gè)下標(biāo)。如圖呐籽，要合并的是綠色和棕色的數(shù)組锋勺。
void Merge(T *initList, T *mergeList, const int l, const int m, const int n)
{
//這個(gè)是歸并兩個(gè)排序數(shù)組，雙指針歸并
int i1, i2; //雙指針
int index = l; //這個(gè)是新數(shù)組的序號(hào)
for (i1 = l, i2 = m + 1; i1 <= m&&i2 <=n; index++)
{
if (initList[i1] < initList[i2])
{
mergeList[index] = initList[i1];
i1++;
}
else
{
mergeList[index] = initList[i2];
i2++;
}
}
//這兩個(gè)copy最多只有一個(gè)起作用
copy(initList + i1, initList + m + 1, mergeList + index);
copy(initList + i2, initList + n + 1, mergeList + index);
}
整體也比較簡(jiǎn)單狡蝶，是一個(gè)雙指針合并數(shù)組的標(biāo)準(zhǔn)寫(xiě)法庶橱，最后用copy把沒(méi)有遍歷的copy過(guò)來(lái)就可以了。
上面這個(gè)只能實(shí)現(xiàn)對(duì)一對(duì)組合的歸并贪惹，我們?cè)谶M(jìn)行歸并的時(shí)候可能要對(duì)多組數(shù)據(jù)（這些還是存放在一個(gè)大的數(shù)組里的）進(jìn)行歸并苏章，所以我們還需要寫(xiě)另外一個(gè)函數(shù)進(jìn)行這樣的歸并。
template<class T>
void MergePass(T *initlist, T *result, int n, int s) //n是數(shù)據(jù)個(gè)數(shù)奏瞬，s是每段個(gè)數(shù)
{
int i;
for (i = 1; i <=n-2*s+1; i += 2 * s) //這里一定是n-2*s+1枫绅，每?jī)蓚€(gè)一對(duì)，不成對(duì)的話就不能遍歷了硼端。
{
Merge(initlist, result, i, i + s - 1,i+2*s-1);
}
if ((i + s - 1) < n) //這是最后一次merge才會(huì)進(jìn)入這個(gè)循環(huán)并淋，也就是i=1下來(lái)的
{
Merge(initlist, result, i, i + s - 1, n);
}
else
copy(initlist + i, initlist + n + 1, result + i);
}
n是總數(shù)據(jù)的個(gè)數(shù)，s是每一段數(shù)據(jù)的個(gè)數(shù)珍昨，所以里面的for循環(huán)是一組一組進(jìn)行歸并县耽，i每次增加2s,因?yàn)槭莾蓛蓺w并，i的循環(huán)條件是<=n-2s+1這個(gè)保證i如果等于n-2s+1的時(shí)候后面還有2s個(gè)數(shù)據(jù)可以歸并镣典。
下面判斷i+s-1和n的大小兔毙，如果進(jìn)行了遍歷，i+s-1是第一組數(shù)據(jù)最后的一個(gè)數(shù)兄春，如果這個(gè)數(shù)小于n的話澎剥，說(shuō)明已經(jīng)進(jìn)行到最后一次歸并了，直接對(duì)大數(shù)組進(jìn)行兩段歸并就可以了赶舆，這個(gè)時(shí)候i是等于1的（也就是說(shuō)并沒(méi)有進(jìn)行上面的for循環(huán)肴裙，n-2s+1已經(jīng)小于1了趾唱，無(wú)法分成兩組等量的來(lái)進(jìn)行歸并）。
如果已經(jīng)進(jìn)行了歸并蜻懦，就只把后面的沒(méi)有分組的復(fù)制下來(lái)就好了，注意復(fù)制的時(shí)候是左閉右開(kāi)區(qū)間夕晓。
最后就是匯總的程序了宛乃，首先是以1為長(zhǎng)度歸并，然后是2蒸辆，再是4征炼，以此類推。
template<class T>
void MergeSort(T *initlist, int n)
{
T *tempList = new T[n + 1];
for (int l = 1; l < n; l *= 2)
{
MergePass(initlist, tempList, n, l);
/*copy(tempList, tempList + n + 1, initlist); */ //每次都拷貝一遍躬贡，可以重復(fù)利用
//一種更好的寫(xiě)法是下面這個(gè)谆奥，歸并一次變換到原來(lái)的數(shù)組，而不是簡(jiǎn)單的拷貝拂玻，效率要高一些
l *= 2;
MergePass(tempList, initlist, n, l);
}
delete[] tempList;
}
因?yàn)椴皇窃粴w并酸些，所以需要借助輔助的一個(gè)數(shù)組，可以每次歸并完把數(shù)據(jù)拷貝回去檐蚜，一種更好的方式是一次循環(huán)里做兩次歸并魄懂。不用擔(dān)心萬(wàn)一只需要做奇數(shù)次歸并怎么辦，如果如此闯第，最后一次歸并實(shí)際上是做了一次復(fù)制市栗。
歸并排序就到這里了。
1.2冒泡排序
這個(gè)大概是本科上c++的課程的時(shí)候?qū)W的第一個(gè)算法咳短，算法很簡(jiǎn)單填帽，每次循環(huán)把最大的一個(gè)數(shù)放到最后面，就相當(dāng)于冒泡一樣咙好，這樣循環(huán)n次就可以對(duì)一組數(shù)進(jìn)行排序：
這里有一個(gè)動(dòng)圖可以看一看篡腌。
int main(void) {
int a[]={7,4,9,3,1},temp;
for(int i=0;i<5;i++)
for(int j=i;j<5;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
for(int i=0;i<5;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
我從維基上直接復(fù)制過(guò)來(lái)的代碼，很簡(jiǎn)單敷扫，不用多說(shuō)哀蘑。
1.3插入排序
插入排序也是比較簡(jiǎn)單的，每次拿出一個(gè)數(shù)葵第，插入到已經(jīng)排序好的數(shù)組中绘迁，插入的過(guò)程是一個(gè)找位置的過(guò)程，具體的過(guò)程看這個(gè)動(dòng)圖卒密，我們認(rèn)為數(shù)組的第一個(gè)數(shù)是已經(jīng)排好序的缀台，然后從第二個(gè)數(shù)開(kāi)始驗(yàn)證，為這個(gè)數(shù)找一個(gè)位置哮奇。舉個(gè)簡(jiǎn)單的例子膛腐。
a=[1,3,5,2,1];
對(duì)于這個(gè)數(shù)組睛约，我們現(xiàn)在遍歷到a[3]這個(gè)位置。
先用tmp=a[3]把a(bǔ)[3]存儲(chǔ)起來(lái)哲身，然后tmp依次和a[2],a[1],a[0]辩涝，比較，如果tmp<a[2],則把a(bǔ)[2]后移（a[3]=a[2]）勘天。這個(gè)時(shí)候數(shù)組變成:
a=[1,3,5,5,1];
然后tmp再和a[1]比較,tmp依然小于a[1],則把a(bǔ)[1]后移怔揩，則變?yōu)椋?br> a=[1,3,3,5,1];
然后tmp和a[0]比較，tmp>=a[0],說(shuō)明這個(gè)位置就是要找的脯丝，則把a(bǔ)[1]這個(gè)位置賦值為tmp商膊，則變?yōu)椋?br> a=[1,2,3,5,1];
這樣一次遍歷就結(jié)束了，其他的都是這樣的宠进，注意寫(xiě)對(duì)遍歷的序號(hào)和邊界條件就行了晕拆。
template<class T>
void InsertSort(T *a, int n)
{
int i, j;
for (j = 1; j < n; j++)
{
int tmp = a[j];
cout << "tmp:" << tmp << endl; //test
i = j-1; //已排序的
while (i >= 0)
{
if (tmp < a[i])
{
a[i + 1] = a[i]; //后移
i--;
}
else
{
a[i+1] = tmp; //找到位置，賦值
break;
}
}
}
}
二分查找及其變種
-
基本二分查找
參考：你真的會(huì)寫(xiě)二分查找么
二分查找是一種“猜價(jià)格”的最好策略材蹬，也很好理解实幕，每一次查找，都把范圍縮小一半赚导，直到找到要查找的元素為止茬缩，是一種非常高效的查找方式，條件是查找的目標(biāo)必須是排序的吼旧。
基本的二分查找比較簡(jiǎn)單：
int Binary_Search1(vector<int> &v, int key)
{
int res=-1;
int left = 0;
int right = v.size() - 1;
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (key > v[mid])
left = mid + 1;
else if (key < v[mid])
right = mid - 1;
else
{
return mid; //找到的話返回下標(biāo)
}
}
return -1; //表示沒(méi)有找到
}
兩點(diǎn)注意：
①終止條件是<=凰锡，如果不加等于，有些數(shù)據(jù)遍歷不到圈暗，比如當(dāng)數(shù)據(jù)是第一個(gè)數(shù)時(shí)掂为。{1,2,3}查找1的話就會(huì)查找不到。
②left和right的更新是mid+1或者mid-1员串，這是因?yàn)閙id已經(jīng)查找過(guò)勇哗，而且不這樣做的話容易引起死循環(huán)。比如當(dāng)left=right時(shí)寸齐，mid等于left欲诺，這時(shí)候無(wú)論key的值如何，都會(huì)進(jìn)入left=right的死循環(huán)渺鹦。
如果能夠保證key一定存在扰法，查找到就可以返回，這是二分查找最簡(jiǎn)單的一種寫(xiě)法毅厚。
-
二分查找的變形
另外塞颁，二分查找還存在著一些變形：
比如，當(dāng)存在多個(gè)值時(shí)，要求查找最后一個(gè)或者第一個(gè)祠锣，如何處理酷窥？
如果找到mid不結(jié)束循環(huán)，最終的left和right應(yīng)該是滿足這樣的關(guān)系：left+1=right
示意圖
那么伴网，可以找到
①最后一個(gè)小于key的元素蓬推，1，
②第一個(gè)大于等于key的元素澡腾，2拳氢，
③最后一個(gè)小于等于key的元素，2蛋铆，
④第一個(gè)大于key的元素，5放接，
另外刺啦，如果存在多個(gè)key時(shí)，稍加判斷纠脾，就可以找到
⑤ 第一個(gè)與key相等的元素
⑥最后一個(gè)與key相等的元素
首先來(lái)看①--④玛瘸，解決問(wèn)題的關(guān)鍵在于上面這一張圖，如果是左邊的話苟蹈，要求最后指向這么一種狀態(tài)糊渊，那么找到的時(shí)候就不能停止查找，而是要把right=mid-1慧脱，這樣可以讓mid繼續(xù)減少渺绒，最后達(dá)到左邊的圖的這一種狀態(tài)，這時(shí)候選擇返回left或者right就能達(dá)到不同的結(jié)果菱鸥。如果是右邊的話就剛好相反宗兼，我把代碼直接貼到下面:
int Binary_Search2(vector<int> &v, int key); //查找最后一個(gè)小于目標(biāo)的數(shù)
int Binary_Search3(vector<int> &v, int key); //查找第一個(gè)大于等于目標(biāo)的數(shù)
int Binary_Search4(vector<int> &v, int key); //第一個(gè)大于目標(biāo)的數(shù)
int Binary_Search5(vector<int> &v, int key); //最后一個(gè)小于等于目標(biāo)的數(shù)
int Binary_Search2(vector<int> &v, int key)
{
int left = 0;
int right = v.size() - 1;
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (key > v[mid])
left = mid + 1;
else if (key <=v[mid])
right = mid - 1;
}
return right;
}
int Binary_Search3(vector<int> &v, int key)
{
int left = 0;
int right = v.size() - 1;
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (key > v[mid])
left = mid + 1;
else if (key <= v[mid])
right = mid - 1;
}
return left;
}
int Binary_Search4(vector<int> &v, int key)
{
int left = 0;
int right = v.size() - 1;
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (key >= v[mid])
left = mid + 1;
else if (key < v[mid])
right = mid - 1;
}
return left;
}
int Binary_Search5(vector<int> &v, int key)
{
int left = 0;
int right = v.size() - 1;
int mid;
while (left <= right)
{
mid = (left + right) / 2;
if (key >= v[mid])
left = mid + 1;
else if (key < v[mid])
right = mid - 1;
}
return right;
}
⑤⑥的問(wèn)題其實(shí)就已經(jīng)在上面了包括了，如果存在多個(gè)key值氮采，第一個(gè)大于等于key值的元素就是第一個(gè)key值殷绍，最后一個(gè)小于等于key值得元素就是最后一個(gè)key值。
另外鹊漠，如果key值本身就不存在主到，我們想找一個(gè)可以插入key值得位置，那么我們既可以找最后一個(gè)小于等于key值的索引躯概，插到其后登钥，也可以找第一個(gè)大于key值得索引，插到它前面楞陷。
理解了這些再去看二分插入簡(jiǎn)直不要太簡(jiǎn)單怔鳖，看這個(gè)題：最長(zhǎng)上升子序列
未完待續(xù)
