插入排序
插入排序的代碼實(shí)現(xiàn)雖然沒(méi)有冒泡排序和選擇排序那么簡(jiǎn)單粗暴兜辞，但它的原理應(yīng)該是最容易理解的了胡诗，因?yàn)橹灰蜻^(guò)撲克牌的人都應(yīng)該能夠秒懂居暖。插入排序是一種最簡(jiǎn)單直觀的排序算法，它的工作原理是通過(guò)構(gòu)建有序序列菱蔬，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描史侣，找到相應(yīng)位置并插入拴泌。
算法步驟：
- 將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列惊橱。
- 從頭到尾依次掃描未排序序列蚪腐，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等税朴，則將待插入元素插入到相等元素的后面回季。）
時(shí)間復(fù)雜度和空間復(fù)雜度
時(shí)間復(fù)雜度：
(1)最好： O(n）
（2)最壞：O(n2)
(3)平均： O(n2）
空間復(fù)雜度：
O（1）
參考代碼
C語(yǔ)言
#include <stdio.h>
void swap(int a[],int i ,int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void sort(int a[],int length){
for (int i = 1; i<length; i++) {
for (int j = i; j>0; j--) {
if (a[j] < a[j-1]) {
swap(a, j, j-1);
}else{
break;
}
}
}
}
int main(int argc, const char * argv[]) {
// insert code here...
// insert code here...
int a[] = {1,6,4,8,7,5,3,2};
sort(a,8);
for (int i = 0; i<8; i++) {
printf("%d ",a[i]);
}
return 0;
}
