iOS话题：算法-排序、二叉树-2020-05-13

排序

排序是iOS算法中提及最多的话题，比较有名的有八大排序算法。

image.png

数据结构常见的八大排序算法（详细整理）

八大排序算法

iOS排序算法

七种常见的数组排序算法整理(C语言版本)

1.快速排序

这个是曝光率最高的排序算法，基本思想：挖坑填数+分治法

  • 从序列当中选择一个基准数(pivot)，在这里我们选择序列当中第一个数最为基准数；

  • 将序列当中的所有数依次遍历，比基准数大的位于其右侧，比基准数小的位于其左侧；

  • 递归，左右两边分别进行以上步骤；退出条件：未排序序列长度为0；

  • 快速排序的Object-C代码如下：

- (void)quickSort:(NSMutableArray *)mutableArray start:(NSInteger)start end:(NSInteger)end {
    // 递归函数退出条件：只有1个元素或者没有元素
    if (start >= end) {
        return;
    }
    
    // 取第一个元素为基准元素
    id pivot = mutableArray[start];
    
    // 设置可以移动的下标
    NSInteger i = start;
    NSInteger j = end;
    
    // 不断重复，将小于基准pivot的移到左边；将大于基准pivot的移到右边；形成两个子数组；
    while (i < j) {
        // 从右开始向左寻找第一个小于pivot的值；(对于本来就大于或者等于基准的数，保持不动)
        while ((i < j) && ([mutableArray[j] hash] >= [pivot hash])) {
            j--;
        }
        // 将小于pivot的值移到左边;填坑mutableArray[I]
        if (i < j) {
            mutableArray[i] = mutableArray[j];
        }
        
        // 从左开始向右寻找第一个大于pivot的值;(对于本来就小于或者等于基准的数，保持不动)
        while ((i < j) && ([mutableArray[i] hash] <= [pivot hash])) {
            I++;
        }
        // 将大于pivot的值移到右边; 填坑mutableArray[j]；(mutableArray[j]上一步已经移到左边，现在已经是坑了)
        if (i < j) {
            mutableArray[j] = mutableArray[I];
        }
    }
    // 循环结束后，说明 i==j，此时左边的值全都小于pivot,右边的值全都大于pivot
    // 将一开始就挖出的基准pivot放回两个子数组的中间位置
    mutableArray[i] = pivot;    // 这个时候i == j；用mutableArray[j] = pivot;也是可以的
    
    // 递归，对左右两个子数组继续进行“挖坑填数”操作; 这个时候i==j； i或者j的位置是基准数，已经排好，不需要再参加排序
    // 左侧序列继续排序
    [self quickSort:mutableArray start:start end:(i-1)];
    // 右侧序列继续排序
    [self quickSort:mutableArray start:(j+1) end:end];
}

由于iOS中数组成员是对象，所以取hash值进行比较。注意：对象不能直接用"<、 =、 >"等进行比较，否则可能会出现@88 > @89的情况。实际试验，对于NSString和NSNumber，采用hash值比较，效果很不错。

  • 封装：实现算法的时候，以可变数组为参数，排序之后，可变数组参数内容被改变。在实际使用中，改变传入参数内容的做法很不好。所以封装一层，不改变使用者给的参数，将排序结果，以一个新数组的形式返回，保持“纯函数”的特性。
/**
 排序算法名称
 */
typedef NS_ENUM(NSInteger,SortType) {
    // 快速排序
    SortTypeQuick = 1,
};

// 统一封装，以返回值的形式给出排序结果，不改变用户给出的参数，保持“纯函数”特性
- (nullable NSArray *)sort:(nullable NSArray *)array type:(SortType)type {
    // 参数检查
    if ((array == nil) || (array.count <= 1)) {
        return nil;
    }
    
    // 使用可变数组进行操作，不改变输入参数
    NSMutableArray *tempArray = [NSMutableArray arrayWithArray:array];
    
    // 根据SortType参数选择不同的排序算法
    switch (type) {
        case SortTypeQuick:
            [self quickSort:tempArray start:0 end:(tempArray.count-1)];
            break;
            
        default:
            break;
    }
    
    // 返回排序后的数组
    return [tempArray copy];
}
  • 测试：可以用一个数字和字符的混合数组进行测试：
//
//
// 统一的测试代码
//
//
- (void)sortTest:(SortType)type {
    NSArray *arrayBeforeSort = [NSMutableArray arrayWithObjects:@89,@"hello",@22,@95,@"Hello",@66,@22,@"world",@57, nil];
    NSLog(@"快速排序之前：%@", arrayBeforeSort);
    NSArray *arrayAfterSort = [self sort:arrayBeforeSort type:type];
    NSLog(@"快速排序之后：%@", arrayAfterSort);
}
企业微信截图_d4a70aab-e5ef-4bed-ad68-cabf71fbd223.png

2. 冒泡排序

  • 将序列当中的左右元素，依次比较，保证右边的元素始终大于左边的元素；
    （ 第一轮结束后，序列最后一个元素一定是当前序列的最大值；）
  • 对序列当中剩下的n-1个元素再次执行步骤1。
  • 对于长度为n的序列，一共需要执行n-1轮比较
- (void)bubbleSort:(NSMutableArray *)mutableArray {
    // 执行n-1轮，最后一个元素不需要比较
    for (NSInteger i = 0; i < (mutableArray.count - 1); i++) {
        for (NSInteger j = 0; j < (mutableArray.count - i - 1); j++) {
            // 如果比旁边的元素大，就交互
            if ([mutableArray[j] hash] > [mutableArray[j+1] hash]) {
                id temp = mutableArray[j];
                mutableArray[j] = mutableArray[j+1];
                mutableArray[j+1] = temp;
            }
        }
    }
}

3. 选择排序

  • 从当前序列选出最小的元素，排在第1位；

  • 从余下的n-1个元素中选出最小值，排在第2位；

  • .... 进行n-1轮，就排好了。

- (void)selectSort:(NSMutableArray *)mutableArray {
    // 执行n-1轮，最后一个元素不需要比较
    for (NSInteger i = 0; i < (mutableArray.count - 1); i++) {
        // 最小值默认是本轮第1个
        NSInteger minIndex = I;
        
        // 将余下的逐个比较，记下最小值的下标
        for (NSInteger j = i; j < mutableArray.count; j++) {
            if ([mutableArray[j] hash] < [mutableArray[minIndex] hash]) {
                minIndex = j;
            }
        }
        // 将最小值和当前位置交换
        if (minIndex != i) {
            id temp = mutableArray[I];
            mutableArray[i] = mutableArray[minIndex];
            mutableArray[minIndex] = temp;
        }
    }
}

4. 堆排序

  • 首先将序列构建称为"大顶堆"；
    （这样满足了大顶堆那条性质：位于根节点的元素一定是当前序列的最大值）
image.png
  • 取出当前大顶堆的根节点，将其与序列末尾元素进行交换；
    （此时：序列末尾的元素为已排序的最大值；由于交换了元素，当前位于根节点的堆并不一定满足大顶堆的性质）
image.png

交换后，排好了一个元素，但是堆被破坏了。接下来仍然需要先创建“大顶堆”，然后交换

  • .... 继续重复n-1次，全部排好。
// 大顶堆调整
- (void)maxHeapAdjust:(NSMutableArray *)mutableArray start:(NSInteger)start end:(NSInteger)end {
    // 建立父节点指标和子节点下标
    NSInteger dadIndex = start;
    NSInteger sonIndex = 2 * dadIndex + 1;
    
    // 在范围内，进行比较和交互，保证父节点比两个子节点都大
    while (sonIndex <= end) {
        // 两个子节点比较，取大的那个
        if (((sonIndex + 1) <= end) && ([mutableArray[sonIndex + 1] hash] > [mutableArray[sonIndex] hash])) {
            sonIndex++;
        }
        
        // 父节点大于子节点，调整完成
        if ([mutableArray[dadIndex] hash] > [mutableArray[sonIndex] hash]) {
            return;
        } else {
            // 父节点小于子节点，交互两个值
            id temp = mutableArray[dadIndex];
            mutableArray[dadIndex] = mutableArray[sonIndex];
            mutableArray[sonIndex] = temp;
            // 父节点较小，和子节点交互完毕后，继续与孙子节点比较
            dadIndex = sonIndex;
            sonIndex = 2 * dadIndex + 1;
        }
    }
}

// 堆排序
- (void)heapSort:(NSMutableArray *)mutableArray {
    // 初始化，创建大顶推；
    // 最后一个有孩子的节点的位置 i =  (length -1) / 2
    for (NSInteger i = (mutableArray.count - 1) / 2; i >= 0; i--) {
        [self maxHeapAdjust:mutableArray start:i end:(mutableArray.count - 1)];
    }
    
    // 重复n次； 1.把根节点（第一个元素，也就是最大的元素）和当前排列的元素交换，排好一个；2，将剩余的元素调整为大顶推
    for (NSInteger j = (mutableArray.count - 1); j > 0; j--) {
        // 交换根节点，也就是0号元素和当前位置
        id temp = mutableArray[0];
        mutableArray[0] = mutableArray[j];
        mutableArray[j] = temp;
        // 调整剩余的元素为大顶堆
        [self maxHeapAdjust:mutableArray start:0 end:(j-1)];
    }
}

5. 插入排序

插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止

// 插入排序
- (void)insertSort:(NSMutableArray *)mutableArray {
    // 遍历数组中的所有元素，其中0号索引元素默认已排序，因此从1开始
    for (NSInteger i = 1; i < mutableArray.count; i++) {
        // 要找插入位置，前面已经排好的序列要往后面挪一个位置，所以要先把当前的待插入元素先保存起来
        id temp = mutableArray[I];
        // 从已经排好的序列尾部往前找，第一个数也要参与比较
        for (NSInteger j = i; j > 0; j--) {
            if ([mutableArray[j-1] hash] > [temp hash]) {
                // 前面的元素比现在的大，就往后挪一格；
                mutableArray[j] = mutableArray[j-1];
                // 如果第0号元素都比当前元素大，那么当前元素要插入第0号位置
                if ((j-1) == 0) {
                    mutableArray[0] = temp;
                    break;
                }
            } else {
                // 后面的元素比当前的大，就说明找到位置了，插入，完成此轮排序
                mutableArray[j] = temp;
                break;
            }
        }
    }
}

未完待续.....

希尔排序，归并排序，基数排序这三种，看了参考文章，不是很理解，暂时就不实践了。

二叉搜索树

  • 树： 每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；

  • 二叉树： 是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。
    一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。
    在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。

  • 二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树： 它或者是一棵空树，或者是具有下列性质的二叉树：

  1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值，（大顶堆）；
  2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值，（小顶堆）；
  3. 它的左、右子树也分别为二叉排序树。
  4. 没有键值相等的节点。

  • 二叉树遍历：以跟为参考来说。前序：根-》左-》右；中序：左-》根-》右；后序：左-》右-》根

  • 二叉树算法主要是递归的思想

【iOS】二叉树的各种问题（OC代码）

二叉搜索树的Model

对于二叉搜索树这种数据类型，用简单的数组来表示是不适合的。所以要建立一个模型：

  • 值： 就用最简单的整数来表示，实际使用中，这个整型值也是必不可少的，可以单做key来用，这是二叉搜索树排序的凭证。

  • 左子树： 用一个同类型的指针表示

  • 右子树： 用一个同类型的指针表示

以上3个是二叉搜索树必不可少的属性，

@interface BinaryTreeNode : NSObject

// 值；当做key来用，是排序用的凭证
@property (assign, nonatomic) NSInteger value;

// 左子树
@property (strong, nonatomic) BinaryTreeNode *leftChild;

// 右子树
@property (strong, nonatomic) BinaryTreeNode *rightChild;

// ... 添加其他需要的属性成员

@end

添加节点

  • 与链表类似，一个根节点*rootNode就代表一棵树。要添加节点，就要从这个根节点*rootNode开始。

  • 采用“递归”的思想，就很简单：如果节点还不存在，那么就新建节点，添加完成，这也是“递归”的退出条件。如果值偏小，那么就去“左子树”；如果值偏大，那么就去“右子树”；如果值相等，就忽略。

  • 到了“左子树”或者“右子树”，重复上面的过程就可以了。这就是“递归”。

  • 最后，返回根节点*rootNode，这代表了一棵树。

/**
 *  向二叉排序树节点添加一个节点
 *
 *  @param rootNode 根节点
 *  @param value    值
 *
 *  @return 根节点
 */
+ (BinaryTreeNode *)addNode:(BinaryTreeNode *)rootNode value:(NSInteger)value {
    // 根节点不存在，创建节点
    if (rootNode == nil) {
        rootNode = [[BinaryTreeNode alloc] init];
        rootNode.value = value;
        NSLog(@"node:%@", @(value));
    } else if (value < rootNode.value) {
        NSLog(@"to left");
        // 值小于根节点，则插入到左子树；这是递归，左子树将做同样的事
        rootNode.leftChild = [BinaryTree addNode:rootNode.leftChild value:value];
    } else if (value > rootNode.value) {
        NSLog(@"to right");
        // 值大于根节点，则插入到右子树；这是递归，右子树将做同样的事
        rootNode.rightChild = [BinaryTree addNode:rootNode.rightChild value:value];
    } else {
        NSLog(@"二叉排序树没有键值相等的节点，值%@已存在，不能插入", @(value));
    }
    return rootNode;
}

创建二叉搜索树

反复调用添加节点方法就可了。

/**
 *  创建二叉排序树
 *  二叉排序树：左节点值全部小于根节点值，右节点值全部大于根节点值
 *
 *  @param values 数组
 *
  *  @return 二叉树根节点
 */
+ (BinaryTreeNode *)createTreeWithValues:(NSArray<NSNumber *> *)values {
    BinaryTreeNode *rootNode = nil;
    for (NSNumber *number in values) {
        NSInteger value = [number integerValue];
        rootNode = [BinaryTree addNode:rootNode value:value];
    }
    return rootNode;
}
  • 测试一下，新建一个Controller，用一个属性持有这个二叉搜索树。
@interface TreeViewController ()

// 二叉搜索树的根节点，代表一棵树
@property (strong, nonatomic) BinaryTreeNode *rootNode;

@end

输入用一串值，得到一颗二叉搜索树

// 创建树
- (IBAction)createButtonTouched:(id)sender {
    NSArray *values = @[@200, @23, @456, @89, @23, @670, @5674, @15];
    self.rootNode = [BinaryTree createTreeWithValues:values];
}

用断点，查看“链式”结构，同时通过log可以看出创建过程。

企业微信截图_ff493fa9-63a7-44ce-87d0-5d7ee4a0f872.png
二叉搜索树的例子.jpg

遍历

/**
 *  先序遍历：先访问根，再遍历左子树，再遍历右子树。典型的递归思想。
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)preOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {
    if (rootNode) {
        // 先访问
        if (handler) {
            handler(rootNode);
        }
        // 再遍历左右子树
        [BinaryTree preOrderTraverseTree:rootNode.leftChild handler:handler];
        [BinaryTree preOrderTraverseTree:rootNode.rightChild handler:handler];
    }
}

/**
 *  中序遍历
 *  先遍历左子树，再访问根，再遍历右子树
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)inOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)  (BinaryTreeNode *treeNode))handler {
    if (rootNode) {
        // 先遍历左子树
        [BinaryTree inOrderTraverseTree:rootNode.leftChild handler:handler];
        
        // 访问节点
        if (handler) {
            handler(rootNode);
        }
    
        // 最后遍历右子树
        [BinaryTree inOrderTraverseTree:rootNode.rightChild handler:handler];
    }
}

/**
 *  后序遍历
 *  先遍历左子树，再遍历右子树，再访问根
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)postOrderTraverseTree:(BinaryTreeNode *)rootNode handler:(void(^)(BinaryTreeNode *treeNode))handler {
    if (rootNode) {
        // 先遍历左右子树
        [BinaryTree postOrderTraverseTree:rootNode.leftChild handler:handler];
        [BinaryTree postOrderTraverseTree:rootNode.rightChild handler:handler];
        
        // 最后访问节点
        if (handler) {
            handler(rootNode);
        }
    }
}

测试一下：

// 先序遍历
- (IBAction)preOrderButtonTouched:(id)sender {
    NSMutableArray<NSNumber *> *preArray = [NSMutableArray array];
    [BinaryTree preOrderTraverseTree:self.rootNode handler:^(BinaryTreeNode * _Nonnull treeNode) {
        [preArray addObject:[NSNumber numberWithInteger:treeNode.value]];
    }];
    NSLog(@"先序遍历：%@", preArray);
}

// 中序遍历
- (IBAction)inOrderButtonTouched:(id)sender {
    NSMutableArray<NSNumber *> *inArray = [NSMutableArray array];
    [BinaryTree inOrderTraverseTree:self.rootNode handler:^(BinaryTreeNode * _Nonnull treeNode) {
        [inArray addObject:[NSNumber numberWithInteger:treeNode.value]];
    }];
    NSLog(@"中序遍历：%@", inArray);
}

// 后序遍历
- (IBAction)postOrderButtonTouched:(id)sender {
    NSMutableArray<NSNumber *> *postArray = [NSMutableArray array];
    [BinaryTree postOrderTraverseTree:self.rootNode handler:^(BinaryTreeNode * _Nonnull treeNode) {
        [postArray addObject:[NSNumber numberWithInteger:treeNode.value]];
    }];
    NSLog(@"后序遍历：%@", postArray);
}

根据二叉树的图，可以查看log中的遍历顺序是否符合：

企业微信截图_aee2f449-badd-4332-a0c5-9f00bbb7b2fe.png

翻转

/**
 * 翻转二叉树（又叫：二叉树的镜像）
 *
 * @param rootNode 根节点
 *
 * @return 翻转后的树根节点（其实就是原二叉树的根节点）
 */
+ (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode {
    // 空节点
    if (!rootNode) {
        return nil;
    }
    
    // 没有子节点
    if (!rootNode.leftChild && !rootNode.rightChild) {
        return rootNode;
    }
    
    // 左右子树递归
    [BinaryTree invertBinaryTree:rootNode.leftChild];
    [BinaryTree invertBinaryTree:rootNode.rightChild];
    
    // 左右节点交换
    BinaryTreeNode *tempNode = rootNode.leftChild;
    rootNode.leftChild = rootNode.rightChild;
    rootNode.rightChild = tempNode;
    return rootNode;
}

测试：将一开始创建的二叉搜索树翻转，然后画出图，与原图比较

企业微信截图_dfc9287b-de1e-43ec-bb82-51668d97a0b1.png
二叉搜索树翻转.jpg

Demo地址

Demo地址

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 199,271评论 5赞 466
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 83,725评论 2赞 376
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 146,252评论 0赞 328
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 53,634评论 1赞 270
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 62,549评论 5赞 359
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 47,985评论 1赞 275
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,471评论 3赞 390
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,128评论 0赞 254
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,257评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,233评论 2赞 317
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,235评论 1赞 328
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,940评论 3赞 316
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,528评论 3赞 302
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,623评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,858评论 1赞 255
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,245评论 2赞 344
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 41,790评论 2赞 339