动力节点首页 全国咨询热线:400-8080-105

绑定手机号,登录
手机号

验证码

微信登录
手机号登录
手机号

验证码

30天自动登录
微信登录与注册
微信扫码登录与注册

扫码关注微信公众号完成登录与注册
手机号登录
首页 > 文章

数据结构排序的概念

08-03 10:34 333浏览
举报 T字号
  • 大字
  • 中字
  • 小字

排序的概念

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

数据定义:假设含有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视频教程免费观看,相关学习资料免费下载!对于火爆技术,每周一定时更新!如果想了解更多相关技术,可以到动力节点在线免费观看数据结构视频教程哦!

0人推荐
共同学习,写下你的评论
0条评论
代码小兵124
程序员代码小兵124

99篇文章贡献336699字

相关课程 更多>

作者相关文章更多>

推荐相关文章更多>

Java面试题及答案整理

代码小兵66904-21 20:01

6道经典算法面试题

杨晶珍05-12 16:39

简述Spring MVC的核心组件

代码小兵49806-11 16:26

SpringMVC 中的组件

代码小兵49806-11 16:28

Spring常见面试题

代码小兵92504-17 16:07

发评论

举报

0/150

取消