箱排序

本文主要是介绍箱排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

箱排序

假定用一个链表保存一个班级学生清单。结点的数据有：学生姓名和考试分数。假设分数是0~100的整数。

采用箱排序可以把分数相同的结点放在同一个箱子里，然后把箱子连接起来就得到了有序的链表

链表定义

#include<iostream>
#include <sstream>

using namespace std;

class illegalParameterValue {
public:
    illegalParameterValue() : message("Illegal parameter value") {}

    explicit illegalParameterValue(char *theMessage) {
        message = theMessage;
    }

    explicit illegalParameterValue(const string &theMessage) {
        message = theMessage;
        cout << message << endl;
    }

    void outputMessge() {
        cout << message << endl;
    }

private:
    string message;
};

// 链表结点的结构定义
template<class T>
struct chainNode {
    // 数据成员
    T element;
    chainNode<T> *next;

    // 方法
    chainNode() {}

    chainNode(const T &element) { this->element = element; }

    chainNode(const T &element, chainNode<T> *next) {
        this->element = element;
        this->next = next;
    }
};

template<class T>
class chainList {
public:
    // 构造函数，复制构造函数和构析函数
    chainList(int initialCapacity = 10);

    chainList(const chainList<T> &);

    ~chainList();

    // 抽象数据类型ADT的方法
    bool empty() const { return listSize == 0; }

    int size() const { return listSize; }

    T &get(int theIndex) const;

    int indexOf(const T &theElement) const;

    void erase(int theIndex);

    void insert(int theIndex, const T &theElement);

    void output(ostream &out) const;

protected:
    void checkIndex(int theIndex) const; // 如果索引无效抛出异常
    chainNode<T> *firstNode; // 指向链表第一个结点的指针
    int listSize;
};

template<class T>
void chainList<T>::checkIndex(int theIndex) const {
    if (theIndex < 0 || theIndex >= size()) {
        stringstream s;
        s << "theIndex " << theIndex << " is illegal";
        illegalParameterValue(s.str());
    }
}

// 构造函数和复制构造函数
template<class T>
chainList<T>::chainList(int initialCapacity) {
    // 构造函数
    if (initialCapacity < 1) {
        ostringstream s;
        s << "Initial capacity = " << initialCapacity << " Muse be > 0 ";
        throw illegalParameterValue(s.str());
    }
    firstNode = nullptr;
    listSize = 0;
}

template<class T>
chainList<T>::chainList(const chainList<T> &theList) {
    // 复制构造函数
    listSize = theList.listSize;
    if (listSize == 0) {
        // 链表theList为空
        firstNode = nullptr;
        return;
    }
    // 链表theList为非空
    chainNode<T> *sourceNode = theList.firstNode; // 复制链表theList的节点
    firstNode = new chainNode<T>(sourceNode->element); // 复制链表theList的首元素
    sourceNode = sourceNode->next;
    chainNode<T> *targetNode = firstNode; // 当前链表*this的最后一个结点
    while (sourceNode != nullptr) {
        // 复制剩余元素
        targetNode->next = new chainNode<T>(sourceNode->element);
        targetNode = targetNode->next;
        sourceNode = sourceNode->next;
    }
    targetNode->next = nullptr; // 链表结束
}

// 构析函数
template<class T>
chainList<T>::~chainList() {
    // 链表构析函数，删除链表的所有节点
    while (firstNode != nullptr) {
        // 删除首结点
        chainNode<T> *nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
}

// get方法
template<class T>
T &chainList<T>::get(int theIndex) const {
    // 返回索引为theIndex的㢝
    // 若该元素不存在，则抛出异常
    checkIndex(theIndex);
    // 移向所需要的结点
    chainNode<T> *currentNode = firstNode;
    for (int i = 0; i < theIndex; ++i)
        currentNode = currentNode->next;
    return currentNode->element;
}

// 返回元素theElement首次出现时的索引
template<class T>
int chainList<T>::indexOf(const T &theElement) const {
    // 返回元素theElement首次出现时的索引
    // 若该元素不存在，则返回-1
    // 搜寻链表寻找元素theElement
    chainNode<T> *currentNode = firstNode;
    int index = 0;
    while (currentNode != nullptr && currentNode->element != theElement) {
        // 移向下一个结点
        currentNode = currentNode->next;
        ++index;
    }
    // 确定是否找到所需的元素
    if (currentNode == nullptr)
        return -1;
    else
        return index;
}

// 删除索引为theIndex的元素
template<class T>
void chainList<T>::erase(int theIndex) {
    // 删除索引为theIndex元素
    // 若该元素不存在，则抛出异常
    checkIndex(theIndex);
    // 索引有效
    chainNode<T> *deleteNode;
    if (theIndex == 0) {
        // 删除链表的头节点
        deleteNode = firstNode;
        firstNode = firstNode->next;
    } else {
        // 用指针p指向要删除节点的前驱结点
        chainNode<T> *p = firstNode;
        for (int i = 0; i < theIndex - 1; ++i)
            p = p->next;
        deleteNode = p->next;
        p->next = p->next->next;
    }
    --listSize;
    delete deleteNode;
}

// 插入theElement并使得其索引为theIndex
template<class T>
void chainList<T>::insert(int theIndex, const T &theElement) {
    // 在索引为theIndex的位置上
    // 若该位置非法，则抛出异常
    if (theIndex < 0 || theIndex > listSize) {
        // 无效索引
        ostringstream s;
        s << "index = " << theIndex << " size = " << listSize;
        throw illegalParameterValue(s.str());
    }
    if (theIndex == 0)
        // 在链表头插入
        firstNode = new chainNode<T>(theElement, firstNode);
    else {
        // 寻找新元素的前驱结点
        chainNode<T> *p = firstNode;
        for (int i = 0; i < theIndex - 1; ++i)
            p = p->next;
        // 在p之后插入
        p->next = new chainNode<T>(theElement, p->next);
    }
    ++listSize;
}

template<class T>
void chainList<T>::output(ostream &out) const {
    // 把链表放入输出流
    for (auto *currentNode = firstNode; currentNode != nullptr; currentNode = currentNode->next)
        out << currentNode->element;
}

// 重载
template<class T>
ostream &operator<<(ostream &out, const chainList<T> &x) {
    x.output(out);
    return out;
}

结点定义

struct studentRecord {
    string name;
    int score;
	// 重载类型转换操作符int()，这样可以使用+、/、<=和!=这些算数和关系操作符
    explicit operator int() const { return score; } // 重载类型转换操作符int()转换为int类型
	// 重载操作符int()只有在操作符号!=和<<以外操作中被调用
    int operator!=(const studentRecord &x) const { return score != x.score; } // 重载运算符
};
// 重载<<
ostream &operator<<(ostream &out, const studentRecord &x) {
    out << x.name << ": " << x.score << endl;
    return out;
}

箱排序方法定义

// 使用链表的多个方法进行箱排序
void binSort(chainList<studentRecord> &theChain, int range) {
    // 按分数排序
    chainList<studentRecord> *bin; // 声明箱子
    bin = new chainList<studentRecord>[range + 1]; // 总共有range+1个箱子

    // 把学生记录从链表中取出，然后分配到箱子中
    int numberOfElements = theChain.size(); // 记录链表中元素数量
    for (int i = 0; i < numberOfElements; ++i) {
        studentRecord x = theChain.get(0); // 得到链表中第一个结点
        theChain.erase(0); // 将该节点从链表中删除
        bin[x.score].insert(0, x); // 将该节点数据连接到对应分数的箱子里
    }
    // 从箱子中收集元素
    for (int j = range; j >= 0; --j) {
        while (!bin[j].empty()) { // 如果第j个箱子中的元素不为0
            studentRecord x = bin[j].get(0); // 拿出第j个箱子中的第一个元素
            bin[j].erase(0); // 然后从箱子中删除该元素
            theChain.insert(0, x); // 将该元素通过头插法加入到链表中
        }
    }
    delete[] bin; // 最后删除箱子
}

全部代码

#include<iostream>
#include <sstream>

using namespace std;

class illegalParameterValue {
public:
    illegalParameterValue() : message("Illegal parameter value") {}

    explicit illegalParameterValue(char *theMessage) {
        message = theMessage;
    }

    explicit illegalParameterValue(const string &theMessage) {
        message = theMessage;
        cout << message << endl;
    }

    void outputMessge() {
        cout << message << endl;
    }

private:
    string message;
};

// 链表结点的结构定义
template<class T>
struct chainNode {
    // 数据成员
    T element;
    chainNode<T> *next;

    // 方法
    chainNode() {}

    chainNode(const T &element) { this->element = element; }

    chainNode(const T &element, chainNode<T> *next) {
        this->element = element;
        this->next = next;
    }
};

template<class T>
class chainList {
public:
    // 构造函数，复制构造函数和构析函数
    chainList(int initialCapacity = 10);

    chainList(const chainList<T> &);

    ~chainList();

    // 抽象数据类型ADT的方法
    bool empty() const { return listSize == 0; }

    int size() const { return listSize; }

    T &get(int theIndex) const;

    int indexOf(const T &theElement) const;

    void erase(int theIndex);

    void insert(int theIndex, const T &theElement);

    void output(ostream &out) const;

protected:
    void checkIndex(int theIndex) const; // 如果索引无效抛出异常
    chainNode<T> *firstNode; // 指向链表第一个结点的指针
    int listSize;
};

template<class T>
void chainList<T>::checkIndex(int theIndex) const {
    if (theIndex < 0 || theIndex >= size()) {
        stringstream s;
        s << "theIndex " << theIndex << " is illegal";
        illegalParameterValue(s.str());
    }
}

// 构造函数和复制构造函数
template<class T>
chainList<T>::chainList(int initialCapacity) {
    // 构造函数
    if (initialCapacity < 1) {
        ostringstream s;
        s << "Initial capacity = " << initialCapacity << " Muse be > 0 ";
        throw illegalParameterValue(s.str());
    }
    firstNode = nullptr;
    listSize = 0;
}

template<class T>
chainList<T>::chainList(const chainList<T> &theList) {
    // 复制构造函数
    listSize = theList.listSize;
    if (listSize == 0) {
        // 链表theList为空
        firstNode = nullptr;
        return;
    }
    // 链表theList为非空
    chainNode<T> *sourceNode = theList.firstNode; // 复制链表theList的节点
    firstNode = new chainNode<T>(sourceNode->element); // 复制链表theList的首元素
    sourceNode = sourceNode->next;
    chainNode<T> *targetNode = firstNode; // 当前链表*this的最后一个结点
    while (sourceNode != nullptr) {
        // 复制剩余元素
        targetNode->next = new chainNode<T>(sourceNode->element);
        targetNode = targetNode->next;
        sourceNode = sourceNode->next;
    }
    targetNode->next = nullptr; // 链表结束
}

// 构析函数
template<class T>
chainList<T>::~chainList() {
    // 链表构析函数，删除链表的所有节点
    while (firstNode != nullptr) {
        // 删除首结点
        chainNode<T> *nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
}

// get方法
template<class T>
T &chainList<T>::get(int theIndex) const {
    // 返回索引为theIndex的㢝
    // 若该元素不存在，则抛出异常
    checkIndex(theIndex);
    // 移向所需要的结点
    chainNode<T> *currentNode = firstNode;
    for (int i = 0; i < theIndex; ++i)
        currentNode = currentNode->next;
    return currentNode->element;
}

// 返回元素theElement首次出现时的索引
template<class T>
int chainList<T>::indexOf(const T &theElement) const {
    // 返回元素theElement首次出现时的索引
    // 若该元素不存在，则返回-1
    // 搜寻链表寻找元素theElement
    chainNode<T> *currentNode = firstNode;
    int index = 0;
    while (currentNode != nullptr && currentNode->element != theElement) {
        // 移向下一个结点
        currentNode = currentNode->next;
        ++index;
    }
    // 确定是否找到所需的元素
    if (currentNode == nullptr)
        return -1;
    else
        return index;
}

// 删除索引为theIndex的元素
template<class T>
void chainList<T>::erase(int theIndex) {
    // 删除索引为theIndex元素
    // 若该元素不存在，则抛出异常
    checkIndex(theIndex);
    // 索引有效
    chainNode<T> *deleteNode;
    if (theIndex == 0) {
        // 删除链表的头节点
        deleteNode = firstNode;
        firstNode = firstNode->next;
    } else {
        // 用指针p指向要删除节点的前驱结点
        chainNode<T> *p = firstNode;
        for (int i = 0; i < theIndex - 1; ++i)
            p = p->next;
        deleteNode = p->next;
        p->next = p->next->next;
    }
    --listSize;
    delete deleteNode;
}

// 插入theElement并使得其索引为theIndex
template<class T>
void chainList<T>::insert(int theIndex, const T &theElement) {
    // 在索引为theIndex的位置上
    // 若该位置非法，则抛出异常
    if (theIndex < 0 || theIndex > listSize) {
        // 无效索引
        ostringstream s;
        s << "index = " << theIndex << " size = " << listSize;
        throw illegalParameterValue(s.str());
    }
    if (theIndex == 0)
        // 在链表头插入
        firstNode = new chainNode<T>(theElement, firstNode);
    else {
        // 寻找新元素的前驱结点
        chainNode<T> *p = firstNode;
        for (int i = 0; i < theIndex - 1; ++i)
            p = p->next;
        // 在p之后插入
        p->next = new chainNode<T>(theElement, p->next);
    }
    ++listSize;
}

template<class T>
void chainList<T>::output(ostream &out) const {
    // 把链表放入输出流
    for (auto *currentNode = firstNode; currentNode != nullptr; currentNode = currentNode->next)
        out << currentNode->element;
}

// 重载
template<class T>
ostream &operator<<(ostream &out, const chainList<T> &x) {
    x.output(out);
    return out;
}

#include"chainList.cpp"

// 用链表保存一个班级学生的清单
// 节点的数据域有：学生姓名，分数
// 假设分数是0~100的整数
struct studentRecord {
    string name;
    int score;

    explicit operator int() const { return score; }

    int operator!=(const studentRecord &x) const { return score != x.score; }
};

ostream &operator<<(ostream &out, const studentRecord &x) {
    out << x.name << ": " << x.score << endl;
    return out;
}

// 使用链表的多个方法进行箱排序
void binSort(chainList<studentRecord> &theChain, int range) {
    // 按分数排序
    chainList<studentRecord> *bin; // 声明箱子
    bin = new chainList<studentRecord>[range + 1]; // 总共有range+1个箱子

    // 把学生记录从链表中取出，然后分配到箱子中
    int numberOfElements = theChain.size(); // 记录链表中元素数量
    for (int i = 0; i < numberOfElements; ++i) {
        studentRecord x = theChain.get(0); // 得到链表中第一个结点
        theChain.erase(0); // 将该节点从链表中删除
        bin[x.score].insert(0, x); // 将该节点数据连接到对应分数的箱子里
    }
    // 从箱子中收集元素
    for (int j = range; j >= 0; --j) {
        while (!bin[j].empty()) { // 如果第j个箱子中的元素不为0
            studentRecord x = bin[j].get(0); // 拿出第j个箱子中的第一个元素
            bin[j].erase(0); // 然后从箱子中删除该元素
            theChain.insert(0, x); // 将该元素通过头插法加入到链表中
        }
    }
    delete[] bin; // 最后删除箱子
}

int main() {
    auto *studentRecords = new chainList<studentRecord>(10);
    int score;
    string name;
    for (int i = 0; i < 10; ++i) {
        auto *sr = new studentRecord; // 为结点申请空间
        cin >> name >> score;
        sr->score = score; // 为结点赋值
        sr->name = name;
        studentRecords->insert(i, *sr); // 将结点插入链表中
    }
    // 查看输入结果
    cout << *studentRecords << endl;
    // 对链表进行箱排序
    binSort(*studentRecords, 5);
    cout << "排序后结果" << endl;
    cout << *studentRecords << endl;

}

输入

A 2
B 4
C 5
D 4
E 3
F 0
G 4
H 3
I 4
J 4

输出

A: 2
B: 4
C: 5
D: 4
E: 3
F: 0
G: 4
H: 3
I: 4
J: 4

排序后结果
F: 0
A: 2
E: 3
H: 3
B: 4
D: 4
G: 4
I: 4
J: 4
C: 5

这篇关于箱排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

箱排序

箱排序

链表定义

结点定义

箱排序方法定义

全部代码

输入

输出

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯