前言##
還記得我們學(xué)習(xí)C語言的時(shí)候的常用的三大排序嗎？
選擇、冒泡、快速排序
當(dāng)時(shí)學(xué)習(xí)的時(shí)候感覺好無聊、聽著也沒有什么意思。雖然當(dāng)時(shí)就會(huì)使用，但是現(xiàn)在讓我直接寫出來我只能寫出大概的思路，但是寫代碼的人的都知道細(xì)節(jié)才是決定成敗的。所以我覺得有必要總結(jié)一下，因此就寫了一個(gè)白話文的demo，寫完之后我感覺算法還是很有趣的嘛。在次分享給大家，希望對大家有幫助。
那么要怎樣的demo才能讓大家都理解呢，想了想那就模仿一下美團(tuán)的價(jià)格排序啊、評分排序什么的（美團(tuán)不一定是用本文的排序，我只是借助這個(gè)demo詳解排序算法）
源碼下載地址高仿美團(tuán)排序算法
冒泡排序##
什么是冒泡，就是像湖面底部的氣泡一樣，砰砰上向上冒
冒泡排序原理解說######
舉個(gè)例子：冒泡排序可以這樣理解
假如小明班級幾名同學(xué)的身高分別是 1 4 8 2 5 7 ，上體育課時(shí)候同學(xué)們隨機(jī)站隊(duì) 1 4 8 2 5 7，體育老師很生氣，要求身高從高到低排列站隊(duì)形（實(shí)現(xiàn)從到小的排序）
首先從第一位開始，第一位同學(xué)和第二位同學(xué)比較，發(fā)現(xiàn)第一位同學(xué)比第二位同學(xué)低 (1 < 4) ,第一位和第二位，交換位置，交換后的結(jié)果是
4 1 8 2 5 7
然后第二位同學(xué)與第三位同學(xué)比較（注意：此時(shí)的第二位同學(xué)是之前的第一位同學(xué)，因?yàn)樯弦徊街薪粨Q了位置），發(fā)現(xiàn)第二位比第三位還是低（1< 8）所以右交換位置, 交換結(jié)果是
4 8 1 2 5 7
.........
第一輪過后的順序變?yōu)?br>
4 8 2 5 7 1
細(xì)心的同學(xué)可能發(fā)現(xiàn)了 ，第一輪其實(shí)是把身高最低的一位（1）同學(xué)歸位了
第二輪
第一位同學(xué)4和第二位同學(xué)8比較（4<8），第一位同學(xué)比第二位同學(xué)低，所以交換位置， 交換結(jié)果
8 4 2 5 7 1
然后第二位同學(xué)4和第三位同學(xué)2比較（4>2）,第二位同學(xué)比第三位同學(xué)高，不用交換位置
接著第三位和第四位比較...........
注意最后一位就不用比較了， 所以比較了多少次呢，自己想一想，動(dòng)動(dòng)腦
接著比較第三輪，第四輪.......
細(xì)心的朋友可能發(fā)現(xiàn)冒泡排序就是歸位的思想
下面直接上代碼 -
按照模型里面價(jià)格排序排序模型數(shù)組
//方法一:左邊歸位
for (NSInteger i = 0; i < self.foodModes.count ; i++)
{
for (NSInteger j = i; j < self.foodModes.count; j++)
{
LZBBaseModel *model_i = self.foodModes[i];
LZBBaseModel *model_j = self.foodModes[j];
if(model_i.price > model_j.price)
{
//交換
[self.foodModes replaceObjectAtIndex:i withObject:model_j];
[self.foodModes replaceObjectAtIndex:j withObject:model_i];
}
}
}
第二種方法，都是可用，只是想讓大家看看歸位的思想
//方法二：右邊歸位
for(NSInteger i = 0; i < self.foodModes.count;i++)
{
for(NSInteger j = 0; j < self.foodModes.count - i; j++)
{
if(j == self.foodModes.count -1) break;
LZBBaseModel *model_j = self.foodModes[j];
LZBBaseModel *model_j1 = self.foodModes[j+1];
if(model_j.price > model_j1.price)
{
[self.foodModes replaceObjectAtIndex:j withObject:model_j1];
[self.foodModes replaceObjectAtIndex:j+1 withObject:model_j];
}
}
}
冒泡排序分析：
時(shí)間復(fù)雜度：N *（N - i）約N * N
N是什么意思？： 數(shù)組的個(gè)數(shù)
快速排序####
由于冒泡排序的時(shí)間復(fù)雜度比較高，所以就想想還有沒有其他排序方式更快?？梢赃@么試著想一想，冒泡是歸位，并且是要么從左邊比較歸位，要么就是從右邊比較歸位，那么可不可以兩邊一起比較向中間靠攏呢，好，想到這個(gè)，那就距離快速排序不遠(yuǎn)了。
快速排序核心思想：歸位 + 二分法+ 遞歸
快速排序原理解說######
有一個(gè)隊(duì)列是 4 6 2 5 1 3 7 用快速排序排序 12345678
首先我們要知道我們要排列的順序是從小到大，意思就是小的在左邊，大的在右邊，
第一輪 ：第一個(gè)數(shù)為基準(zhǔn)數(shù) 4
那么A從左邊開始找大于 4 的數(shù)，找到之后停止， B從右邊開始找小于4的數(shù)，（B先開始找，因?yàn)榛鶞?zhǔn)數(shù)在左邊），這樣當(dāng)B找到3就停止、A找到6就停止，那么開始交換，交換后的結(jié)果4 3 2 5 1 6 7，這個(gè)時(shí)候第一輪還沒有結(jié)束，A和B繼續(xù)找，找到就繼續(xù)交換，當(dāng)某一刻事件A和B相遇的時(shí)候，那么就不用找了，直接把基準(zhǔn)數(shù)與相遇的值交換，第一輪結(jié)果
1 3 2 4 5 6 7
后面幾步這里我不做解說，大家要自己寫一下才能體會(huì)，要是全是文字，可能根本沒有耐心看完。其實(shí)第一輪把數(shù)列分成的2組,2組又分別進(jìn)行第一輪的操作，細(xì)心的同學(xué)可能發(fā)現(xiàn)，其實(shí)每一輪都會(huì)歸位一個(gè)數(shù)，所以我把這些排序就理解的歸位類的。
我覺得還是看代碼比較親切，上代碼
//快速排序- 星級評分
- (void)fastSortLeftIndex:(NSInteger)left WithRightIndex: (NSInteger)right
{
NSInteger i, j;
if(left > right) return;
LZBBaseModel *tempModel = self.foodModes[left]; //基準(zhǔn)模型
i = left;
j = right;
while (i != j) {
//從右邊開始找比基準(zhǔn)模型的評分小的模型
while (i<j && self.foodModes[j].evaluation>tempModel.evaluation) {
j--;
}
//從左向右找
while (i < j && self.foodModes[i].evaluation <= tempModel.evaluation) {
i++;
}
//如果左右都找到了就交換模型
if(i < j)
{
LZBBaseModel *model_i = self.foodModes[i];
LZBBaseModel *model_j = self.foodModes[j];
[self.foodModes replaceObjectAtIndex:i withObject:model_j];
[self.foodModes replaceObjectAtIndex:j withObject:model_i];
}
}
//如果相遇了
self.foodModes[left] = self.foodModes[i];
self.foodModes[i] = tempModel;
//第一輪結(jié)束之后，采用遞歸 - 二分法
[self fastSortLeftIndex:left WithRightIndex:i-1];
[self fastSortLeftIndex:i+1 WithRightIndex:right];
return;
//快速排序時(shí)間復(fù)雜度:N * logN - 所以我比較喜歡快速排序哦
}
快速排序的時(shí)間復(fù)雜度： N * logN 比冒泡排序爽
后期還會(huì)有算法大白話算法更新哦哦
最后贈(zèng)言###
如果覺得文章對您有幫助，不要忘記star哦!??，star 是對程序猿最大的鼓勵(lì)！
