选择排序和插入排序（三十）

        今天我们来看下排序，那么什么是排序呢？排序是计算机内部经常进行的一种操作，其目的是将一组“无序”的数据元素调整为“有序”的数据元素。那么排序的数学定义时什么呢？如下

        下来我们来看一个概念：排序的稳定性。什么是排序的稳定性呢？它是指如果在序列中有两个数据元素 r_[i] 和 r_[j]，它们的关键字 k_[i]  == k_[j] ，且在排序之前，对象 r_[i] 排在 r_[j] 前面；如果在排序之后，对象 r_[i] 仍在 r_[j] 的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。

        下来我们来看看多关键字排序。这个就是在排序时需要比较的关键字多余一个，那么是什么意思呢？就是当排序结果首先按关键字 1 进行排序，当关键字 1 相同时按关键字 2 进行排序；…；当关键字 n-1 相同时按关键字 n 进行排序。对于多关键字排序，我们只需要在比较操作时同时考虑多个关键字即可。下来我们通过一个示例代码来进行分析

#include <iostream>
#include "Object.h"

using namespace std;
using namespace DTLib;

struct Test : public Object
{
    int key1;
    int key2;

    Test(int k1, int k2)
    {
        key1 = k1;
        key2 = k2;
    }

    bool operator ==(const Test& t)
    {
        return (key1 == t.key1) && (key2 == t.key2);
    }

    bool operator !=(const Test& t)
    {
        return !(*this == t);
    }

    bool operator >(const Test& t)
    {
        return (key1 > t.key1) || ((key1 == t.key1) && (key2 > t.key2));
    }

    bool operator <=(const Test& t)
    {
        return !(*this > t);
    }

    bool operator <(const Test& t)
    {
        return (key1 < t.key1) || ((key1 == t.key1) && (key2 < t.key2));
    }

    bool operator >=(const Test& t)
    {
        return !(*this < t);
    }
};

int main()
{
    Test t1(3, 4);
    Test t2(3, 5);
    
    Test t3(2, 4);
    Test t4(1, 2);

    cout << "t1 < t2 : " << (t1 < t2) << endl;
    cout << "t3 > t4 : " << (t3 > t4) << endl;

    return 0;
}

        下来我们来看看输出结果

        在上面的示例中，我们看到排序中的关键操作：比较和交换。比较是指任意两个数据元素通过比较操作确定先后次序；交换是指数据元素之间需要交换才能得到预期结果。那么我们在进行排序的时候怎么进行判断这个排序是优是劣呢？从下面三个方面来进行判断。1、时间性能：关键性能差异体现在比较和交换的数量；2、辅助存储空间：为完成排序操作所需要额外的存储空间，必要时可以“空间换时间”；3、算法的实现复杂性：过于复杂的排序法可能影响可读性和可维护性。

        下来我们来看看 DTLib 库中的排序类的设计，如下

        我们来基于上面的排序类来进一步实现选择排序和插入排序。

        1、选择排序：它的基本思想是每次（例如第 i 次，i = 0, 1, …, n-2）从后面 n-i 个待排的数据元素中选出关键字最小的元素，作为有序元素序列第 i 个元素。第 i 次选择排序示例如下

        我们来看看具体是怎么实现的，如下所示

        我们看到是从第一个开始，选出最小的数据元素，后面以此类推，直至最后全部排序完毕。下来我们来具体看看源码是怎样实现的

#ifndef SORT_H
#define SORT_H

#include "Object.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;
    }
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]);
            }
        }
    }
};

}

#endif // SORT_H

        测试代码如下

#include <iostream>
#include "Sort.h"

using namespace std;
using namespace DTLib;

int main()
{
    int array[] = {3, 2, 4, 1, 5};

    Sort::Select(array, 5);

    for(int i=0; i<5; i++)
    {
        cout << array[i] << endl;
    }
}

        我们来看看运行结果

        我们在代码中默认是从小到大的进行排序，我们在选择排序时，再输入第三个参数 false，看看它是否是从大到小进行排序的

        通过上面的排序可知，在排完序后，数据元素的位置已经改动。因此，选择排序是不稳定排序。

        2、插入排序：它的基本思想是当插入第 i(i >= 1) 个数据元素时，其那面的 V[0], V[1], …, V[i-1] 已经排好序；这时，用 V[i] 的关键字与 V[i-1]，V[i-2]，…，V[0] 的关键字进行比较，找到位置后将 V[i] 插入，原来位置上的对象向后顺移。第 i 次插入排序示例如下

        我们来看看具体是怎么实现的，如下所示

        最后的结果为

        我们看到它是通过比较来得出具体位置的。那么我们在下面的代码中直接从后向前来进行比较，具体源码如下

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

        我们来看看使用 Insert 排序方法是否和之前使用 Select 排序方法实现的效果是一样的，结果如下（还是加上 false 参数）

        我们看到效果是完全一样的。那么根据上面的方法可知，在进行插入排序时，数据元素的相对顺序不需要改动，因此插入排序是稳定排序。通过对选择排序和插入排序的学习，总结如下：1、排序是数据元素从无序到有序的过程；2、排序具有稳定性，是选择排序算法的因素之一；3、比较和交换是排序的基本操作，多关键字排序与单关键字排序无本质区别；4、排序的时间性能是区分排序算法好坏的主要因素；5、选择排序每次选择未排元素中的最小元素，插入排序每次将第 i 个元素插入前面 i-1 个已排元素中；6、选择排序是不稳定的排序法，插入排序是稳定的排序方法；7、选择排序和插入排序的时间复杂度为 O(n²)。