概念
插入排序(Straight Insertion Sort):有一個已經(jīng)有序的數(shù)據(jù)序列光坝,要求在這個已經(jīng)排好的數(shù)據(jù)序列中插入一個數(shù)逗栽,但要求插入后此數(shù)據(jù)序列仍然有序贞远,這個時候就要用到一種新的排序方法——插入排序法,
原理
將一個記錄插入到已排序好的有序表中悦即,從而得到一個新,記錄數(shù)增1的有序表逼裆。即:先將序列的第1個記錄看成是一個有序的子序列郁稍,然后從第2個記錄逐個進行插入,直至整個序列有序為止胜宇。
例子為從小到大的排序
算法描述(C語言)
void insert_sort(int *a, int len) {
for (int i = 1; i < len; i++) {
int temp = a[i]; //保存當(dāng)前位置的值
int j;
for (j = i - 1; j >= 0 && temp < a[j]; j--) {
a[j + 1] = a[j]; //后移一位
}
a[j + 1] = temp;//插入到合適的位置
}
}
int main() {
int a[] = {3, 2, 7, 1, 0, 3};
int len = sizeof(a)/sizeof(int);
insert_sort(a, len);
for (int i = 0; i < len; i++) {
printf("%d\n", a[i]);
}
return 0;
}
算法穩(wěn)定性
兩個相等的元素排序結(jié)束后位置都不會發(fā)生交換耀怜,所以插入排序是穩(wěn)定的恢着。
算法分析
時間復(fù)雜度:O(n2)