数据结构实战开发教程（八）选择排序和插入排序、冒泡排序和希尔排序、归并排序和快速排序、排序的工程应用示例

四十六、排序的基本概念

1、排序的一般定义

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

2、排序的数学定义

        

3、排序的示例

        

4、问题

按总评排序后为什么张无忌的排名比郭靖靠前呢？

因为采用的不稳定排序法。

5、排序的稳定性

        

6、稳定性排序示例

7、多关键字排序

• 排序时需要比较的关键字多余一个
  • 排序结果首先按关键字1进行排序
  • 当关键字1相同时按关键字2进行排序
  • ……..
  • 当关键字n-1相同时按关键字n进行排序

8、多关键字排序示例

9、问题

多关键字排序是否比单关键字排序更复杂？

对于多关键字排序，只需要在比较操作时同时考虑多个关键字即可！！！

10、编程实验：多关键字比较操作

        代码在最后，整合在一起。

11、排序中的关键操作

• 比较
  • 任意两个数据元素通过比较操作确定先后次序
• 交换
  • 数据元素之间需要交换才能得到预期结果

12、排序的审判

• 时间性能
  • 关键性能差异体现在比较和交换的数量
• 辅助存储空间
  • 为完成排序操作需要的额外的存储空间
  • 必要时可以“空间换时间”
• 算法的实现复杂性
  • 过于复杂的排序法可能影响可读性和可维护性

13、DTLib 中的排序类设计

14、编程实验：DTLib中的排序类

代码在最后，整合在一起。

15、小结

• 排序是数据元素从无序到有序的过程
• 排序具有稳定性，是选择排序算法的因素之一
• 比较和交换是排序的基本操作
• 多关键字排序与单关键字排序无本质区别
• 排序的时间性能是区分排序算法好坏的主要因素

四十七、选择排序和插入排序

1、选择排序的基本思想

每次（例如第i次，i = 0，1,..., n-2）从后面n-i个待排的数据元素中选出关键字最小的元素，作为有序元素序列第i个元素。

2、第i次选择排序示例

3、编程实验：选择排序的实现Sort:Select

        代码在最后，整合在一起。

4、插入排序的基本思想

当插入第i(i≥ 1)个数据元素时，前面的V[0]，V[1] ,V[i-1]已经排好序;这时，用Vi]的关键字与V[i-1] ，Vii-2]，...，V[O]的关键字进行比较，

找到位置后将V[ü]插入，原来位置上的对象向后顺移。

5、第i次插入排序示例

6、编程实验：插入排序的实现

Sort:Insert

代码在最后，整合在一起。

7、小结

• 选择排序每次选择未排元素中的最小元素
• 插入排序每次将第i个元素插入前面i-1个已排元素中
• 选择排序是不稳定的排序法，插入排序是稳定的排序方法
• 选择排序和插入排序的时间复杂度为O(n^2)

四十八、冒泡排序和希尔排序

1、冒泡排序的基本思想

每次从后向前进行（假设为第i次）,j = n-1, n-2, ...， i ,两两比较Vlj-1]和V[j]的关键字﹔如果发生逆序，则交换vlj-1]和Vlj]。

2、第i次冒泡排序示例

3、编程实验：冒泡排序的实现

Sort::Bubble

代码在最后，整合在一起。

4、希尔排序的基本思想

将待排序列划分为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排序。

5、希尔排序示例

6、编程实验：希尔排序的实现

Sort::Shell

代码在最后，整合在一起。

7、小结

• 冒泡排序每次从后向前将较小的元素交互到位
• 冒泡排序是一种稳定的排序法，其复杂度为O(n^2)
• 希尔排序通过分组的方式进行多次插入排序
• 希尔排序是一种不稳定的排序法，其复杂度为O(n^(3/2))

四十九、归并排序和快速排序

1、归并排序的基本思想

将两个或两个以上的有序序列合并成一个新的有序序列

2、归并的套路

• 将3个有序序列归并为一个新的有序序列，称为3路归并
• 将N个有序序列归并为一个新的有序序列，称为N路归并
• 将多个有序序列归并为一个新的有序序列，称为多路归并

3、2路归并示例

4、归并排序的代码实现

5、编程实验：归并排序的实现

Sort::Merge

代码在最后，整合在一起。

6、快速排序的基本思想

• 任取序列中的某个数据元素作为基准将整个序列划分为左右两个子序列
  • 左侧子序列中所有元素都小于或等于基准元素
  • 右侧子序列中所有元素都大于基准元素
  • 基准元素排在这两个子序列中间
• 分别对这两个子序列重复进行划分，直到所有的数据元素都排在相应位置上为止

7、快速排序示例

8、编程实验：快速排序的实现

Sort::Quick

代码在最后，整合在一起。

9、小结

• 归并排序需要额外的辅助空间才能完成，空间复杂度为O(n)
• 归并排序的时间复杂度为O(n*logn)，是—种稳定的排序法
• 快速排序通过递归的方式对排序问题进行划分
• 快速排序的时间复杂度为O(n*logn)，是一种不稳定的排序法

五十、排序的工程应用示例

1、排序类(Sort)与数组类(Array)的关系

2、新增的成员函数

3、编程实验：排序类与数组类的关系

Array.h

Sort.h

代码在最后，整合在一起。

4、问题

当待排数据元素为体积庞大的对象时，如何提高排序的效率？

5、问题示例

6、问题分析

• 排序过程中不可避免的需要进行交换操作
• 交换操作的本质为数据元素间的相互复制
• 当数据元素体积较大时，交换操作耗时巨大

7、解决方案：代理模式

1. 为待排数据元素设置代理对象
2. 对代理对象所组成的序列进行排序
3. 需要访问有序数据元素时，通过访问代理序列完成

8、真的能够提高排序效率吗？

9、编程实验：解决方案

Proxy Pattern

10、小结

• DTLib中的排序类和数组类之间存在关联关系
• 排序类能够对数组类对象进行排序
• 当排序体积庞大的对象时，使用代理模式间接完成
• 代理模式的使用有效避开大对象交换时的耗时操作
• 代理模式解决方案是空间换时间思想的体现

#ifndef SORT_H
#define SORT_H

#include "Object.h"
#include "Array.h"

namespace DTLib
{

class Sort : public Object
{
private:
    Sort();
    Sort(const Sort&);
    Sort& operator = (const Sort&);

    template < typename T >
    static void Swap(T& a, T& b)
    {
        T c(a);
        a = b;
        b = c;
    }

    template < typename T >
    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]) : (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(i=begin; i<=end; i++)
        {
            src[i] = helper[i];
        }
    }

    template < typename T >
    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 int Partition(T array[], int begin, int end, bool min2max)
    {
        T pv = array[begin];

        while( begin < end )
        {
            while( (begin < end) && (min2max ? (array[end] > pv) : (array[end] < pv)) )
            {
                end--;
            }

            Swap(array[begin], array[end]);

            while( (begin < end) && (min2max ? (array[begin] <= pv) : (array[begin] >= pv)) )
            {
                begin++;
            }

            Swap(array[begin], array[end]);
        }

        array[begin] = pv;

        return begin;
    }

    template < typename T >
    static void Quick(T array[], int begin, int end, bool min2max)
    {
        if( begin < end )
        {
            int pivot = Partition(array, begin, end, min2max);

            Quick(array, begin, pivot-1, min2max);
            Quick(array, pivot+1, end, min2max);
        }
    }

public:
    // 选择排序
    template < typename T >
    static void Select(T array[], int len, bool min2max = true)
    {
        for(int i=0; i<len; i++)
        {
            int min = i;

            for(int j=i+1; j<len; j++)
            {
                if( min2max ? (array[min] > array[j]) : (array[min] < array[j]) )
                {
                    min = j;
                }
            }

            if( min != i )// 如果当前位置的值是若干最小值中的一个，就不再进行交换了。
            {
                Swap(array[i], array[min]);
            }
        }
    }
// 插入排序
    template < typename T >
    static void Insert(T array[], int len, bool min2max = true)
    {
        for(int i=1; i<len; i++)
        {
            int k = i;
            T e = array[i];

            for(int j=i-1; (j>=0) && (min2max ? (array[j]>e) : (array[j]<e)); j--)
            {
                array[j+1] = array[j];
                k = j;
            }

            if( k != i )
            {
                array[k] = e; // 插入位置
            }
        }
    }
// 冒泡排序
    template < typename T >
    static void Bubble(T array[], int len, bool min2max = true)
    {
        bool exchange = true;

        for(int i=0; (i<len) && exchange; i++)
        {
            exchange = false;

            for(int j=len-1; j>i; j--)
            {
                if( min2max ? (array[j] < array[j-1]) : (array[j] > array[j-1]) )
                {
                    Swap(array[j], array[j-1]);
                    exchange = true;
                }
            }
        }
    }
// 希尔排序
    template < typename T >
    static void Shell(T array[], int len, bool min2max = true)
    {
        int d = len;

        do
        {
            d = d / 3 + 1; // 大量的理论实践证明，此方法效率最高

            for(int i=d; i<len; i+=d)
            {
                int k = i;
                T e = array[i];

                for(int j=i-d; (j>=0) && (min2max ? (array[j]>e) : (array[j]<e)); j-=d)
                {
                    array[j+d] = array[j];
                    k = j;
                }

                if( k != i )
                {
                    array[k] = e;
                }
            }

        } while( d > 1 );
    }

    template < typename T >
    static void Merge(T array[], int len, bool min2max = true)
    {
        T* helper = new T[len];

        if( helper != NULL )
        {
            Merge(array, helper, 0, len-1, min2max);
        }

        delete[] helper;
    }

    template < typename T >
    static void Quick(T array[], int len, bool min2max = true)
    {
        Quick(array, 0, len-1, min2max);
    }

    template < typename T >
    static void Heap(T array[], int len, bool min2max = true)
    {
        DynamicHeap<T> heap(len, !min2max);

        for(int i=0; i<len; i++)
        {
            heap.add(array[i]);
        }

        for(int i=0; i<len; i++)
        {
            array[i] = heap.front();

            heap.remove();
        }
    }

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

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

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

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

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

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

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

}

#endif // SORT_H