排序1---插入排序

目录

插入排序的基本思路：

插入排序的代码实现：

代码：

代码解读：

插入排序的时间、空间复杂度：

插入排序的基本思路：

插入排序是一个比较简单的排序。 

我们插入排序就是我们先假设前面的一段区间有序，然后从这个区间的后面一个位置开始，将该位置的值定位待插入的值，待插入的值与该区间的值进行比较，如果区间里面的值大于我们的待插入的值，就将这个值往后移一位，再继续比较，一直到我们比较完最后一个值，或者比较到一个比我们待插入值要小的值，这个时候我们就停止我们的比较。在将我们待插入的值插入比待插入值要小的值的后。

插入排序的代码实现：

代码：

void Insersort(int* a, int n)
{
    int end = 0;
    //假设[0,end]之间是有序的
    for (int j = 0; j < n - 1; j++)//为n-1的原因是防止end+1越界
    {
        end = j;
        int tem = a[end + 1];//待插入的数据
        for (end = j; end >= 0; end--)
        {
            if (a[end] > tem)
            {
                a[end + 1] = a[end];
            }
            else {
                break;//避免极端情况如：当我们的tem 的值最小的时候，我们跳出循环在插入不会越界
            }
        }
        a[end + 1] = tem;
    }
 
}

代码解读：

在我们代码的时候可以先将单趟排序的思路写出来。再去将我们整个排序的实现。

首先我们要将我们待排序的值用一个变量存下来，因为我们往后面移动的这个行为会直接将后面的值给覆盖，这时我们待插入的值如果没有取出来的就会导致你找不到这个值了。

我们里面的 之后就是将我们待插入的值与区间里面的值进行比较，如果是小于那么与待插入的值往后移一个，否则就跳出循环。这个为什么我们不在里面将我们待插入的值插入进去，是为了当我们这个循环是正常结束的时候就不需要去进行特殊处理，我们都一律在循环外面进行插入。

对于外层循环就是控制我们插入的次数，先假设我们有序的区间里面还没有值，我们从第一个数开始插入，就是从下标为0的地方开始,但是我们的i是小于n-1,为了防止我们的end+1越界。

插入排序的时间、空间复杂度：

时间复杂度：我们插入的时间复杂度是O(N^2),

插入排序最好的情况是O(N)，数组有序的情况下。

最坏的情况是O(N^2)，逆序的情况下。

空间复杂度是O（1）。

稳定性：我们这里写的是稳定的。因为当其中有一个值与待插入的值相等的情况下我们是跳出内循环，插入再其后面，相对位置保持不变。

插入排序的一个特点：元素集合越接近有序，直接插入排序算法的时间效率越高