C语言 插入排序

适用场景： 数组基本有序，排序时可节约大量时间

排序思路： 默认数组有序，新加入的数找到自己合适的位置插入。 如果新数字基本有序，一次数组遍历即可完成排序。顺序数组排序时间复杂度为O(n), 逆序时间复杂度则退化为O(n^2).

C语言代码如下：

void insertSort(int * arr, int len)
{
    int swap = 0;

    if (NULL == arr)
    {
        return;
    }

    for (int i = 0; i < (len - 1); i ++)
    {
        //默认队列为有序队列，如果队列有序不用O(n)可排序完成
        if (arr[i] > arr[i + 1])
        {
            swap = arr[i + 1];
            arr[i + 1] = arr[i];
            for (int j = i - 1; j >= 0; j --)
            {
                if (swap < arr[j])
                {
                    arr[j + 1] = arr[j];
                }
                else
                {
                    break;
                }
            }

            if (0 > j)
            {
                j = 0;
            }

            arr[j] = swap;
        }
    }
}

如果该函数既要能完成正序，也能完成逆序，则增加一个比较函数指针作为参数输入。

void insertSort(int * arr, int len, int (*cmp)(int, int))
{
    int swap = 0;

    if (NULL == arr)
    {
        return;
    }

    for (int i = 0; i < (len - 1); i ++)
    {
        //默认队列为有序队列，如果队列有序不用O(n)可排序完成
        if (cmp(arr[i], arr[i + 1]) > 0)
        {
            swap = arr[i + 1];
            arr[i + 1] = arr[i];
            for (int j = i - 1; j >= 0; j --)
            {
                if (swap < arr[j])
                {
                    arr[j + 1] = arr[j];
                }
                else
                {
                    break;
                }
            }

            if (0 > j)
            {
                j = 0;
            }

            arr[j] = swap;
        }
    }
}