常见的六种排序算法

排序算法 平均时间复杂度 空间复杂度 稳定性
插入排序 O(n^2) O(1) 稳定
希尔排序 O(n^1.5) O(1) 不稳定
选择排序 O(n²) O(1) 不稳定
堆排序 O(N*logN) O(1) 不稳定
冒泡排序 O(n^2) O(1) 稳定
快速排序 O(N*logN) O(N*logN) 不稳定
归并排序 O(N*logN) O(1) 稳定

算法一:插入排序

插入排序算法.png

插入排序(Insertion Sort)在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

时间复杂度: O(n^2)

步骤如下:

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置5. 将新元素插入到该位置中
  5. 重复步骤2

示例

#pragma mark -- 插入排序---
- (NSMutableArray *)insertSort:(NSMutableArray *)fromArray {

for (int i = 1; i < fromArray.count; i ++)
{
    for (int j = i ; j > 0; j --)
    {
        if ([fromArray[j] integerValue] < [fromArray[j - 1] integerValue])
        {
            NSNumber *temp = fromArray[j];
            fromArray[j] = fromArray[j - 1];
            fromArray[j - 1] = temp;

        }
        else
        {
            break;
        }
    }
}

return fromArray;

}

算法二:选择排序

选择排序.png

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。

时间复杂度: O(n^2)

步骤如下:

  • 遍历数组,找到最小的元素,将其置于数组起始位置。
  • 从上次最小元素存放的后一个元素开始遍历至数组尾,将最小的元素置于开始处。
  • 重复上述过程,直到元素排序完毕。

示例

#pragma mark ---选择排序---
- (NSMutableArray *)selectSort:(NSMutableArray *)fromArray {
  for (int i = 0; i < fromArray.count - 1; i ++)
  {
      for (int j = i + 1; j < fromArray.count; j++)
      {
          if ([fromArray[i] integerValue] > [fromArray[j] integerValue])
          {
              NSNumber *temp = fromArray[i];
              fromArray[i] = fromArray[j];
              fromArray[j] = temp;
            
          }
      }
  }
  return fromArray;
}

算法三:冒泡排序

冒泡排序.jpg

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

时间复杂度: O(n^2)

步骤如下:

  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个,直到把最大的元素放到数组尾部。
  • 遍历长度减一,对剩下的元素从头重复以上的步骤。
  • 直到没有任何一对数字需要比较时完成。

示例

#pragma mark -- 冒泡排序----
- (NSMutableArray *)bubbleSort:(NSMutableArray *)fromArray {
  for (int i = 0; i < fromArray.count; i++)
  {
      for (int j = 0; j < fromArray.count - 1 - i ; j++)
      {
          if ([fromArray[j + 1] integerValue] < [fromArray[j] integerValue])
          {
              NSNumber *temp = fromArray[j + 1];
              fromArray[j + 1] = fromArray[j];
              fromArray[j] = temp;
          }
      }
  }

  return fromArray;
}

算法四:希尔排序

希尔排序.png

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

时间复杂度: O(n^1.5)

步骤如下:

  • 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;
  • 随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

示例

#pragma mark --- 希尔排序---

- (NSMutableArray *)shellSort:(NSMutableArray *)fromArray {

    NSInteger incre = fromArray.count/2; //增量

    while (incre > 0)
    {
        for (int i = 0; i < incre; i ++)   //根据增量分为若干子序列
        {
            for (int j = i ; j < fromArray.count; j += incre)  //分组内插入排序
            {
                for (int k = j ; k > i; k -= incre)
                {
                    if ([fromArray[k] integerValue] < [fromArray[k - incre] integerValue])
                    {
                        NSNumber *temp = fromArray[k];
                        fromArray[k] = fromArray[k - incre];
                        fromArray[k - incre] = temp;
                    }
                    else
                    {
                        break;
                    }
                }
             }
        }
    
        incre /= 2;
    }

    return fromArray;
}

算法五:快速排序

快速排序.gif

快速排序(Quicksort)是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

时间复杂度:O(N*logN)

步骤:

  • 从数列中挑出一个元素,称为 “基准”(pivot),
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

示例

#pragma mark ----- 快速排序 --- 

- (NSMutableArray *)quickSork:(NSMutableArray *)fromArray {

    NSMutableArray *leftArray = [NSMutableArray array];
    NSMutableArray *rightArray = [NSMutableArray array];
    if (fromArray.count < 1)
    {
        return fromArray;
    }

    //随机一个基点
    int randomPivotPoint = arc4random() % fromArray.count;
    NSNumber *pivotValue = fromArray[randomPivotPoint];

    [fromArray removeObject:pivotValue];

    for (NSNumber *num in fromArray)
    {
        if ([num integerValue] < [pivotValue integerValue])
        {
            [leftArray addObject:num];
        }
        else
        {
            [rightArray addObject:num];
        }
    }

    //递归
    NSMutableArray *sortArray = [NSMutableArray array];
    [sortArray addObjectsFromArray:[self quickSork:leftArray]];
    [sortArray addObject:pivotValue];
    [sortArray addObjectsFromArray:[self quickSork:rightArray]];


    return sortArray;
}

算法六:归并排序

归并算法.png

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

时间复杂度:O(N*logN)

步骤如下:

  • 申请空间,创建两个数组,长度分别为两个有序数组的长度
  • 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  • 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  • 重复步骤3直到某一指针达到序列尾
  • 将另一序列剩下的所有元素直接复制到合并序列尾

示例

#pragma mark --- 归并排序 ------

- (void)mergeSort:(NSMutableArray *)list startIndex:(NSInteger)startIndex endIndex:(NSInteger)endIndex{

    if (startIndex < endIndex)
    {
    
        //取中间位置,将左右两边分别递归进行归并,直至左右两边只剩1个元素
        NSInteger middle = (startIndex + endIndex) / 2;
        [self mergeSort:list startIndex:startIndex endIndex:middle];
        [self mergeSort:list startIndex:middle+1 endIndex:endIndex];
    
        //对左右2边的数据进行合并
        NSInteger i = startIndex; //左边数据的起始位置
        NSInteger j = middle+1; //右边数据的起始位置
    
        NSMutableArray *temp = [NSMutableArray array]; //临时数组
        while (i <= middle && j <= endIndex)
        {
            //如果左边数据较小,则将其放到临时数组里,并将左边位置向后移一位
            if ([list[i] integerValue] < [list[j] integerValue])
            {
                [temp addObject:list[i]];
                i++;
            }
            //否则将右边数据放到临时数组里,并将右边位置向后移一位
            else
            {
                [temp addObject:list[j]];
                j++;
            }
        }
        //如果左边还有数据,则将剩余的部分全都复制到临时数组里
        while (i <= middle)
        {
            [temp addObject:list[i]];
            i++;
        }
        //如果右边还有数据(左右两边只可能存在一边有剩余数据的情况),则将剩余的部分全都复制到临时数组里
        while (j <= endIndex)
        {
            [temp addObject:list[j]];
            j++;
        }
    
        //再将临时数组里的数据(已经排好序了)保存到原始数据中,以达到对原始数据的排序
        for (i=0; i < temp.count; i++)
        {
            //注意:需要从startIndex位置开始,因为这里是递归调用的
            [list replaceObjectAtIndex:startIndex withObject:temp[i]];
            startIndex++;
        }
    }
}

算法七:堆排序

堆排序.png

堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

时间复杂度:O(N*logN) 由于每次重新恢复堆的时间复杂度为O(logN),共N - 1次重新恢复堆操作,再加上前面建立堆时N / 2次向下调整,每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)。

步骤如下:

  • 将数据初始化成堆,即将数据存储到一个完全二叉树中,再构造大顶堆(升序)或小顶堆(降序)。
  • 交换堆顶元素和最后一个元素,得到一个新的堆,被交换到底部的黄色部分为有序,其余堆为无序且可能不满足堆特性,所以需要对其余部分进行堆调整,调整好后继续将堆顶元素和最后一个堆低未排序元素进行交换……

示例

#pragma mark ---- 堆排序 -------
/**
 *    array: 数据源
 *    index: 节点索引
 */
-(void)maxHeapAdjust:(NSMutableArray *)array index:(NSInteger)index  length:(NSInteger)length
{
    NSInteger leftChildIndex = index * 2 + 1;  //获取该节点的左子节点索引
    NSInteger rightChildIndex = index * 2 + 2; //获取该节点的右子节点索引
    NSInteger maxValueIndex = index;//暂时把该索引当做最大值所对应的索引

    //判断左子节点的值是否大于当前最大值
    if (leftChildIndex < length && [array[leftChildIndex] integerValue] > [array[maxValueIndex] integerValue])
    {
        //把左子节点的索引作为最大值所对应的索引
        maxValueIndex = leftChildIndex;
    }


    //判断右子节点的值是否大于当前最大值
    if (rightChildIndex < length && [array[rightChildIndex] integerValue] > [array[maxValueIndex] integerValue])
    {
        maxValueIndex = rightChildIndex;
    }

    //如果该节点不是最大值所在的节点 则将其和最大值节点进行交换
    if (maxValueIndex != index)
    {
        [array exchangeObjectAtIndex:maxValueIndex withObjectAtIndex:index];
    
    }

}

//构建最大栈
- (void)createMaxHeap:(NSMutableArray*)array
{

    /*
     从最后一个非叶子节点开始 自下而上进行调整堆
     */
    for (NSInteger i = (array.count/2 - 1);i >= 0; --i)
    {
        [self maxHeapAdjust:array index:i length:array.count] ;
    }

    //从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素
    for(int j = array.count - 1;j > 0; --j)
    {
        //把第一个元素和当前的最后一个元素交换,
        [array exchangeObjectAtIndex:0 withObjectAtIndex:j];
        //不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值
        [self maxHeapAdjust:array index:0 length:j];
    }

}

//最大栈排序
- (void)maxHeapSort:(NSMutableArray *)fromArray
{

    [self createMaxHeap:fromArray];
}

---------第二部分:链表-------------

判断一个链表是否有环

声明一个节点
typedef int ElemType;  // 假定数据类型为int
typedef struct Node{

    ElemType data;
    struct Node *next;

} Node,*LinkList;
代码实现
#pragma mark  ------------链表----------------

#pragma mark ------ 判断一个链表是否有环 -----
//如何判断是否有环?如果有两个头结点指针,一个走的快,一个走的慢,那么若干步以后,快的指针总会超过慢的指针一圈。
- (BOOL)hasLoop:(LinkList)pHead{
    LinkList fast,slow;
    fast = pHead;
    slow = pHead;
    //如果无环,则fast先走到终点
    //当链表长度为奇数时,fast->Next为空
    //当链表长度为偶数时,fast为空

    while (fast != NULL && fast -> next != NULL)
    {
        fast = fast -> next -> next;
        slow = slow -> next;
    
         //如果有环,则fast会超过slow一圈
        if (fast == slow)
        {
            break;
        }
    }

    if (fast == NULL || fast -> next == NULL)
    {
        return NO;
    }
    else
        return YES;


}

Every day to write, to be continued...

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 197,099评论 5 462
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 82,846评论 2 374
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 144,146评论 0 325
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 52,789评论 1 267
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 61,656评论 5 358
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 46,467评论 1 276
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 36,870评论 3 389
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 35,500评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 39,790评论 1 293
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,828评论 2 314
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,628评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,449评论 3 316
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 37,881评论 3 300
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,077评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,376评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 41,879评论 2 343
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,089评论 2 338

推荐阅读更多精彩内容

  • 一、直接插入排序 直接插入排序(Insertion Sort)的基本思想是:每次将一个待排序的元素记录,按其关键字...
    kevin16929阅读 544评论 0 0
  • Ba la la la ~ 读者朋友们,你们好啊,又到了冷锋时间,话不多说,发车! 1.冒泡排序(Bub...
    王饱饱阅读 1,782评论 0 7
  • 该篇文章主要介绍了算法基础以及几种常见的排序算法:选择排序、插入排序、冒泡排序、快速排序、堆排序。 一、算法基础 ...
    ZhengYaWei阅读 1,237评论 0 12
  • 我一直觉得写代码也可以写出艺术,在不懂画的人的眼里,《向日葵》不过是小孩子的涂鸦,在懂代码的人眼里,那看似混乱的字...
    AidenRao阅读 4,122评论 9 59
  • 离高考还有三十二天,有些人奋起直追,有些人原地踏步。 我们班有一个女生,她初中时学习就特别认真,上了高中更加...
    一颗半糖阅读 954评论 0 6