今天我们来看下排序，那么什么是排序呢？排序是计算机内部经常进行的一种操作，其目的是将一组“无序”的数据元素调整为“有序”的数据元素。那么排序的数学定义时什么呢？如下
下来我们来看一个概念：排序的稳定性。什么是排序的稳定性呢？它是指如果在序列中有两个数据元素 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(n2)。