关于堆排序 - 编程论坛

#2

jmjljl2010-08-18 15:00

比如说一个话费单怎么根据通话日期通话时间通话开始时间安照这个次序排序

#3

pangding2010-08-19 00:59

自己写个 compare 的函数对象，做第三个参数传给 make_heap 和 sort_heap。

#4

lintaoyn2010-08-19 10:24

用pair吧，看看标准库的

#5

flyingcat2010-08-22 00:52

楼主指的是大小顶堆么？我写了个顶堆排序的：

程序代码：

#include <iostream>
#include <queue>
#include <cstdlib>
using namespace std;

struct cnbeta
{
    int data , start , time;
    friend bool operator< (const struct cnbeta &a,const struct cnbeta &b) //重载<操作符
    {
        if(a.data == b.data)
            if(a.time == b.time)
                return a.start > b.start ; //最后比较通话开始时间，按从小到大排
            else
                return a.time > b.time;//从小到大排通话时间
        return a.data > b.data ;//从小到大排日期
    }
};
priority_queue <cnbeta> cn;

int main()
{
    struct cnbeta tmp;
    tmp.data = 1; tmp.time = 2; tmp.start = 3;
    cn.push(tmp);
    tmp.data = 1; tmp.time = 1; tmp.start = 3;
    cn.push(tmp);
    tmp.data = 2; tmp.time = 3; tmp.start = 4;
    cn.push(tmp);
    while(!cn.empty())
    {
        tmp = cn.top();
        cn.pop();
        cout << tmp.data << " " << tmp.time << " " << tmp.start << endl;
    }
    system("pause");
    return 0;
}

#6

jmjljl2010-08-22 07:21

回复 5楼 flyingcat

你写的程序不错，我说的是大根堆排序，因为我做的排序是七八万行话单信息堆派速度快现在出学c＋＋出栈入栈我没用过看来你是高手呀

#7

pangding2010-08-22 10:51

C++ 库里有堆排序直接用就是了，不用自己写。
如果你觉得自己定义函数对象费劲，重载一下 operator < 之类的东西也行。make_heap sort_heap 默认是用小于号排大根堆。

#8

flyingcat2010-08-23 01:58

那楼主的意思应该是可以用algorithm里的sort函数，此函数可以进行高效排序

程序代码：

#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;

struct cnbeta
{
    int date , start , time;
}cn[100];

int cmp(const struct cnbeta &a , const struct cnbeta &b) //自定义的sort的比较函数
{
    if(a.date == b.date)
        if(a.time == b.time)
            return a.start < b.start;  //比较通话开始时间，按从小到大排
        else
            return a.time < b.time; //从小到大排通话时间
    return a.date < b.date; //从小到大排日期
}

int main()
{
    int i;
    cn[0].date = 1; cn[0].time = 2; cn[0].start = 3;
    cn[1].date = 1; cn[1].time = 1; cn[1].start = 3;
    cn[2].date = 2; cn[2].time = 3; cn[2].start = 4;
    sort(cn,cn+3,cmp); //对数据排序
    for (i = 0; i < 3 ; i++)
        cout << cn[i].date << " " << cn[i].time << " " << cn[i].start << endl;
    system("pause");
    return 0;
}

#9

pangding2010-08-23 08:55

楼主一直说他想用堆排，不知道有什么特别的用意。也许他只用做堆就行？不一定着急排？

#10

flyingcat2010-08-23 22:09

以下是引用pangding在2010-8-23 08:55:59的发言：

楼主一直说他想用堆排，不知道有什么特别的用意。也许他只用做堆就行？不一定着急排？

- -!唔……可是我第一个例子里也有push的操作……