算法—堆排序

0.对于堆我们首先考虑最小堆
10
/
20 30
/
40 60
可以看出一个完全二叉树
放在一位数组里面存储起来
0 1 2 3 4
10 20 30 40 60
eg：20 这个元素的下标是1，那么对应的父节点就是 (i-1)/2
它的字节点就是 2i+1，和 2i+2

1.接下来我们要考虑堆的建立，这个建立主要建立在插入，每次插入都是在最下面。
先举个栗子：

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.
    
    int a[100] = {0};
    int aLength = sizeof(a)/sizeof(int);
    for (int i = 0 ; i < aLength; i++) {
        a[i] = -1; //当做一个特殊字符
    }
    
    //其实这里就是在建立堆 
    insertNum(a, 10);
    insertNum(a, 40);
    insertNum(a, 60);
    insertNum(a, 30);
    insertNum(a, 20);
    insertNum(a, 8);


    deleteNum(a);
    deleteNum(a);
}

/*
 * 插入元素
 **/
void insertNum(int * a,int num) {

    int i = 0;
    while (a[i] >= 0) {
        i++;
    }
    a[i] = num;
    
    minHeapFixAfterInsertAction(a, i);
    
    printA(a);
}

/*
 * 最小堆的修复，主要是修复最后个元素i
 **/
void minHeapFixAfterInsertAction(int * a,int i) {
    
    int parent_i = (i - 1)/2;
    while (parent_i >= 0 && i > parent_i) {
        
        if (a[parent_i] > a[i]) {
            
        
            swap(&a[parent_i], &a[i]);
            
        }else {
            break;
        }
        i = parent_i; //交互完以后 i现在指向 前面的parent
        parent_i = (i-1)/2;
    }
    
}

2.接下来就是删除，删除就是删除第一个元素，然后把最后一个元素放入到第一个位置，然后再调整堆，就是把父节点的元素往下沉。

/* 删除只能删除第一个 **/
void deleteNum(int *a) {
    
    int i = 0;
    while (a[i] > 0) {
        i++;
    }
    if (i >0) {
        i--;
    }
    
    // i 表示 最后一个元素 把这个元素放到 第0个位置
    
    a[0] = a[i];
    a[i] = -1;
    int count = i; //最大的个数
   
    
    /* 开始下沉数据**/
    
    int parent = 0;
    int son    = parent*2 +1;
    while (parent < count && son < count) {
        
        if (son+1 < count && a[son] > a[son +1]) {
            
            son += 1;
        }
        
        if (a[parent] > a[son]) {
            
            swap(&a[parent], &a[son]);
            
            
        }else {
            break;
        }
        
        parent = son;
        son    = parent*2+1;
        
    }
    
    printA(a);
}

3.下面的就是打印函数和交换函数

void printA(int * a) {
    
    printf("\n");
    int i = 0;
    while (a[i] >= 0) {
        printf(" %d ",a[i]);
        i++;
    }
    
}

void swap(int * n,int * m) {
    
    int tmp = *n ;
    *n = *m;
    *m = tmp;
}

算法—堆排序

推荐阅读更多精彩内容