---

一、排序的基本概念

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

 2.排序数学定义：假设含 n 个数据元素序列为{R1, R2, ..., Rn}， 其相应的关键字序列为 {K1, K2, ..., Kn}，这 些关键字相互之间可以进行比较，即：在它们之间存在着这样一个关系 Kp1 ，按此固有关系将上式记录序列重新排列为 {Rp1, Rp2, ..., Rpn}的操作称为排序。

 3.排序的稳定性：如果在序列中有两个数据元素 r[i] 和 r[j]，它们的关键字 k[i] == k[j]，且在排序之前，对 象 r[i] 排在 r[j] 前面；如果在排序之后，对象 r[i] 仍在对象 r[j] 的前面，则称这个排序方法 是稳定的，否则称这个排序方法是不稳定的；

 4.排序的关键操作：比较（任意两个数据元素通过比较操作确定先后次序；） 交换（数据元素之间需要交换才能得到预期效果（无序变有序）；）

 5.排序算法的选择：

  （1）时间性能：关键性能差异体现在比较和交换的数量；

  （2）辅助存储空间：为完成排序操作需要的额外的存储空间：嵌入式开发，空间资源受限；必 要时可以“空间换时间”； 

  （3）算法的实现复杂性：过于复杂的排序法可能影响可读性和可维护性；

排序是数据元素从无序到有序的过程；排序具有稳定性，是选择排序算法的（主要）因素之一；比较和交换是排序的基本操作；排序的时间性能是区分排序算法好坏的主要因素；

二、插入排序

 1.直接插入排序

  （1）插入排序：：每一步将一个待排序的元素，按其排序码的大小，插入到前面已 经排好序的一组元素的适当位置上去，直到元素全部插入为止。

  （2）基本思想：：每一步将一个待排序的元素，按其排序码的大小，插入到前面已 经排好序的一组元素的适当位置上去，直到元素全部插入为止。

#include<stdio.h>
template<class...