插入排序

void insertionSort(int arr[], const int n) 
{
    //n-1趟决定一个元素的在已排序的序列中的位置
    for (int i = 1; i <= n -1 ; i++)
    {
        //i+1位置的元素往已排序[0, i-1]里找位置
        int j = i;
        const int valueToInsert = arr[j];
        while (j > 0 && valueToInsert < arr[j - 1])
        {
            arr[j] = arr[j-1];
            j--;
        }

        arr[j] = valueToInsert;
    }
}