前提條件：
-大多數(shù)情況下遏弱，為了簡單起見只討論從小到大的排序
-N是正整數(shù)
-只討論基于比較的排序（< > =有定義）
-只討論內(nèi)部排序滑频，即加載到內(nèi)存中的排序
相關(guān)概念
-穩(wěn)定性：排序前相等的兩個(gè)元素西乖，排序后相對位置沒有發(fā)生改變
-時(shí)間復(fù)雜度:時(shí)間復(fù)雜度是定量描述一個(gè)算法的運(yùn)行的時(shí)間，一般與算法輸入值的長度N有關(guān)术陶，常用大O符號表述;
統(tǒng)一的入口
void X_sort(int arr[] ,int N)
ElenmentType 為數(shù)組類型 N 為數(shù)中元素的個(gè)數(shù)
示例圖
插入排序.jpg
主函數(shù)
//插入排序
void Insertion_Sort(int arr[],int N){
//每次取一個(gè)元素
for (int p = 1; p < N; p++) {
//存儲取出的元素
int tmp = arr[p];
//與在它位置之前的元素進(jìn)行比較
for (int i = p; i > 0 && arr[i-1] > tmp; i--){
//如果大于當(dāng)前元素燎字，則把兩個(gè)元素互換順序
arr[i] = arr[i-1];
arr[i-1] = tmp;
}
}
}
時(shí)間復(fù)雜度：
沒有一種排序在任何情況下都是表現(xiàn)最好
最好情況：順序 T = O(N)
最壞情況：逆序 T = O(N^2)
穩(wěn)定性： 穩(wěn)定
測試
int main(int argc, const char * argv[]) {
//數(shù)組
int arr[9] ={8,6,1,2,4,9,3,7,5};
//冒泡排序函數(shù)
Insertion_Sort(arr, 9);
//打印排序后結(jié)果
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)
