admin 管理员组文章数量: 1184232
2024年1月27日发(作者：jfreechart jar包下载)
c语言插入排序代码
C语言插入排序代码
插入排序是一种简单直观的排序算法，其基本思想是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增加1的有序表。具体实现时，我们可以将待排序数组分为已排序和未排序两个部分，每次从未排序部分中取出一个元素，在已排序部分中找到合适的位置插入即可。下面是C语言实现插入排序算法的代码：
```
void insertion_sort(int arr[], int len) {
int i, j, temp;
for (i = 1; i < len; i++) {
temp = arr[i]; // 取出待插入元素
j = i - 1;
while (j >= 0 && arr[j] > temp) { // 在已排好序的数组中找到合适位置
arr[j + 1] = arr[j]; // 将元素后移
j--;
}
arr[j + 1] = temp; // 插入元素
}
}
```
代码解析
首先定义了一个名为insertion_sort的函数，它接受两个参数：一个整型数组arr和数组长度len。
变量i用于遍历整个数组，初始值为1。因为我们假设第一个元素已经排好序了。
在每一次循环开始时，我们先取出待插入元素temp。
变量j用于在已经排好序的数组中找到合适的位置插入temp。初始值为i-1，因为我们需要从已经排好序的数组的最后一个元素开始比较。
在while循环中，我们比较arr[j]和temp的大小。如果arr[j]大于temp，则将arr[j]后移一位，继续向前比较。如果arr[j]小于或等于temp，则说明temp应该插入到arr[j]的后面。
最后，我们将temp插入到位置j+1处。
代码优化
上面的代码实现了插入排序算法，但是还可以进行一些优化。
首先，在while循环中，我们每次需要比较两个数并且将一个数后移一位。这个过程可以用一个for循环来代替：
```
for (; j >= 0 && arr[j] > temp; j--) {
arr[j + 1] = arr[j];
}
```
其次，在每次将待插入元素插入到已排好序的数组时，都需要进行一次赋值操作。这个过程可以用memcpy函数来代替：
```
memcpy(&arr[j + 2], &arr[j + 1], (i - j - 1) * sizeof(int));
memcpy(&arr[j + 1], &temp, sizeof(int));
```
最终优化后的代码如下：
```
void insertion_sort(int arr[], int len) {
int i, j;
for (i = 1; i < len; i++) {
int temp = arr[i];
for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
memcpy(&arr[j + 2], &arr[j + 1], (i - j - 1) * sizeof(int));
}
memcpy(&arr[j + 1], &temp, sizeof(int));
}
}
```
总结
插入排序是一种简单直观的排序算法，其时间复杂度为O(n^2)。在实际应用中，插入排序常用于小规模数据的排序或者作为其他高级排序算法的子过程。
版权声明：本文标题：c语言插入排序代码 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1706344339a505609.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论