简述：从下标为1的元素开始往前查找，依次与前边的所有元素进行比较，直到与第0个元素比较，找到自己合适的位置后。开始查找的起始下标+1，重复上一过程。
- 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
- 最坏时间复杂度：O(n²)
- 稳定
python3
# coding:utf-8
def insert_sort(alist):
"""插入排序"""
n = len(alist)
for j in range(1,n):
i = j
while i > 0:
if alist[i] < alist[i-1]:
alist[i], alist[i - 1] = alist[i - 1] , alist[i]
i -= 1
else:
break
if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
insert_sort(li)
print(li)
objective - c
- (void)insert_sort:(NSMutableArray *)arr {
for (int i = 1; i < arr.count; i++) {
int j = i;
while (j > 0) {
if (arr[j] < arr[j-1]) {
NSNumber *temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j -= 1;
} else {
break;
}
}
}
}
