直接 插入排序 （Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。.
废话不多说先看看代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#define _CRT_SECURE_NO_WARNINGS 1//直接插入排序法#include <stdio.h>void Compare(int arr[], int len){ int i = 0; for (i = 0; i < len-1; i++)//len减一因为要插入的数是i+1 { int M = i;//记录有序列表最后应该元素下标 int num = arr[i + 1];//要插入的数 while (M >= 0) { if (num < arr[M])//继续比较 { arr[M + 1] = arr[M];//交换数值 M--; } else { break; } } arr[M + 1] = num; }}int main(){ int arr[] = { 2,3,4,1,2,34,4,56,3,434,4 }; int len = sizeof(arr) / 4; int i = 0; Compare(arr,len); for (i = 0; i < len; i++) { printf("%d ", arr[i]); } return 0;} |
一、什么是直接插入排序
就像玩扑克时相同，假设前n-1项是有序数列，现在将第n项插入其中，使得前n项有序。然后依次进行插入，直到将整个数列全部插入，排序完成。
对于一组数据我们无法得知是否有序，但第一个元素只有一个，所以是有序的，所以将第一个元素作为第一个有序数列。后面的数值依次插入其中·。
二、代码讲解
|
1
|
void Compare(int arr[], int len) |
首先创建一个插入排序的函数，需要传入数组和数据个数，因此创建int arr[],int len两个形参。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
void Compare(int arr[], int len){ int i = 0; for (i = 0; i < len-1; i++)//len减一因为要插入的数是i+1 { int M = i;//记录有序列表最后应该元素下标 int num = arr[i + 1];//要插入的数 while (M >= 0) { if (num < arr[M])//继续比较 { arr[M + 1] = arr[M];//交换数值 M--; } else { break; } } arr[M + 1] = num; }} |
因为插入排序是由前一个和后一个数据进行比较的，所以比较次数为（数据个数-1）。
|
1
2
|
int M = i;//记录有序列表最后应该元素下标 int num = arr[i + 1];//要插入的数 |
这里需要前后两个数据比较，且这两个需要比较的数据是变化的，所以创建表示两个数据的变量。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
while (M >= 0) { if (num < arr[M])//继续比较 { arr[M + 1] = arr[M];//交换数值 M--; } else { break; } } arr[M + 1] = num; |
利用循环进行比较，如果后一个数比前一个数小，就交换位置（数值）。如果后一个数比前一个数更大，break跳出循环。
当每一次循环比较到最后一次时，需要将两个数进行最后的交换，因为之前只是将arr[M]的值赋给了arr[M+1],此时需要将arr[M+1]的值赋给arr[M]才算完成数值交换，否则会出现比较数据丢失和重复的问题。此时的M--了的，所以需要M+1得到所需要的数据下标进行交换。
总结
本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注服务器之家的更多内容!
原文链接：https://blog.csdn.net/weixin_63246064/article/details/122050587
