算法解析之插入排序

插入排序

插入排序类似于打扑克牌整理手牌的情景

算法思路：
1、把整个序列分为已排序部分和未排序部分，初始状态就是第一个元素和剩下的部分
2、取出未排序部分的第一个值在已排序部分寻找合适的位置插入
3、重复2直到有序
C++：

template <typename T>
void insertionSort(T arr[],int n){
    //3:未排序部分有n-1个元素，所以需要n-1次循环
    for (int i = 1; i < n; i++) {//i指示了未排序部分的第一个元素
        //2:在已排序部分查找至多需要j-1次
        for (int j = i; j > 0; j--) {//j初始为i，开始冒泡
            if (arr[j] < arr[j-1]) {
                swap(&arr[j], &arr[j-1]);
            }else{
                break;//如果待插入元素大于或等于前一个元素，跳出，因为这时已经有序
            }
        }
    }
}