排序的概念

定义：排序是计算机内经常进行的一种操作，其目的是将一组“无序”的数据调整为“有序”的数据元素。

数据定义：假设含有n个数据元素的序列为{R1,R2…Rn},其相应的关键字序列为：{K1,K2…Kn};这些关键字相互之间进行比较，即：在他们之间存在着这样的一个关系：Kp1 <= Kp2 <= … <= Kpn按此固有关系将上式重新排列为：{Rp1, Rp2, … Rpn}的操作称为排序。

排序的稳定性

问题：什么按照总评排序后张无忌的排名比郭靖靠前呢?

排序的稳定性：

如果序列中有两个数据元素Ri和Rj,他们关键字的Ki == Kj，且排序之前，对象Ri排在Rj之前，但排序之后两者的顺序交互，则称这个排序方案是不稳定的。

多关键字排序

排序时需要比较的关键字有多个，排序结果首先按照关键字1进行，当关键字1相同，按照关键字2进行排序…

多关键字的排序并不比单关键字复杂，只需要在定义比较操作时，同时考虑多个关键字即可!

多关键字排序实例：

class MulitKeySort : public Object
{
protected:
    int key1;
    int key2;
public:
    MulitKeySort(int k1, int k2)
    {
        key1 = k1;
        key2 = k2;
    }
    bool operator ==(const MulitKeySort& m)
    {
        return ( (key1==m.key1) && (key2==m.key2));
    }
    bool operator !=(const MulitKeySort& m)
    {
        return !(*this == m);
    }
    bool operator <(const MulitKeySort& m)
    {
        return ( (key1<m.key1) || ((key1==m.key1) && (key2<m.key2)));
    }
    bool operator >=(const MulitKeySort& m)
    {
        return !(*this < m);
    }
    bool operator >(const MulitKeySort& m)
    {
        return ( (key1>m.key1) || ((key1==m.key1) && (key2>m.key2)));
    }
    bool operator <=(const MulitKeySort& m)
    {
        return !(*this > m);
    }
};
//测试代码：
void test_1()
{
    MulitKeySort m1(3, 4);
    MulitKeySort m2(3, 3);
    cout << (m1 > m2) << endl;
}

排序的选择

** 排序中的关键操作**

比较：任意两个数据元素通过比较操作确定先后次序。

交换：数据元素之间需要交换才能得到预期的结果。

排序的选择依据：

时间性能，关键性能差异体现在比较和交换的数量

辅助存储空间：完成排序操作需要额外的存储空间，必要时可以“空间换时间”

算法的实现复杂度：过于复杂的排序算法可能影响可读性和可维护性。

排序类的设计

继承自顶层父类Object，并且私有化所有构造途径，将各种排序算法设计为静态成员函数。

class DTSort : public Object
{
private:
    DTSort();
    DTSort(const DTSort&);
    DTSort& operator =(const DTSort&);
    template < typename T >
    static void Swap(T& a, T& b)
    {
        T c(a);
        a = b;
        b = c;
    }
}；

动力节点在线课程涵盖零基础入门，高级进阶，在职提升三大主力内容，覆盖Java从入门到就业提升的全体系学习内容。全部Java视频教程免费观看，相关学习资料免费下载!对于火爆技术，每周一定时更新!如果想了解更多相关技术，可以到动力节点在线免费观看数据结构视频教程哦!