堆排序的OC实现_移动开发_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > 移动开发 > 堆排序的OC实现

堆排序的OC实现

 2015/4/15 20:46:22  皮拉夫大王  程序员俱乐部  我要评论(0)
  • 摘要:/*建议先看堆调整方法,堆调整了解了,整个排序算法就算掌握了*/-(void)viewDidLoad{[superviewDidLoad];/*测试数据*/NSArray*array=@[@3,@2,@6,@4,@1,@0,@6,@7,@5];NSMutableArray*mutable=[NSMutableArrayarrayWithArray:array];mutable=[selfcreateMaxHeap:mutable];NSIntegernum=mutable.count
  • 标签:实现 堆排序
/*
 建议先看堆调整方法,堆调整了解了,整个排序算法就算掌握了
 */
- (void)viewDidLoad
{
    [super viewDidLoad];
    
    
    /*
     测试数据
     */
    NSArray *array=@[@3,@2,@6,@4,@1,@0,@6,@7,@5];

    NSMutableArray *mutable=[NSMutableArray arrayWithArray:array];

    mutable=[self createMaxHeap:mutable];
    
    NSInteger num=mutable.count;
    
    /*
     剩余的元素个数不为1时则继续调整,取出元素。取出的元素放在最后的一个节点。然后减小堆的元素的个数。所以大顶堆排序出来的是升序的。
     */
    while (num>1)
    {
        [mutable exchangeObjectAtIndex:0 withObjectAtIndex:num-1];
        
        mutable=[self maxHeapAdjust:mutable index:0 length:num-1];
        num--;
    }
}


/*
 调整堆 递归调整的过程。这个调整堆的方法传入的是待调整的数组,数组元素的长度(为什么不直接用array.count呢?因为再进行排序
 的时候,我们会动态更改无序堆的长度,而array的长度确是不变的,所以不用array.cout) 其实每调用一次调整堆方法,我们相当于只调整3个元素:父节点,左、右子节点。当左子结点是三者中最大的时候,把它和父节点进行交换。然后再递归调整以刚才的父节点(现在被降级为左子节点)为父节点的三个节点。此时为什么不用调整右子节点呢?这是由于我们建立大顶堆的过程中,都是自下而上进行调整的,此时我们没有动右子节点,且右子节点和现在的父节点(原来的左子节点)满足大顶堆的条件,所以不用调整。
 */
-(NSMutableArray*)maxHeapAdjust:(NSMutableArray *)array index:(NSInteger)index  length:(NSInteger)length
{
    NSInteger leftChildIndex =index*2+1;//获取该节点的左子节点索引
    NSInteger rightChildIndex=index*2+2;//获取该节点的右子节点索引
    NSInteger maxValueIndex=index;//暂时把该索引当做最大值所对应的索引
    
    // leftChildIndex<length你
    //array[leftChildIndex]>array[maxValueIndex] 判断左子节点的值是否大于当前最大值
    if (leftChildIndex<length && array[leftChildIndex]>array[maxValueIndex])
    {
        //把左子节点的索引作为最大值所对应的索引
        maxValueIndex=leftChildIndex;
    }
    // rightChildIndex<length
    //array[leftChildIndex]>array[maxValueIndex] 判断左子节点的值是否大于当前最大值
    if (rightChildIndex<length && array[rightChildIndex]>array[maxValueIndex])
    {
        maxValueIndex=rightChildIndex;
    }
    
    //如果该节点不是最大值所在的节点 则将其和最大值节点进行交换
    if (maxValueIndex!=index)
    {
        [array exchangeObjectAtIndex:maxValueIndex withObjectAtIndex:index];
        
        //递归乡下调整,此时maxValueIndex索引所对应的值是 刚才的父节点。
        array=[self maxHeapAdjust:array index:maxValueIndex length:length];
    }
    
    return array;
}


-(NSMutableArray*)createMaxHeap:(NSMutableArray*)array
{

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

    return array;
}

 

上一篇: 在线直播编码过程的不同凡响 下一篇: 没有下一篇了!
发表评论
用户名: 匿名