直接插入排序 简单易懂写法

直接插入排序是一种简单易懂的排序算法，下面是它的一种实现方式：

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

# 示例arr = [5, 2, 8, 9, 1]
insertion_sort(arr)
print(arr)  # 输出：[1, 2, 5, 8, 9]

在这个实现中，我们从第二个元素开始遍历数组，将当前元素与前面已排序的元素进行比较，如果前面的元素大于当前元素，则将前面的元素后移一位，直到找到合适的位置插入当前元素。这样，每次插入一个元素后，前面的部分都是有序的，最终完成整个数组的排序。

相关问题

归并排序和直接插入排序

归并排序和直接插入排序是两种常见的排序算法。

归并排序（Merge Sort）是一种分治策略的排序算法。它将待排序的序列不断地二分，直到只剩下一个元素，然后再将这些单个元素合并成有序的序列。具体步骤如下：
1. 将待排序序列不断地二分，直到每个子序列只剩下一个元素。
2. 将相邻的两个子序列两两合并，使得合并后的子序列有序。
3. 不断重复步骤2，直到最终只剩下一个有序序列。

直接插入排序（Insertion Sort）是一种简单直观的排序算法。它通过构建有序序列，对于未排序的元素，在已排序序列中从后向前扫描，找到相应位置并插入。具体步骤如下：
1. 将第一个元素视为已排序序列。
2. 从第二个元素开始，逐个将未排序的元素插入到已排序序列中的正确位置。
3. 重复步骤2，直到所有元素都被插入到有序序列中。

归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。它具有稳定性和适用于大规模数据排序的优点。
直接插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。它具有简单易懂、适用于小规模数据排序的优点。

这是关于归并排序和直接插入排序的简要介绍，希望能对你有所帮助！如果你还有其他问题，请随时提问。

归并排序算法C语言通俗易懂简单程序

以下是一个通俗易懂的归并排序算法的C语言程序示例：

#include <stdio.h>

// 合并两个有序数组
void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
    int i = 0, j = 0, k = 0;

    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }

    while (i < leftSize) {
        arr[k++] = left[i++];
    }

    while (j < rightSize) {
        arr[k++] = right[j++];
    }
}

// 归并排序
void mergeSort(int arr[], int size) {
    if (size <= 1) {
        return;
    }

    int mid = size / 2;
    int left[mid];
    int right[size - mid];

    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }

    for (int i = mid; i < size; i++) {
        right[i - mid] = arr[i];
    }

    mergeSort(left, mid);
    mergeSort(right, size - mid);
    merge(arr, left, mid, right, size - mid);
}

int main() {
    int arr[] = {5, 2, 8, 3, 1, 9, 4, 7, 6};
    int size = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, size);

    printf("排序后的数组：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}