03-插入排序（python、oc）

简述：从下标为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;
            }
        }
    }
}