插入排序

插入排序（Insert Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

程序实现

• Python

def insert_sort(ls):
    length = len(ls)
    for i in range(1,length):
        for j in range(i,-1,-1):
            if ls[j]>ls[j-1]:
                ls[j],ls[j-1]=ls[j-1],ls[j]
            else:
                break
    return ls

• C++

void bubble_sort(int nums[],int n){
    for (int i=1;i<n;i++){
        for (int j=i;j>0;j--){
            if (nums[j]<nums[j-1]){
                swap(nums[j],nums[j-1]);
            }
            else{
                break;
            }
        }
    }
}

复杂度和稳定性

• 平均时间复杂度: O(n^2)，最优时间复杂度: O(n)
• 空间复杂度为 O(1)
• 稳定性：稳定