c 插入排序

递归：

#include <stdio.h>

void insertionSort(int *array, int allnum, int order) 
{
    // *array -> 数组的地址
    // allnum -> 数组的元素个数
    // order -> 待插入数的下标
    int datum; // datum -> 定义基准点
    
    // 递归的结束判断条件
    if (order >= allnum)
    {
        return;
    }
    
    // 判断是否为第一次
    if (0 == order)
    {
        insertionSort(array,allnum,++order);
        return;
    }
    // 判断是否为第二次
    if (1 == order)
    {
        if (array[1] < array[0])
        {
            int temp = array[0];
            array[0] = array[1];
            array[1] = temp;
        }
        insertionSort(array,allnum,++order);
        return;
    } 
    
    // 如果是第三次以上 -->>
    /* 判断是否为最大值？*/
    if (array[order] > array[order - 1])
    {
        insertionSort(array,allnum,++order); 
        return;
    }
    /* 判断是否为最小值？*/
    if (array[order] < array[0])
    {
        int temp = array[order];
        for (int ii = order; ii > 0; ii--)
        {
            array[ii] = array[ii-1];
        }
        array[0] = temp;
        insertionSort(array,allnum,++order); 
        return;
    }

    /* 如果在中间 ---> 待插入元素的寻位 */
    for (int i = order; i > 1; i--)
    {

        if (array[order] < array[i-1] && array[order] > array[i-2])
        {
            int temp = array[order];
            for (int ii = order; ii >= i; ii--)
            {
                array[ii] = array[ii-1];
            }
            array[i-1] = temp;
            break;
        }
        
    }
    insertionSort(array,allnum,++order);
    return;
}

void printArray(int *array, int num)
{
    for (int i = 0; i < num; i++)
    {
        printf("%2d ",*(array + i));
    }
    putchar('\n');
    return;
}

int main(void)
{
    int array[] = {9,10,3,4,2,5,1,7,8,6};
    int num = sizeof(array) / sizeof(int);
    printArray(array,num);
    insertionSort(array,num,0);
    printArray(array,num);
    return 0;
}