C语言-简单插入排序

        直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。 

当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N^2)。

所以，数据越接近正序，直接插入排序的算法性能越好。 

由直接插入排序算法可知，我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为 1 。

直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。

void insertSort(int arr[], int n)
{
    int i, j, tmp;

    for(i = 1; i < n; i++)
    {
        for(j = i; j > 0; j--)
        {
            if(arr[j] < arr[j-1])
            {
                tmp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = tmp;
            }
            else
            {
                break;
            }
        }
    }

    return;
}