插入排序

时间复杂度

最好情况:已正序 $O(n)$

一般情况:$O(n^2)$

最坏情况:逆序$O(n^2)$

C++ 代码

#include <iostream>

using namespace std;

void insertionSort(int arr[], int n)
{   //从1开始 直接跳过 a[0] 1个数的时候 已经排序完好了
    for (int i = 1; i < n; i ++)  //每次循环i 给前i个数进行排序  
    {   
        int key = arr[i];
        int j = i - 1;
                        //arr[j]>key 就将 key 向前移动 
        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];    //同时将a[j] 向后移动 为key挪位置
            j --;
        }
        arr[j + 1] = key;//找到小于key的or到开头了 把key插到这里
    }
}

int main()
{
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i ++) cin >> arr[i];

    insertionSort(arr, n);

    for (int i = 0; i < n; i ++) cout << arr[i] << ' ';

    return 0;
}