iOS的冒泡排序和快速排序（高仿美团排序）

2017-05-07 本文已影响418人摸着石头过河_崖边树

前言##

还记得我们学习C语言的时候的常用的三大排序吗？
选择、冒泡、快速排序
当时学习的时候感觉好无聊、听着也没有什么意思。虽然当时就会使用，但是现在让我直接写出来我只能写出大概的思路，但是写代码的人的都知道细节才是决定成败的。所以我觉得有必要总结一下，因此就写了一个白话文的demo，写完之后我感觉算法还是很有趣的嘛。在次分享给大家，希望对大家有帮助。

那么要怎样的demo才能让大家都理解呢，想了想那就模仿一下美团的价格排序啊、评分排序什么的（美团不一定是用本文的排序，我只是借助这个demo详解排序算法）

Simulator Screen Shot 2016年4月27日下午12.57.26.png

源码下载地址高仿美团排序算法

冒泡排序##

什么是冒泡，就是像湖面底部的气泡一样，砰砰上向上冒

Snip20160428_5.png

冒泡排序原理解说######

举个例子：冒泡排序可以这样理解
假如小明班级几名同学的身高分别是 1 4 8 2 5 7 ，上体育课时候同学们随机站队 1 4 8 2 5 7，体育老师很生气，要求身高从高到低排列站队形（实现从到小的排序）
首先从第一位开始，第一位同学和第二位同学比较，发现第一位同学比第二位同学低 (1 < 4) ,第一位和第二位，交换位置，交换后的结果是
4 1 8 2 5 7
然后第二位同学与第三位同学比较（注意：此时的第二位同学是之前的第一位同学，因为上一步中交换了位置），发现第二位比第三位还是低（1< 8）所以右交换位置, 交换结果是
4 8 1 2 5 7
.........
第一轮过后的顺序变为
4 8 2 5 7 1
细心的同学可能发现了，第一轮其实是把身高最低的一位（1）同学归位了

第二轮
第一位同学4和第二位同学8比较（4<8），第一位同学比第二位同学低，所以交换位置，交换结果
8 4 2 5 7 1
然后第二位同学4和第三位同学2比较（4>2）,第二位同学比第三位同学高，不用交换位置
接着第三位和第四位比较...........
注意最后一位就不用比较了，所以比较了多少次呢，自己想一想，动动脑

接着比较第三轮，第四轮.......

细心的朋友可能发现冒泡排序就是归位的思想
下面直接上代码 -

按照模型里面价格排序排序模型数组

   //方法一:左边归位
 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];
        }
    }
}

冒泡排序分析：
时间复杂度：N *（N - i）约N * N
N是什么意思？：数组的个数

快速排序####

由于冒泡排序的时间复杂度比较高，所以就想想还有没有其他排序方式更快。可以这么试着想一想，冒泡是归位，并且是要么从左边比较归位，要么就是从右边比较归位，那么可不可以两边一起比较向中间靠拢呢，好，想到这个，那就距离快速排序不远了。
快速排序核心思想：归位 + 二分法+ 递归

快速排序原理解说######

有一个队列是 4 6 2 5 1 3 7 用快速排序排序 12345678

首先我们要知道我们要排列的顺序是从小到大，意思就是小的在左边，大的在右边，
第一轮：第一个数为基准数 4
那么A从左边开始找大于 4 的数，找到之后停止， B从右边开始找小于4的数，（B先开始找，因为基准数在左边），这样当B找到3就停止、A找到6就停止，那么开始交换，交换后的结果4 3 2 5 1 6 7，这个时候第一轮还没有结束，A和B继续找，找到就继续交换，当某一刻事件A和B相遇的时候，那么就不用找了，直接把基准数与相遇的值交换，第一轮结果
1 3 2 4 5 6 7

后面几步这里我不做解说，大家要自己写一下才能体会，要是全是文字，可能根本没有耐心看完。其实第一轮把数列分成的2组,2组又分别进行第一轮的操作，细心的同学可能发现，其实每一轮都会归位一个数，所以我把这些排序就理解的归位类的。

我觉得还是看代码比较亲切，上代码

//快速排序- 星级评分

- (void)fastSortLeftIndex:(NSInteger)left WithRightIndex:       (NSInteger)right
{
NSInteger i, j;
if(left > right) return;
LZBBaseModel *tempModel = self.foodModes[left]; //基准模型
i = left;
j = right;
while (i != j) {
    //从右边开始找比基准模型的评分小的模型
    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;
//第一轮结束之后，采用递归 - 二分法
[self fastSortLeftIndex:left WithRightIndex:i-1];
[self fastSortLeftIndex:i+1 WithRightIndex:right];
return;
//快速排序时间复杂度:N * logN - 所以我比较喜欢快速排序哦

}

快速排序的时间复杂度： N * logN 比冒泡排序爽

后期还会有算法大白话算法更新哦哦

最后赠言###

如果觉得文章对您有帮助，不要忘记star哦!😝，star 是对程序猿最大的鼓励！