成都创新互联网站制作重庆分公司

数据结构(11)_排序

1.排序的基本概念

1.1.排序的概念

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

创新互联建站专注为客户提供全方位的互联网综合服务，包含不限于做网站、成都网站制作、竹溪网络推广、小程序定制开发、竹溪网络营销、竹溪企业策划、竹溪品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联建站为所有大学生创业者提供竹溪建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com

1.2.排序的稳定性

数据结构(11)_排序
问题：什么按照总评排序后张无忌的排名比郭靖靠前呢？
排序的稳定性：
如果序列中有两个数据元素Ri和Rj,他们关键字的Ki == Kj，且排序之前，对象Ri排在Rj之前，但排序之后两者的顺序交互，则称这个排序方案是不稳定的。

1.3.多关键字排序

排序时需要比较的关键字有多个，排序结果首先按照关键字1进行，当关键字1相同，按照关键字2进行排序...
数据结构(11)_排序
多关键字的排序并不比单关键字复杂，只需要在定义比较操作时，同时考虑多个关键字即可!
多关键字排序实例：

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=(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;
}

1.4.排序的选择

排序中的关键操作

  • 比较：任意两个数据元素通过比较操作确定先后次序。
  • 交换：数据元素之间需要交换才能得到预期的结果。
    排序的选择依据：
  • 时间性能，关键性能差异体现在比较和交换的数量
  • 辅助存储空间：完成排序操作需要额外的存储空间，必要时可以“空间换时间”

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

    1.5.排序类的设计

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

    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;
}
}；

    2.常用排序算法

    2.1.选择排序

    基本思想：每次（例如第i次，i=0，1，2...,n-2）从后面n-1个待排列的的数据元素中选出关键字最新的元素，左右有序元素序列的i个元素。
    数据结构(11)_排序
    数据结构(11)_排序
    数据结构(11)_排序

    template < typename T >
static void SelectSort(T array[], int len, bool min2max = true)
{
    for(int i=0; iarray[min])
            {
                min = j;
            }
        }

        if(i != min)
        {
            Swap(array[i], array[min]);
        }
    }
}

  • 选择排序每次选择未排序的最小元素，插入排序每次将第i个元素插入前面i-1个已经排序的序列；

    2.2.插入排序

    当插入第i(i>=1)个数据元素时，前面的V[0],V[1],...,V[i-1]已经排好序，这时用V[i]的关键字与前i-1个关键字进行比较，找到位置后将V[i]插入，原来位置上的对象向后顺移。
    数据结构(11)_排序
    数据结构(11)_排序
    数据结构(11)_排序

    template < typename T >
static void InsertSort(T array[], int len, bool min2max = true)
{
    for(int i=1; i=0) && (min2max ? array[j]>e : array[j]

  • 选择排序是不稳定的排序法，插入排序时稳定的排序法。两者的时间复杂度都为O(n^2)

    2.3.冒泡排序

    基本思想：每次从后向前进行（假设为第i次），j=n-1, n-2, ...i, 两两比较V[j-1]和V[j]的关键字；如果发生逆序，则交换V[j-1]和V[j]。
    数据结构(11)_排序
    数据结构(11)_排序
    数据结构(11)_排序

    template < typename T >
static void BubbleSort(T array[], int len, bool min2max = true)  // 稳定， O(n^2)
{
    bool exchange = true;

    for(int i=0; (ii; j--)
        {
            if(min2max ? array[j] < array[j-1] : array[j] > array[j-1])
            {
                Swap(array[j], array[j-1]);
                exchange = true;
            }
        }
    }
}

  • 冒泡排序每次从后向前将较小的元素交换到位，是一种稳定的排序方法，其负责度为O(n^2);

    2.4.希尔排序

    基本思想：将待排序划分为若干组，在每一组进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排序。
    例如:将n个数据元素分成d个子序列：
    数据结构(11)_排序
    其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。
    数据结构(11)_排序
    数据结构(11)_排序
    数据结构(11)_排序

    template < typename T >
static void ShellSort(T array[], int len, bool min2max = true) // 不稳定， O(n^2/3)
{
    int d = len;
    do
    {
        d = d / 3 +1;
        cout << "d = " << d << endl;
        for(int i=d; i=0) && (min2max ? (array[j]>e) : (array[j]1);

}

  • 希尔排序通过分组的方式进行多次插入排序，是一种不稳定的排序法，复杂度为O(n^2/3)。

    2.5. 归并排序

    基本思想：将两个或者两个以上的有序序列合并成一个新的有序序列。
    数据结构(11)_排序
    这种方法称为二路归并。同理，将N个有序序列归并未一个新有序序列称为N路归并。
    数据结构(11)_排序
    数据结构(11)_排序

    template 
static void Merge(T src[], T helper[], int begin, int mid, int end, bool min2max)
{
    int i = begin;
    int j = mid + 1;
    int k = begin;  //辅助空间的起始位置

    while( (i<=mid) && (j<=end) )
    {
        if(min2max ? src[i]src[j])
        {
            helper[k++] = src[i++];
        }
        else
        {
            helper[k++] = src[j++];
        }
    }

    while(i <= mid) // 左路数据有剩余，直接合并入最终序列
    {
        helper[k++] = src[i++];
    }

    while(j <= end) // ...
    {
        helper[k++] = src[j++];
    }

    for(int i=begin; i<=end; i++)
    {
        src[i] = helper[i];     // 将数据拷贝回原来空间
    }
}
template 
static void Merge(T src[], T helper[], int begin, int end, bool min2max)
{
    if(begin < end) //递归出口
    {
        int mid = (begin + end) / 2;
        // 左路数据合并
        Merge(src, helper, begin, mid, min2max);
        // 右路数据合并
        Merge(src, helper, mid+1, end, min2max);
        // 二路归并
        Merge(src, helper, begin, mid, end, min2max);
    }
}
template < typename T >
static void MergeSort(T array[], int len, bool min2max = true)
{
    // 申请辅助堆空间
    T* helper = new T[len];
    cout << "help: " << helper <
  • 归并排序需要额外的辅助空间才能完成，空间复杂度为O(n)，时间复杂度为O（n*logn），是一种稳定的排序法；

    2.6.快速排序

    基本思想：
    任取序列中的某个数据元素作为基准将整个序列划分为左右两个子序列。

  • 左侧子序列中所有数据元素都小于或等于基本元素；
  • 右侧子序列中所有数据元素都大于基准数据元素；

  • 基准元素排列在这两个子序列中间；
    分别对这两个子序列重复进行划分，直到所有的数据元素都排在相应的位置上为止。
    数据结构(11)_排序
    数据结构(11)_排序

    template 
static int Partion(T array[], int begin, int end, bool min2max)
{
    T pv = array[begin];

    while(begin < end)
    {
        while( (beginpv) : (array[end]=pv)) )
        {
            begin++;
        }
        Swap(array[begin], array[end]);
    }

    return begin;
}
template 
static void Quick(T src[], int begin, int end, bool min2max)
{
    if(begin < end) //递归出口
    {
        //对序列进行区域划分,返回基准元素的位置
        int pivot = Partion(src, begin, end, min2max);
        //对基准左侧的数据元素进行排序
        Quick(src, begin, pivot-1, min2max);
        //对基准右侧的数据元素进行排序
        Quick(src, pivot+1, end, min2max);
    }
}
template < typename T >
static void QuickSort(T array[], int len, bool min2max = true)
{
    Quick(array, 0, len-1, min2max);
}
  • 快速排序通过递归的方式对排序问题进行划分，时间复杂度为O（n*logn），是一种不稳定的排序法。

    3.排序的工程应用

    3.1.排序类功能扩展

    在前面的章节中，我们实现了自己的数组类，排序类DTSrot和数组类Array之间存在什么关系？
    数据结构(11)_排序
    排序类的实现，不单要考虑对元素数据的排序，也应该支持自定义数据的排序。
    新增成员函数：

  • 数组中类中需要提供一个返回元素数据的成员函数函数；

  • 排序类中增加可以实现数组类的成员函数(应该作为之前原生数组排序类的重载版本)；
    数据结构(11)_排序

    //使排序算法支持自定义数组类的排序
template < typename T >
static void SelectSort(Array& array, bool min2max = true)
{
    SelectSort(array.array(), array.length(), min2max);
}

template < typename T >
static void InsertSort(Array& array, bool min2max = true)
{
    InsertSort(array.array(), array.length(), min2max);
}

template < typename T >
static void BubbleSort(Array& array, bool min2max = true)
{
    BubbleSort(array.array(), array.length(), min2max);
}

template < typename T >
static void ShellSort(Array& array, bool min2max = true)
{
    ShellSort(array.array(), array.length(), min2max);
}

template < typename T >
static void MergeSort(Array& array, bool min2max = true)
{
    MergeSort(array.array(), array.length(), min2max);
}

template < typename T >
static void QuickSort(Array& array, bool min2max = true)
{
    QuickSort(array.array(), array.length(), min2max);
}

    3.2.代理模式

    问题：当待排序数据元素为体积庞大的对象时，如何提高排序效率？
    譬如对下面的对象使用冒泡排序算法进行排序，必然涉及大量的数据交换，严重影响效率。
    数据结构(11)_排序
    问题分析：
    1.排序过程中不可避免的要进行交换操作，交换操作的本质为数据元素的复制，当数据元素体积较大时，交换操作耗时巨大。
    代理模式：
    1.为待排序数据元素设置代理对象；
    2.对代理对象所组成的序列进行排序
    3.需要访问有序数据元素时，通过访问代理序列完成。
    艰苦奋斗酸辣粉

数据结构(11)_排序
数据结构(11)_排序

struct Test :public Object
{
    int id;
    int data1[1000];
    double data2[500];

    bool operator < (const Test& obj)
    {
        return id < obj.id;
    }

    bool operator <= (const Test& obj)
    {
        return id <= obj.id;
    }

    bool operator >= (const Test& obj)
    {
        return id >= obj.id;
    }

    bool operator > (const Test& obj)
    {
        return id > obj.id;
    }
};

class TestProxy : public Object
{
protected:
    Test* pTest;
public:
    int id()const
    {
        return pTest->id;
    }

    int* data1()const
    {
        return pTest->data1;
    }

    double* data2()const
    {
        return pTest->data2;
    }

    Test& test()const
    {
        return *pTest;
    }

    bool operator >(const TestProxy& obj)
    {
        return test() > obj.test();
    }

    bool operator >=(const TestProxy& obj)
    {
        return test() >= obj.test();
    }

    bool operator <(const TestProxy& obj)
    {
        return test() < obj.test();
    }

    bool operator <=(const TestProxy& obj)
    {
        return test() <= obj.test();
    }

    Test& operator =(Test& test)
    {
        pTest = &test;
        return test;
    }
};

Test t[1000];
TestProxy pt[1000];

void test_3()
{
    clock_t begin = 0;
    clock_t end = 0;

    for(int i=0;i<1000;i++)
    {
        t[i].id = i;
        pt[i] = t[i];
    }

    begin = clock();

    //DTSort::BubbleSort(t,1000,false);
    DTSort::BubbleSort(pt,1000,false);

    end = clock();

    cout << "Time:" << (end - begin) << endl;
    for(int i=0;i<1000;i++)
    {
        //cout << t[i].id << " " << pt[i].id() << endl;
    }

}

使用代理模式：
数据结构(11)_排序
不使用代理模式：
数据结构(11)_排序
两者时间相差超过50倍，可见代码模式的优势。
总结：
1.排序类应当同时支持原生数组和数组类的的排序；
2.当排序元素为体积庞大的对象时，可以考虑使用代理模式简介完成（有效避开大对象交换时的耗时操作），是空间换时间思想的体现。


文章名称：数据结构(11)_排序
当前URL：http://cxhlcq.com/article/pecjgh.html

其他资讯

全国免费咨询:

400-028-6601

业务咨询：028-86922220 / 13518219792

节假值班：18980820575 / 13518219792

联系地址：成都市太升南路288号锦天国际A幢1002号

Copyright © 成都创新互联科技有限公司重庆分公司 渝ICP备2021005571号
友情链接:： 成都网站建设 重庆网站建设 四川网站建设 重庆建设网站 移动服务器托管 成都服务器托管 云服务器 广告设计制作 重庆网页设计 重庆做网站 重庆网站制作 重庆网站建设 重庆网站公司 渝中网站制作 重庆网站设计

在线咨询

微信咨询

电话咨询

028-86922220（工作日）

18980820575（7×24）

提交需求

返回顶部