数据结构的直接插入排序(C语言版)
一.直接插入排序的基本概念
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