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

05-29 1239阅读

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

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

将数组分为已排序和未排序两部分。
每次从未排序部分取出一个元素,将其插入到已排序部分的合适位置,使得已排序部分保持有序。
重复步骤2,直到整个数组有序。

2.排序的工作原理

假设前 i-1 个元素已经有序,现在要将第 i 个元素插入到前 i-1 个有序元素中,使得前 i 个元素也有序。
为了插入第 i 个元素,需要先找到它在前 i-1 个元素中的适当位置。可以从右到左依次与前面的元素比较,找到第一个小于第 i 个元素的位置。
找到合适的位置后,将第 i 个元素插入到该位置,同时需要将位置之后的元素都向后移动一位。
重复步骤 1-3, 直到整个数组有序。

3.排序的优点

实现简单,编码容易。
对于部分有序的数组,直接插入排序的效率很高。
是一种稳定的排序算法,即相等元素的相对位置不会改变。
在数组规模较小时,直接插入排序的性能优于其他更复杂的排序算法。

4.排序的缺点

时间复杂度为O(n^2),在数据量较大时效率较低。
需要在数组中进行大量的数据移动操作,效率较低。
不适合于元素数量较大的数组排序。如果待排序数组基本有序,直接插入排序的效率会很高,但如果数组越乱,排序效率就会越低。
无法利用cpu的缓存机制,对于大规模数据排序,其性能会明显低于其他排序算法。

5.直接插入排序的功能

将无序数组或部分有序数组排列成升序序列。
维护数组中元素的相对顺序,即相等元素的相对位置不会改变。这使得直接插入排序是一种稳定的排序算法。
适用于小规模数据的排序,当数组规模较小时它的性能比较优秀。
对于部分有序的数组,直接插入排序的效率会很高,因为需要移动的元素较少。
可以改写为降序排序,只需要在插入时改为从后向前比较并插入即可。
可以作为其他排序算法的基础,如希尔排序就是基于直接插入排序改进而来的。

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

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

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

insertionSort(int arr[], int n) 函数是直接插入排序的实现。它接受一个整型数组 arr 和数组长度 n 作为参数。
外层 for 循环从下标为 1 的元素开始遍历数组。这是因为下标为 0 的元素可以认为是一个已排序的子数组。
在每次外层循环迭代中:
- 将当前元素 arr[i] 保存到变量 key 中。
- 将当前元素的前一个下标 i-1 赋给变量 j。这个变量用于在已排序的子数组中找到 key 的插入位置。
内层 while 循环用于在已排序的子数组中找到 key 的插入位置。循环条件是 j >= 0 && arr[j] > key，即只要 j 不越界且 arr[j] 大于 key，就一直执行循环体。
在内层循环中:
- 将 arr[j] 向后移动一位,赋值给 arr[j+1]。这相当于为 key 腾出一个位置。
- 将 j 减1,继续向前检查已排序的子数组。
当内层循环结束时,也就找到了 key 的合适插入位置 j+1。此时将 key 赋值给 arr[j+1]，完成了插入操作。
main() 函数中创建了一个示例数组 arr，并调用 insertionSort() 函数对其进行排序。
最后,分别打印排序前后的数组。

2.算法的工作过程

将数组分为已排序和未排序两部分。
每次从未排序部分取出一个元素 key。
在已排序部分中找到 key 的合适插入位置。
将 key 插入到找到的位置,完成一次插入排序。
重复步骤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 
void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i = 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  
```