直接插入排序和直接选择排序
了解了排序的基本概念，接下来我们来谈谈如何实现直接插入排序与直接选择排序。
直接插入排序
直接插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的序列中的适当位置，直到全部记录插入完成为止。
1．基本思路
假设待排序的记录存放在数组 R[1..n]中。初始时，R[1]自成 1 个有序区，无序区为 R[2..n]。从 i=2 起直至 i=n 为止，依次将 R[i] 插入当前的有序区 R[1..i-1] 中，生成含 n 个记录的有序区。
2．第 i-1 趟直接插入排序
通常将一个记录 R[i][i=2，3，…，n-1]插入到当前的有序区，使得插入后仍保证该区间里的记录是按关键字有序的操作称第 i-1 趟直接插入排序。
排序过程的某一中间时刻，R 被划分成两个子区间 R[1．．i-1]（有序区）和 R[i．．n]（无序区）。
直接插入排序的基本操作是将当前无序区的第 1 个记录 R[i]插人到有序区 R[1．．i-1]中适当的位置上，使 R[1．．i]变为新的有序区。
一趟直接插入排序方法
1．简单方法
首先在当前有序区 R[1..i-1]中查找R[i]的正确插入位置 k(1≤k≤i-1)；然后将 R[k．．i-1]中的记录均后移一个位置，腾出 k 位置上的空间插入 R[i]。
注意： 若 R[i]的关键字大于等于 R[1．．i-1]中所有记录的关键字，则 R[i]就是插入原位置。
2．改进的方法
一种查找比较操作和记录移动操作交替地进行的方法。
具体做法：
将待插入记录 R[i]的关键字从右向左依次与有序区中记录 R[j][j=i-1，i-2，…，1]的关键字进行比较：
- 若 R[j]的关键字大于 R[i]的关键字，则将 R[j]后移一个位置；
- 若 R[j]的关键字小于或等于 R[i]的关键字，则查找过程结束，j+1 即为 R[i]的插入位置。
因为从右往左比较操作与移动操作同时进行，关键字比 R[i]的关键字大的记录均已后移，所以 j+1 的位置已经腾空，只要将 R[i] 直接插入此位置即可完成一趟直接插入排序。
直接插入排序算法
1．代码实现
2.运行截图：
3.算法分析
(1)算法的时间性能分析
对于具有 n 个记录的文件，要进行 n-1 趟排序。
如果目标是把n个元素的数列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。
2．算法的空间复杂度分析
算法所需的辅助空间是一个监视哨，辅助空间复杂度 S(n)=O(1)。是一个就地排序。
3．直接插入排序的稳定性
直接插入排序是稳定的排序方法。
动图来源于网上，侵删!
直接选择排序
选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放入已排序数列的最后，直到全部记录排序完毕。常用的选择排序方法有直接选择排序和堆排序。
1.直接选择排序的基本思想
n个记录的数列的直接选择排序可经过n-1趟直接选择排序得到有序结果：
(1)初始状态：无序区为 R[1..n]，有序区为空。
(2)第 1 趟排序：在无序区 R[1..n]中选出关键字最小的记录 R[k]，将它与无序区的第 1 个记录 R[1]交换，使 R[1..i]和 R[2..n]分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。
(3)第 i 趟排序：第i趟排序开始时，当前有序区和无序区分别为 R[1..i-1]和 R[i..n][1≤i≤n-1]。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第 i 个记录 R[i]交换，使 R[1..i]和 R[i+1..n]分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。
这样，n 个记录的数列的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。
2.代码实现：
3.运行截图：
4.算法分析
（1）关键字比较次数
无论数列初始状态怎样，在第 i 趟排序中选出最小关键字的记录，需做 n-i 次比较，因此，总的比较次数为： n(n-1)/2=O(n2)。
（2）时间复杂度
直接选择排序的平均时间复杂度为 O(n2)。
（3）空间复杂度
直接选择排序是一个就地排序，空间复杂度为S(n)=O(1)。
（4）稳定性分析
直接选择排序是不稳定的。
动图来源于网上，侵删!
贴上不同排序算法的性能比较图：
。