插入排序（考研与工程师必备）

插入排序是一种简单快速的排序算法，就是把一无序的数据，以第一个数据为准，假设第一个数据是经过排序过的，把第二个数据和排好的数据进行比较，注意插入排序是从后向前进行比较，如果此时有一个新元素，则从已经排序的序列的尾部向前进行比较，如果排序过的序列的元素值大于新元素，则把新元素插入到该元素的前面。
程序实现：
int *InsertSort(int arr[], int n)
{
int i, j, key;

// 从第二个元素开始遍历（索引1）
for (i = 1; i < n; i++) {
    key = arr[i]; // 当前要插入的元素
    j = i - 1;   // 已排序部分的最后一个元素索引
    
    // 将当前元素与已排序部分从后向前比较
    // 如果当前元素较小，则向后移动已排序元素
    while (j >= 0 && arr[j] > key) 
    {
        arr[j + 1] = arr[j];
        j--;
    }
    
    // 找到合适位置，插入当前元素
    arr[j + 1] = key;
}
return arr;

}

int main(void)
{
int buf[]={12,25,11,5,56,32,14,66,23};
int *p = InsertSort(buf,sizeof(buf)/sizeof(buf[0]));
for (int i = 0; i < sizeof(buf)/sizeof(buf[0]); ++i)//输出显示排序后的数组
{
printf("%d\n",p[i]);
}
return 0;
}

程序效果：