`

ios:oc实现排序算法

    博客分类:
  • ios
ios 
阅读更多
下面是我用oc实现的快速排序,冒泡排序,直接插入排序和折半插入排序,希尔排序,堆排序,直接选择排序



/*******************************快速排序 start**********************************/
//随即取 当前取第一个,首先找到第一个的位置,然后分成left和right两组子集 ,分别对left和right继续执行分割(同上操作)

-(void)QuickSort:(NSMutableArray *)list StartIndex:(NSInteger)startIndex EndIndex:(NSInteger)endIndex{
   
    if(startIndex >= endIndex)return;
   
    NSNumber * temp = [list objectAtIndex:startIndex];
    NSInteger tempIndex = startIndex; //临时索引 处理交换位置(即下一个交换的对象的位置)
   
    for(int i = startIndex + 1 ; i <= endIndex ; i++){
       
        NSNumber *t = [list objectAtIndex:i];
       
        if([temp intValue] > [t intValue]){
           
            tempIndex = tempIndex + 1;
           
            [list exchangeObjectAtIndex:tempIndex withObjectAtIndex:i];
           
        }
       
    }
   
    [list exchangeObjectAtIndex:tempIndex withObjectAtIndex:startIndex];
    [self QuickSort:list StartIndex:startIndex EndIndex:tempIndex-1];
    [self QuickSort:list StartIndex:tempIndex+1 EndIndex:endIndex];

}

/*******************************快速排序 end**********************************/

/*******************************冒泡排序 start**********************************/
//取第一个 与其邻接的对比,若大则交换
-(void)BubbleSort:(NSMutableArray *)list{
   
    for (int j = 1; j<= [list count]; j++) {
           
        for(int i = 0 ;i < j ; i++){
           
            if(i == [list count]-1)return;
           
            NSInteger a1 = [[list objectAtIndex:i] intValue];
            NSInteger a2 = [[list objectAtIndex:i+1] intValue];
           
            if(a1 > a2){
                [list exchangeObjectAtIndex:i withObjectAtIndex:i+1];
            }
           
        }
       
    }
   
}
/*******************************冒泡排序 end**********************************/

/*******************************直接插入排序 start**********************************/
//从无序表中取出第一个元素,插入到有序表的合适位置,使有序表仍然有序
-(void)InsertSort:(NSMutableArray *)list{
   
    for(int i = 1 ; i < [list count] ; i++){
       
       
        int j = i;
        NSInteger temp= [[list objectAtIndex:i] intValue];
       
        while (j > 0 && temp < [[list objectAtIndex:j - 1]intValue]) {
           
            [list replaceObjectAtIndex:j withObject:[list objectAtIndex:(j-1)]];
            //list[j] = list[j-1];
            j--;
       
        }
        [list replaceObjectAtIndex:j withObject:[NSNumber numberWithInt:temp]];
        //list[j] = temp;
       
    }
   
}
/*******************************直接插入排序 end**********************************/

/*******************************折半插入排序 start**********************************/
//从无序表中取出第一个元素,利用折半查找插入到有序表的合适位置,使有序表仍然有序
-(void)BinaryInsertSort:(NSMutableArray *)list{
   
    //索引从1开始 默认让出第一元素为默认有序表 从第二个元素开始比较
    for(int i = 1 ; i < [list count] ; i++){
       
        //binary search start
        NSInteger temp= [[list objectAtIndex:i] intValue];
       
        int left = 0;
        int right = i - 1;
       
        while (left <= right) {
           
            int middle = (left + right)/2;
           
            if(temp < [[list objectAtIndex:middle] intValue]){
               
                right = middle - 1;
               
            }else{
               
                left = middle + 1;
           
            }
           
        }
        //binary search end
       
        //移动3,5,6,[4] 4是当前目标对象 利用binarysearch 找到4应该在有续集{3,5,6}的位置,然后向后移动即{3,5,6,[4]}-->{3,[4],5,6}
        for(int j = i ; j > left; j--){
           
            [list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-1]];
           
        }
        [list replaceObjectAtIndex:left withObject:[NSNumber numberWithInt:temp]];
       
    }
   
   
}
/*******************************折半插入排序 end**********************************/

/*******************************希尔排序 start**********************************/
//对直接插入排序优化,创造一个gap 来对表进行分割,对分割后的每个子集进行直接插入排序 知道gap==1结束
-(void)shellSort:(NSMutableArray *)list{

    int gap = [list count] / 2;
   
    while (gap >= 1) {
       
       
        for(int i = gap ; i < [list count]; i++){
       
            NSInteger temp = [[list objectAtIndex:i] intValue];
            int j = i;
           
            while (j >= gap && temp < [[list objectAtIndex:(j - gap)] intValue]) {
                [list replaceObjectAtIndex:j withObject:[list objectAtIndex:j-gap]];
                j -= gap;
            }
            [list replaceObjectAtIndex:j withObject:[NSNumber numberWithInt:temp]];
           
           
        }
       
        gap = gap / 2;
    }



}
/*******************************希尔排序 end**********************************/



/*******************************堆排序 start**********************************/
//创建最大堆heap 最大/最小优先级队列
-(void)CreateBiggestHeap:(NSMutableArray *)list Count:(NSInteger)count{
   
    //int count = [list count];
    int lastParentIndex = (count - 2)/2;
    for(int i = lastParentIndex; i >= 0 ; i--){
       
        NSInteger parentIndex = i;
        NSInteger parentNode = [[list objectAtIndex:parentIndex] intValue];
       
       
        //获取左子结点为当前子结点
        int currentChildIndex = 2*i + 1;
        //
       
        while (currentChildIndex <= count - 1) {
           
            NSInteger leftChildNode = [[list objectAtIndex:(currentChildIndex)] intValue];
           
            if((currentChildIndex + 1) <= count-1){//表示存在右子结点
               
                //读取右子结点
                int rightChildIndex =currentChildIndex + 1;
                NSInteger rightChildNode = [[list objectAtIndex:(rightChildIndex)] intValue];
               
                //如果右子结点为最大
                if(rightChildNode > leftChildNode && rightChildNode > parentNode){
                    [list exchangeObjectAtIndex:parentIndex withObjectAtIndex:rightChildIndex];
                    currentChildIndex = rightChildIndex;//右子结点为当前子结点 继续循环
                //左子结点最大
                }else if(leftChildNode > rightChildNode && leftChildNode > parentNode){
                    [list exchangeObjectAtIndex:parentIndex withObjectAtIndex:currentChildIndex];
                }
               
            }else{
               
                if(leftChildNode > parentNode){
                    [list exchangeObjectAtIndex:parentIndex withObjectAtIndex:currentChildIndex];
                   
                }
               
            }
           
            //更新父结点和下一个子结点
            parentIndex = currentChildIndex;
            currentChildIndex = 2*currentChildIndex + 1;
                       
        }

    }
   
}

//每次执行最大堆(索引要前移动 即排除已经排好的最大堆头元算 交换到list尾部的这个元素)
-(void)HeapSort:(NSMutableArray *)list{
   
    for(int i = [list count] ; i > 0; i--){
       
        [self CreateBiggestHeap:list Count:i];
       
        //NSLog(@"%@",list);
       
        [list exchangeObjectAtIndex:(i-1) withObjectAtIndex:0];
       
    }
   
}


/*******************************堆排序 end**********************************/

/*******************************直接选择排序 start**********************************/
//在对象集中选出最小的 若不是第一个 则与第一个交换 在剩余的对象集中选出最小的 执行前面的步骤
-(void)SelectSort:(NSMutableArray *)list{
   
    for(int i = 0 ; i<[list count]; i++){
       
        int k = i;
        for(int j = i+1 ; j<[list count]; j++){
           
            NSInteger jvalue = [[list objectAtIndex:j] intValue];
            NSInteger kvalue = [[list objectAtIndex:k] intValue];
           
            if(jvalue < kvalue){
                k = j;
            }
           
        }
        if(k != i){
            [list exchangeObjectAtIndex:i withObjectAtIndex:k];
        }
       
    }
   
}

/*******************************直接选择排序 end**********************************/
分享到:
评论

相关推荐

    iOS:demo 小功能 OC实现常用数据结构

    10. 排序算法: OC中可以使用内置的`- (NSArray *)sortedArrayUsingComparator:(NSComparator)cmptr`方法对数组进行排序,或者自定义排序算法,如冒泡排序、选择排序、插入排序、快速排序、归并排序等。 以上这些...

    oc中数组排序

    Objective-C的`sortUsingComparator:`方法内部可能会使用这些高级排序算法,但具体实现取决于系统。 六、实践应用 为了更好地复习和巩固OC中的数组排序,可以创建一个练习项目,模拟实际场景,比如根据用户输入的...

    ios-几种常用的排序方法-)OC.zip

    在iOS开发中,排序算法是基础且至关重要的编程技能,特别是在处理数据集合时。本资料主要探讨了四种常见的排序算法,它们分别是冒泡排序、选择排序、插入排序和快速排序。下面将对这些算法进行详细解释。 ### 1. ...

    OC写的寻路算法

    在iOS和macOS开发中,Objective-C(简称OC)是一种常用的编程语言,它以其强大的功能和面向对象特性深受开发者喜爱。在游戏开发、地图导航或者任何需要路径规划的场景中,寻路算法扮演着至关重要的角色。A*(A-star...

    ios设计模式开发23种设计模式OC编程

    在iOS中,常用于提供多种策略选择,如排序算法。 22. **模板方法模式**:定义一个操作中的算法骨架,而将一些步骤延迟到子类中。使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。在iOS中,用于...

    swift-iOS通讯录联系人列表较完整(中文排序)

    因此,项目可能自定义了排序算法,确保中文姓名按照正确的字典顺序排列。这通常涉及到`NSString`的`compare:`方法和自定义的比较闭包。 5. **列表视图**:联系人列表通常使用`UITableView`或`UICollectionView`来...

    比较杂的demo以及算法和GCD说明

    这个压缩包文件"比较杂的demo以及算法和GCD说明"提供了一些实践性的示例,涉及到Objective-C(OC)语言和iOS开发,同时也涵盖了算法基础和GCD(Grand Central Dispatch)的使用。下面我们将深入探讨这些知识点。 ...

    ios-热词 历史记录 文本自适应封装.zip

    - 常见的排序算法如快速排序、归并排序可以用于对热词按频率、时间等因素进行排序。 - 自定义排序规则:根据业务需求,可以设计特定的排序策略,例如结合时间、热度和用户偏好。 3. **热词高亮**: - 使用...

    新浪微博oc

    9. **搜索算法**:“热搜排行榜”可能需要实现搜索排序算法,如TF-IDF、BM25等,以及实时数据分析。 10. **社交网络API**:理解和使用新浪开放平台提供的API,遵循其认证流程和规则。 11. **用户授权与身份验证**:...

    iOS最近照片气泡弹窗

    在实现"iOS最近照片气泡弹窗"时,开发者通常会用到Objective-C(OC)语言,因为这是iOS早期主要的编程语言,虽然Swift现在更为流行,但许多现有代码库和教程依然基于OC。以下是一些关键的技术点: 1. **UIView和...

    iOS面试题-总览

    快速排序是一种高效的排序算法,采用分治策略。代码中提供的`quickSortWithArray`方法实现了这一算法,它通过选取一个基准值,将数组分为两部分,使得一部分的所有元素都小于基准,另一部分的所有元素都大于基准,...

    A星寻路_OC

    4. **启发式函数**:实现启发式函数h(n),根据实际问题的特性计算从当前节点到目标节点的预估代价。 5. **搜索过程**:循环直到找到目标节点或者没有节点可扩展。每次从队列中取出节点,检查是否为目标节点;如果...

    Objective C 二分查找(快速排序)

    在这个特定的案例中,我们关注的是使用Objective-C实现的两个核心算法:二分查找(Binary Search)和快速排序(Quick Sort)。下面我们将详细探讨这两个算法及其在Objective-C中的实现。 首先,快速排序是一种高效...

    iOS-面试宝典3.0.pdf

    在iOS开发中,多线程的底层实现主要依赖于操作系统提供的线程管理和调度机制。具体来说,iOS系统(基于macOS内核)使用的是POSIX线程库(即pthread),这是一个跨平台的线程库,支持创建和管理线程。当开发者在代码...

    百度笔试题整理

    - 快速排序是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录继续进行排序,...

    IOS缓存管理之YYCache使用详解

    这样实现了淘汰算法。由于内存访问速度很快,锁占用的时间少,因此用的速度最快的 OSSpinLockLock。 二、硬盘缓存(YYDiskCache) YYCache 的硬盘缓存采用的是文件和数据库相互配合的方式。有一个参数 ...

    OC-math-test

    4. **算法实现**:项目可能包含了各种数学算法的Objective-C实现,如排序算法(冒泡排序、快速排序等)、搜索算法(二分查找、深度优先搜索等)或者复杂的数据结构(如树、图、堆)。 5. **单元测试**:在Objective...

    武汉大学软件工程oc高建华赵小刚大作业.doc

    信息管理模块中,系统获取学生信息,通过排序算法(可能使用了课后作业中的内容)对姓名进行字母顺序排序,并实现了搜索和添加功能。成绩查询模块则通过数据库查询来获取所需成绩。数据库设计包括了学生表、成绩表和...

    北航计算机复试面试题(完整版)资料.doc

    * Andriod 和 ios 各用什么语言写 app * java 和 oc 有什么共同点和不同点 * java 一次编译多处运行的原理 * 什么是多态 * 子类继承父类的内存分配是怎样的 专业方向部分: * 什么是云计算? * 杀毒现在为什么使用...

Global site tag (gtag.js) - Google Analytics