数据结构的直接插入排序（C语言版）

一.直接插入排序的基本概念

1.直接插入排序的基本思想

1. 将数组分为已排序和未排序两部分。

2. 每次从未排序部分取出一个元素,将其插入到已排序部分的合适位置,使得已排序部分保持有序。

3. 重复步骤2,直到整个数组有序。

2.排序的工作原理

1. 假设前 i-1 个元素已经有序,现在要将第 i 个元素插入到前 i-1 个有序元素中,使得前 i 个元素也有序。

2. 为了插入第 i 个元素,需要先找到它在前 i-1 个元素中的适当位置。可以从右到左依次与前面的元素比较,找到第一个小于第 i 个元素的位置。

3. 找到合适的位置后,将第 i 个元素插入到该位置,同时需要将位置之后的元素都向后移动一位。

4. 重复步骤 1-3, 直到整个数组有序。

3.排序的优点

1. 实现简单,编码容易。

2. 对于部分有序的数组,直接插入排序的效率很高。

3. 是一种稳定的排序算法,即相等元素的相对位置不会改变。

4. 在数组规模较小时,直接插入排序的性能优于其他更复杂的排序算法。

4.排序的缺点

1. 时间复杂度为O(n^2),在数据量较大时效率较低。

2. 需要在数组中进行大量的数据移动操作,效率较低。

3. 不适合于元素数量较大的数组排序。如果待排序数组基本有序,直接插入排序的效率会很高,但如果数组越乱,排序效率就会越低。

4. 无法利用cpu的缓存机制,对于大规模数据排序,其性能会明显低于其他排序算法。

5.直接插入排序的功能

1. 将无序数组或部分有序数组排列成升序序列。

2. 维护数组中元素的相对顺序,即相等元素的相对位置不会改变。这使得直接插入排序是一种稳定的排序算法。

3. 适用于小规模数据的排序,当数组规模较小时它的性能比较优秀。

4. 对于部分有序的数组,直接插入排序的效率会很高,因为需要移动的元素较少。

5. 可以改写为降序排序,只需要在插入时改为从后向前比较并插入即可。

6. 可以作为其他排序算法的基础,如希尔排序就是基于直接插入排序改进而来的。

二.直接插入排序的代码实现

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 = j - 1;
        }
        arr[j + 1] = key;
    }
}

1.直接插入排序算法的工作原理

1. insertionSort(int arr[], int n) 函数是直接插入排序的实现。它接受一个整型数组 arr 和数组长度 n 作为参数。

2. 外层 for 循环从下标为 1 的元素开始遍历数组。这是因为下标为 0 的元素可以认为是一个已排序的子数组。

3. 在每次外层循环迭代中:

   • 将当前元素 arr[i] 保存到变量 key 中。
   • 将当前元素的前一个下标 i-1 赋给变量 j。这个变量用于在已排序的子数组中找到 key 的插入位置。

4. 内层 while 循环用于在已排序的子数组中找到 key 的插入位置。循环条件是 j >= 0 && arr[j] > key，即只要 j 不越界且 arr[j] 大于 key，就一直执行循环体。

5. 在内层循环中:

   • 将 arr[j] 向后移动一位,赋值给 arr[j+1]。这相当于为 key 腾出一个位置。
   • 将 j 减1,继续向前检查已排序的子数组。

6. 当内层循环结束时,也就找到了 key 的合适插入位置 j+1。此时将 key 赋值给 arr[j+1]，完成了插入操作。

7. main() 函数中创建了一个示例数组 arr，并调用 insertionSort() 函数对其进行排序。

8. 最后,分别打印排序前后的数组。

2.算法的工作过程

1. 将数组分为已排序和未排序两部分。
2. 每次从未排序部分取出一个元素 key。
3. 在已排序部分中找到 key 的合适插入位置。
4. 将 key 插入到找到的位置,完成一次插入排序。
5. 重复步骤2-4,直到整个数组有序。

三.直接插入排序的源代码

1.insertionSort(int arr[], int n) 函数

• 接受一个整型数组 arr 和数组长度 n 作为输入参数。
• 实现直接插入排序算法,将数组 arr 按升序排列。

2.算法步骤

• 从数组的第二个元素开始遍历 (i = 1到n-1).
• 对于当前元素 arr[i], 将其保存在变量 key 中.
• 设置一个指针 j 指向当前元素的前一个位置 (j = i-1).
• 从 j 开始向前遍历已排序子数组, 将大于 key 的元素都向后移动一位 (while (j >= 0 && arr[j] > key)).
• 找到 key 的正确插入位置后, 将 key 插入到该位置 (arr[j+1] = key).

3.main() 函数

• 定义一个整型数组 arr 并计算其长度 n.
• 打印原始数组.
• 调用 insertionSort() 函数对数组进行排序.
• 打印排序后的数组.

通过这段代码,我们可以看到直接插入排序的具体实现过程。它将数组分为已排序和未排序两部分,并且每次从未排序部分取出一个元素,找到它在已排序部分的正确位置并插入。这种简单高效的排序方法在小规模数据和部分有序数组中表现出色。

#include <stdio.h>

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 = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    insertionSort(arr, n);

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

    return 0;
}