前提条件：

-大多数情况下，为了简单起见只讨论从小到大的排序
-N是正整数
-只讨论基于比较的排序（< > =有定义）
-只讨论内部排序，即加载到内存中的排序

相关概念

-稳定性：排序前相等的两个元素，排序后相对位置没有发生改变
-时间复杂度:时间复杂度是定量描述一个算法的运行的时间，一般与算法输入值的长度N有关，常用大O符号表述;

统一的入口

 void X_sort(int arr[] ,int N)
 ElenmentType 为数组类型  N 为数中元素的个数

示例图

插入排序.jpg

主函数

//插入排序
void Insertion_Sort(int arr[],int N){
   //每次取一个元素
   for (int p = 1; p < N; p++) {
       //存储取出的元素
       int tmp = arr[p];
       //与在它位置之前的元素进行比较
       for (int i = p; i > 0 && arr[i-1] > tmp; i--){
           //如果大于当前元素，则把两个元素互换顺序
           arr[i] = arr[i-1];
           arr[i-1] = tmp;
       }
   }
}

时间复杂度：

没有一种排序在任何情况下都是表现最好

最好情况：顺序 T = O(N)

最坏情况：逆序 T = O(N^2)

稳定性： 稳定

测试

int main(int argc, const char * argv[]) {
    //数组
    int arr[9] ={8,6,1,2,4,9,3,7,5};
   //冒泡排序函数
    Insertion_Sort(arr, 9);
   //打印排序后结果
    for (int j= 0; j< 9; j++) {
        printf("%d",arr[j]);
    }
    return 0;
}

输出

Printing description of arr:
(int [9]) arr = ([0] = 1, [1] = 2, [2] = 3, [3] = 4, [4] = 5, [5] = 6, [6] = 7, [7] = 8, [8] = 9)