導(dǎo)
算法是很重要的，之前在看《算法導(dǎo)論》的時(shí)候捻脖，基本上是不知所錯(cuò)。后來(lái)買了《啊哈中鼠，算法》可婶。補(bǔ)補(bǔ)簡(jiǎn)單的算法知識(shí)。
在這本書學(xué)習(xí)完成之后援雇，想再去看《算法導(dǎo)論》可能會(huì)好一些矛渴。如果大家還有好的書推薦，請(qǐng)留言惫搏。十分感謝具温。
之前粗略的看過(guò)一遍，但是老話說(shuō)的好：好記性筐赔，不如爛筆頭铣猩。還是記下來(lái)，熟悉一遍茴丰。印象深刻达皿。
這本書，作者很是用心贿肩，用了很多巧妙的比喻峦椰，而且配圖也很好玩，很好理解汰规。
這一章作者主要講了三個(gè)算法：桶排序汤功，冒泡排序，快速排序溜哮。
桶排序：
現(xiàn)在有一個(gè)數(shù)組a[5] = {6,4,6,3,8},5個(gè)元素不大于10滔金。0~10是11個(gè)數(shù)，那么我們就拿11一個(gè)洗腳桶茂嗓，分別是0號(hào)到10號(hào)鹦蠕，桶里面什么都沒(méi)有。找來(lái)5根筷子在抛，筷子分別標(biāo)注a數(shù)組中的數(shù)字大小钟病。然后按照筷子上的數(shù)字找到相同數(shù)字的桶的編號(hào)，放進(jìn)去。之后肠阱，我們從0號(hào)桶順序的取里面的筷子票唆，進(jìn)行一一排列，這樣就排序完了屹徘，那肯定是3走趋，4，6噪伊，6簿煌，8了，如果從大到小就從10號(hào)桶到0號(hào)桶挨個(gè)取鉴吹，那就是8姨伟，6，6豆励，4夺荒，3了。
如果你要嘗試n個(gè)0到10的良蒸，從大到小或者從小到大排序呢技扼。趕緊寫個(gè)程序理解下。
// 定義一個(gè)數(shù)組（11個(gè)桶）
int a[11];
// 循環(huán)賦值都為0嫩痰，其實(shí)是桶里面什么都沒(méi)有
for (int z = 0; z < 11; z++)
{
a[z] = 0;
}
// 定義你要比較的元素?cái)?shù)組剿吻，數(shù)組元素值是0~10
// 這個(gè)數(shù)組里面的值，比如數(shù)組中的`7`,其實(shí)是對(duì)應(yīng)桶數(shù)組中的下標(biāo)
int b[5] = {7,3,5,1,6};
// 定義筷子t串纺，筷子一直加1和橙，表示有幾個(gè)相同的值
int t;
// 循環(huán)比較的元素?cái)?shù)組
for (int z = 0; z < 5; z++)
{
// 對(duì)t進(jìn)行賦值，列如：b[0]是7造垛，那么t=7
t = b[z];
// 也就是a[7]原本是0魔招，現(xiàn)在++，若有3個(gè)t=7五辽，那么a[7]的值就是3了
// 如果你還想去重办斑，那直接a[t] = 1；就可以了杆逗。
a[t]++;
}
// 進(jìn)行雙循環(huán)取值
// 下面是重小到大排序（for (int z = 10; z >= 0; z--) {} 從大到小排序）
for (int z = 0; z < 11; z++)
{
// 相對(duì)應(yīng)的桶里面有幾個(gè)值
for (int j = 0; j < a[z]; j++)
{
// 打印值
printf("%d\t",z);
}
}
打印的值如下：
1 3 5 6 7
啵~
冒泡排序：
冒泡排序的基本思想是：每次比較兩個(gè)相鄰的元素乡翅，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)！
基本上我們?cè)趯W(xué)習(xí)任何語(yǔ)言的時(shí)候都會(huì)學(xué)冒泡排序罪郊，直接上代碼蠕蚜。
// 要進(jìn)行排序的源數(shù)組
int a[12] = {89,99,23,44,21,43,55,21,1,56,77,98};
// 中間的接受者
int t;
// 冒泡排序的核心代碼
for (int z = 0; z < 12 - 1; z++)
{
for (int p = 0; p < 12 - 1; p++)
{
// 進(jìn)行比較(從打到小排序)
if (a[p] < a[p + 1])
{
// 進(jìn)行交換
t = a[p];
a[p] = a[p + 1];
a[p + 1] = t;
}
}
}
for (int z = 0; z < 12; z++)
{
printf("%d \t",a[z]);
}
打印的值如下：
99 98 89 77 56 55 44 43 23 21 21 1
快速排序
為什么用
快速排序，作者說(shuō)：桶排序其實(shí)浪費(fèi)了很多的空間悔橄，而冒泡排序可以解決桶排序的浪費(fèi)空間的問(wèn)題靶累，但是冒泡排序存在在運(yùn)行比較很多值排序腺毫，則會(huì)花費(fèi)比桶排序多的多的時(shí)間。
快速排序：設(shè)置基準(zhǔn)數(shù)挣柬，進(jìn)行
遞歸式快速歸位潮酒。
強(qiáng)行理解一波：按照作者的理解我做了一個(gè)高低的圖，幫助我理解邪蛔。順序看圖急黎。
以最開始的<6>作為基準(zhǔn)數(shù)，從左邊開始找到一個(gè)大的侧到，從右邊開始找到一個(gè)小的勃教，進(jìn)行交換。
上面第一次交換完畢匠抗。
進(jìn)行下一次交換故源。
最終<6>和<3>進(jìn)行交換闺魏。
下面的圖，我們看到
6左邊的都小于等于6奉呛，6最右邊的都大于等于6如绸。
然后我們
6左邊的再次用上面同樣的方法進(jìn)行，以3為基準(zhǔn)交換位置狭园，右邊的以9也進(jìn)行交換位置。這樣來(lái)回交換。我們就完成了排序了踏堡。
作者畫了一個(gè)很長(zhǎng)的圖，建議大家可以買書咒劲，看看顷蟆，很好理解。這里只是做筆記腐魂，進(jìn)行自我理解帐偎。
就像作者所說(shuō)我們寫個(gè)程序來(lái)理解一下更好。
// 初始化內(nèi)容
self.numberArray = [[NSMutableArray alloc] init];
for (int z = 0; z < 100; z++)
{
// 100個(gè)100以內(nèi)
int number = arc4random()%100;
[self.numberArray addObject:[NSNumber numberWithInt:number]];
}
// 輸出未排序的數(shù)組
for (NSNumber * number in self.numberArray)
{
printf("%d \t",number.intValue);
}
// 左邊下表從0開始蛔屹，右邊99開始
[self quickSortWithLeftNumber:0 rightNumber:99];
NSLog(@"%@",self.numberArray);
// 輸出結(jié)果
for (NSNumber * number in self.numberArray)
{
printf("%d \t",number.intValue);
}
/**
快速排序
*/
- (void)quickSortWithLeftNumber:(int)leftNumber rightNumber:(int)rightNumber
{
if (leftNumber > rightNumber)
{
return;
}
int left_i;
int right_j;
int temp;
int t;
// 基準(zhǔn)出
temp = self.numberArray[leftNumber].intValue;
left_i = leftNumber;
right_j = rightNumber;
while (left_i != right_j)
{
// 找右邊
while (self.numberArray[right_j].intValue >= temp && left_i < right_j)
{
right_j--;
}
// 找左邊
while (self.numberArray[left_i].intValue <= temp && left_i < right_j)
{
left_i++;
}
// 如果達(dá)成削樊，則進(jìn)行數(shù)組位置交換
if (left_i < right_j)
{
t = self.numberArray[left_i].intValue;
self.numberArray[left_i] = self.numberArray[right_j];
self.numberArray[right_j] = [NSNumber numberWithInt:t];
}
}
// 進(jìn)行基準(zhǔn)歸位
self.numberArray[leftNumber] = self.numberArray[left_i];
self.numberArray[left_i] = [NSNumber numberWithInt:temp];
// 如圖，繼續(xù)處理左邊的兔毒，進(jìn)行遞歸
[self quickSortWithLeftNumber:leftNumber rightNumber:left_i-1];
// 如圖漫贞，繼續(xù)處理右邊的，進(jìn)行遞歸
[self quickSortWithLeftNumber:left_i+1 rightNumber:rightNumber];
}
輸出未排序的數(shù)組
89 67 10 77 10 55 10 96 9 85 45 45 6 54 31 12 15 67 27 60 38 68 36 3 69 63 26 28 32 7 23 40 50 47 62 55 43 65 33 99 84 24 54 84 79 93 23 30 57 77 62 21 99 14 99 61 93 98 70 73 95 62 47 50 94 42 91 74 49 53 38 73 9 14 50 95 23 95 26 80 84 71 36 1 4 20 41 27 75 45 77 3 99 10 43 93 28 2 15 94
輸出排序的結(jié)果：
1 2 3 3 4 6 7 9 9 10 10 10 10 12 14 14 15 15 20 21 23 23 23 24 26 26 27 27 28 28 30 31 32 33 36 36 38 38 40 41 42 43 43 45 45 45 47 47 49 50 50 50 53 54 54 55 55 57 60 61 62 62 62 63 65 67 67 68 69 70 71 73 73 74 75 77 77 77 79 80 84 84 84 85 89 91 93 93 93 94 94 95 95 95 96 98 99 99 99 99
