堆排序

2019-08-16 07:58:04来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

堆排序

 

  数据结构课上学过冒泡排序、选择排序、合并排序、快速排序等等,但就是没有堆排序。以前一看到堆,就觉得是个代码很复杂的算法,而且已经有这么多同等速度的排序算法了,没必要看堆排序了。但是最近看面试题发现有大量的关于堆的知识题,所以还是得看看,看了一下发现挺简单的,而且有其他排序算法没有的优点:支持插入删除,获取极值。

代码如下:

#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 1e4 + 5;
int a[N];

void shiftDown(int* data,int index,int number) {
    int fa = index;
    int son = fa * 2 + 1;
    while (son< number) {
        if (son + 1 < number && data[son + 1] < data[son]) son++;
        if (data[fa]>data[son]) {
            swap(data[fa], data[son]);
            fa = son;
            son = fa * 2 + 1;
        }
        else {
            break;
        }
    }
}
void sort(int* data,int number) {
    for (int i = number / 2 - 1; i >= 0; i--) {
        shiftDown(data, i, number);
    }
    //sort
    for (int i = number - 1; i >= 0; i--) {
        swap(data[0], data[i]);
        shiftDown(data, 0, i);
    }
}
int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
}

 


原文链接:https://www.cnblogs.com/chen9510/p/11297464.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Ural 1298 Knight 题解

下一篇:2019.08.02 云从科技C++后台开发