直接插入排序
插入排序的基本方法是：每一步都将待排序的元素，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。
直接插入排序基本思想：将一个元素插入到已排好序的序列中，从而得到一个新的有序序列（将序列的第一个数据看成是一个有序的子序列，然后从第二个记录逐个向该有序的子序列进行有序的插入，直至整个序列有序）
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。
代码
for(i
=0;i
<n
;i
++)
{
if(s
[i
]<s
[i
-1])
{
temp
= s
[i
];
j
= i
-1;
while(j
>=0 && s
[j
]>temp
)
{
s
[j
+1]=s
[j
];
j
--;
}
s
[j
+1] = temp
;
}
}
复杂的分析
时间复杂度：O(n^) 空间复杂度：O(1)
改进冒泡排序
如果已经是有序的数列，就不要再进行排序，及时终止，进入下一次排序，可以提高冒泡排序的时间复杂度用两个循环嵌套进行两两比较，用一个false标记无序，进入一层循环，若标记为true，则表示有序，不用进行比较
代码
bool flag
= false;
for(i
=0;(i
<n
) && (flag
== false);i
++)
{
flag
= true;
for(j
=n
-1;j
>i
;j
--)
{
if(s
[j
] < s
[j
-1])
{
temp
= s
[j
];
s
[j
] = s
[j
-1];
s
[j
-1] = temp
;
flag
= false;
}
}
}
复杂的分析
时间复杂度：最差O(n^2) 最好O(n) 空间复杂度：O(1)
