请写出直接插入排序算法代码，分析直接插入排序的最好和最坏时间复杂度

以下是直接插入排序算法的代码：

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

直接插入排序的最好时间复杂度是(n)，当待排序的数组已经是有序的情况下，只需要比较n-1次即可完成排序。

最坏时间复杂度是O(n^2)，当待排序的数组是逆序的情况下，需要比较和移动的次数都是最多的，需要比较n(n-1)/2次，移动n(n-1)/2次。

相关问题

插入排序算法的最好和最坏情况复杂度分析

这里给出原问题的翻译：插入排序算法的最好和最坏情况复杂度分析。

回答：

插入排序算法的最好情况是当原数组已经排好序时，时间复杂度为O(n)，最坏情况是当原数组为逆序时，时间复杂度为O(n^2)，平均情况下时间复杂度为O(n^2)。插入排序算法适合于对小数据集进行排序。

请用伪代码写出折半插入排序，并分析它的时间复杂度

算法描述：

折半插入排序是对直接插入排序的优化，其思路是将待排序的元素插入到已有序的序列中，但不是像直接插入排序一样从前往后逐个比较，而是采用折半查找的方法找到插入的位置。具体步骤如下：

1. 从第二个元素开始，把它和前面的有序序列进行比较，找到插入位置；
2. 通过折半查找的方式找到插入位置，减少比较次数；
3. 将待排序元素插入到已有序的序列中，继续进行下一次插入。

伪代码实现：

function binaryInsertionSort(arr):
    for i from 1 to length(arr)-1 do
        temp = arr[i]
        left = 0
        right = i - 1
        while left <= right do
            mid = (left + right) / 2
            if arr[mid] > temp then
                right = mid - 1
            else:
                left = mid + 1
        end while
        for j from i - 1 downto left do
            arr[j+1] = arr[j]
        end for
        arr[left] = temp
    end for
    return arr
end function

时间复杂度分析：

1. 折半查找的时间复杂度为 O(log n)；
2. 插入操作最多需要移动 n-1 次，因此时间复杂度为 O(n)；
3. 因此，折半插入排序的时间复杂度为 O(n log n)。