前提条件：
-大多数情况下，为了简单起见只讨论从小到大的排序
-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)
