选择和插入都是比较简单的排序算法.两种算法都是通过将最小值前移的方式进行排序的.不同的是插入排序是取i值和i前面的数据做逐一比较,将最小值放在最前端,而选择排序是将i后面的最小值和i位置进行交换.

下面具体说一下两种算法的区别

选择排序

其排序流程如下：

1. 首先从原始数组中选择最小的一个数据，将其和位于第一个位置的数据进行交换。
2. 接着从剩下的 n-1 个数据中选择次小的一个元素，将其和第二个位置的数据交换。
3. 然后，这样不断重复，直到最后连个数据完成交换。至此，便完成对原始数组的从小到大的排序。

我举一个实际数据的例子来一步步的执行选择排序算法。对于5个整型数据 118、101、105、127、112，这是一组无序的数据。对其执行的选择排序过程，如下图所示，选择排序算法的执行步骤如下：

1. 第一次排序，从原始数组中选择最小的数据，这个数据便是101，将其与第一个数据118进行交换。此时排序后的数据为 101、118、105、127、112。
2. 第二次排序，从剩余的数组中选择最小的数据，这个数据是105，将其与第二个数据118进行交换。此时排序后的数据为101、105、118、127、112。
3. 第三次排序，将剩余的数据中选择最小的数据，这个数据是112，将其与第三个数据118进行交换。此时排序后的数据为101、105、112、127、118。
4. 第四次排序，将剩余的数组中选择最小的数据，这个数据为118，将其与第四次数据127进行交换。此时排序后的数据为101、105、112、118、127。

从上面的例子，可以非常直观的了解到选择排序算法的执行过程。选择排序算法在对N个数据进行排序时，无论原始数据有无顺序，都需要进行 N-1 步的中间排序。这种排序方法思路很简单直观，但是缺点就是执行的步骤有点长，效率也不是很高。

在这里，输入参数datas一般为一个数组的首地址。待排序的原数据便保存在数组datas中，程序中通过两层循环来对数据进行选择排序。为了更清楚的看到算法执行过程，在排序的每一步输出了当前排序结果。

插入排序

首先来解释一下插入排序法的原理，它的原理是每插入一个数都要将它和之前的已经完成排序的序列进行重新排序，也就是要找到新插入的数对应原序列中的位置。那么也就是说，每次插入一个数都要对原来排序好的那部分序列进行重新的排序，时间复杂度同样为O(n²)。 这种算法是稳定的排序方法。

此算法有两种基本的操作：

①比较操作；

②交换操作

其中，对于交换操作，可以优化成移动操作，即不直接进行两个元素的交换，还是用一个枢轴元素(tmp)将当前元素先保存起来，然后执行移动操作，待确定了最终位置后，再将当前元素放入合适的位置。(下面的插入排序就用到了这个技巧)--因为，交换操作需要三次赋值，而移动操作只需要一次赋值！

递归思想

插入排序算法有种递归的思想在里面，它由N-1趟排序组成。初始时，只考虑数组下标0处的元素，只有一个元素，显然是有序的。

1. 第一趟 对下标 1 处的元素进行排序，保证数组[0,1]上的元素有序；
2. 第二趟 对下标 2 处的元素进行排序，保证数组[0,2]上的元素有序；
3. .....
4. .....

第N-1趟对下标 N-1 处的元素进行排序，保证数组[0,N-1]上的元素有序，也就是整个数组有序了。

它的递归思想就体现在：当对位置 i 处的元素进行排序时，[0,i-1]上的元素一定是已经有序的了。

排序前: 6 3 3 5 6 3 1 0 6 4

i = 0: 6

i = 1: 3 6

i = 2: 3 3 6

i = 3: 3 3 5 6

i = 4: 3 3 5 6 6

i = 5: 3 3 3 5 6 6

i = 6: 1 3 3 3 5 6 6

i = 7: 0 1 3 3 3 5 6 6

i = 8: 0 1 3 3 3 5 6 6 6

i = 9: 0 1 3 3 3 4 5 6 6 6

排序后: 0 1 3 3 3 4 5 6 6 6

插入排序算法实现