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

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

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

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

#include #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     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 array[j]) : (array[min] < array[j]))                {                    min = j;                }            }            if( min != i )            {                Swap(array[i], array[min]);            }        }    }};}#endif // SORT_H

测试代码如下

#include #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=0) && (min2max ? (array[j]>e) : (array[j]
我们来看看使用 Insert 排序方法是否和之前使用 Select 排序方法实现的效果是一样的，结果如下（还是加上 false 参数）
我们看到效果是完全一样的。那么根据上面的方法可知，在进行插入排序时，数据元素的相对顺序不需要改动，因此插入排序是稳定排序。通过对选择排序和插入排序的学习，总结如下：1、排序是数据元素从无序到有序的过程；2、排序具有稳定性，是选择排序算法的因素之一；3、比较和交换是排序的基本操作，多关键字排序与单关键字排序无本质区别；4、排序的时间性能是区分排序算法好坏的主要因素；5、选择排序每次选择未排元素中的最小元素，插入排序每次将第 i 个元素插入前面 i-1 个已排元素中；6、选择排序是不稳定的排序法，插入排序是稳定的排序方法；7、选择排序和插入排序的时间复杂度为 O(n2)。