数据结构(11)_排序

1.排序的基本概念

1.1.排序的概念

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

1.2.排序的稳定性

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

1.3.多关键字排序

排序时需要比较的关键字有多个，排序结果首先按照关键字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=(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，并且私有化所有构造途径，将各种排序算法设计为静态成员函数。
  

  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个元素。
  
  
  

  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]插入，原来位置上的对象向后顺移。
  
  
  

  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]。




  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个子序列：

其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。




  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. 归并排序

  基本思想：将两个或者两个以上的有序序列合并成一个新的有序序列。

这种方法称为二路归并。同理，将N个有序序列归并未一个新有序序列称为N路归并。



  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.快速排序

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

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

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



  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之间存在什么关系？
  
  排序类的实现，不单要考虑对元素数据的排序，也应该支持自定义数据的排序。
  新增成员函数：

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

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


  //使排序算法支持自定义数组类的排序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.代理模式

  问题：当待排序数据元素为体积庞大的对象时，如何提高排序效率？
譬如对下面的对象使用冒泡排序算法进行排序，必然涉及大量的数据交换，严重影响效率。

问题分析：
1.排序过程中不可避免的要进行交换操作，交换操作的本质为数据元素的复制，当数据元素体积较大时，交换操作耗时巨大。
代理模式：
1.为待排序数据元素设置代理对象；
2.对代理对象所组成的序列进行排序
3.需要访问有序数据元素时，通过访问代理序列完成。
艰苦奋斗酸辣粉

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

使用代理模式：

不使用代理模式：

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