堆排序（Heap Sort）

1. 算法描述

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点值总是小于（或者大于）它的父节点。通过调整把最大值或者最小值调整到顶端然后确定此值的位置,对剩余的数据继续进行堆排序.

• 创建堆,第一趟使数据满足堆的特性;
• 交换首数据及未排序数据末尾数据,固定排序好的数据位置；
• 对剩余数据进行堆排序；

2. 过程演示

Heap Sort.gif

堆排序

原始数据

34 54  12  78 3  45  9 

// 建堆过程
                34
          54           12                            
       78     3     45     9 
    

                34
          54           45                            
       78     3     12     9 


               34
         78          45                            
      54     3   12      9 


               78
          34         45                            
      54     3    12      9        


            78
       54        45                            
    34     3  12      9 

// 一趟堆排序过程

              9
        54          45                            
    34      3   12       #78
    
              54
        9           45                            
    34     3    12       #78

                 54
         34              45                            
    9         3     12       #78

                 54
          34              45                            
      9       3      12        #78        

// 第二次交换 确定了  54,78 的位置
                12
         34               45                            
    9         3      #54        78# 

3. 代码实现

/*
 * 堆排序
 */

- (void)heapSort:(NSMutableArray *)sortArray {
    
    // 建大跟堆
    NSInteger lastFatherNote = sortArray.count / 2;
    for (NSInteger i = lastFatherNote; i >= 0; i --) {
        [self adjustHeap:sortArray head:i length:sortArray.count];
        self.count1 ++;
    }
    
    // 开始调整排序
    for (NSInteger i = sortArray.count - 1; i >= 0; i--) {
        [sortArray exchangeObjectAtIndex:0 withObjectAtIndex:i];  // 建堆过程 已经把最大值调整到顶部  所以把顶部下沉确定位置 以后不再进入排序过程
        [self adjustHeap:sortArray head:0 length:i];
        self.count1 ++;
    }
}


// 堆的调整
- (void)adjustHeap:(NSMutableArray *)sortArray
              head:(NSInteger)head
            length:(NSInteger)length {
    
    NSInteger left = 2 *head + 1;
    NSInteger right = 2 *head + 2;
    
    if (left >= length) {
        return; // 只有一个元素 不做处理
    }
    
    NSInteger bigger = left;
    
    if (right < length) {
        if ([sortArray[right] integerValue] > [sortArray[bigger] integerValue])  {
            bigger = right;
        }
    }
    
    // 如果大的子节点 大于父节点  则交换 继续向下调整
    if ([sortArray[bigger] integerValue] > [sortArray[head] integerValue]) {
        [sortArray exchangeObjectAtIndex:bigger withObjectAtIndex:head];
        [self adjustHeap:sortArray head:bigger length:length];
    }
    self.count2 ++;
}

4. 验证

 NSArray *arr = [self pakageNumber:1000];    
 NSMutableArray *sortArray = [NSMutableArray arrayWithArray:arr];
 [self heapSort:sortArray];
count1  :1501                        // 外层循环
count2 : 8414                      // 内层循环

一万条数据所用时间
time:0.044660;