插入法排序

插入排序（Insertion Sort）的基本思想是将待排序的元素插入到已经排好序的有序序列中，从而得到一个新的、元素个数加一的有序序列。具体实现步骤如下：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果已经排序的元素大于新元素，将该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5

代码实现：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

其中，arr是待排序的列表，key是当前要插入的元素，j是已经排好序的元素序列的最后一个元素的下标。

相关问题

C语言简化的插入法排序

插入排序是一种简单直观的排序算法，其基本思想是将待排序的元素插入到已排序的序列中，从而得到一个新的有序序列。插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。

下面是C语言简化的插入排序的代码：

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

这段代码实现了一个简单的插入排序算法，它接受一个整型数组和数组长度作为参数，对数组进行排序。

c++写一个直接插入法排序函数

好的，以下是直接插入法排序函数的C++实现：

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

        // 将比key大的元素向右移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

该函数接收一个整型数组`arr`和数组长度`n`作为参数，使用直接插入法对数组进行升序排序。具体实现是通过遍历数组，将每个元素插入到已排序的子数组中的正确位置，使得子数组仍然保持有序。时间复杂度为$O(n^2)$，空间复杂度为$O(1)$。