内部排序之直接插入排序

68 阅读 0 评论 45 点赞

我是靠谱客的博主真实自行车，最近开发中收集的这篇文章主要介绍内部排序之直接插入排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

直接插入排序

直接插入排序(Straight Insertion Sort)是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。
直接插入排序的方法：先将序列中第一个记录看成有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字递减的有序序列为止
直接插入排序中需要设定一个临时变量temp，temp在直接插入排序中尤为重要，充当了一个哨兵的角色。
下面我们用这样一个例子去详细的说明直接插入排序的过程：
现在我们有一串无序序列“49，38，65，97，76，13，27，49”也就是一串数组，设为数组a
我们要用直接插入排序的方法将其变为有序的序列
1.先将这八个数字标号：
此时在这里插入图片描述
2.此时我们将a[0]看为为有序序列，从a[1]开始逐个插入，所以将a[1]的值赋给哨兵temp，a[1]的值就为空了

3.将哨兵temp与有序序列的最后一位比较；如若temp的值>=有序序列最后一个的值/temp比较完了有序序列中所有的数（也就是temp的值最小，则temp值赋给数组中的空位；如若temp的值<有序序列最后一个的值，则有序序列的最后一个向前移动填补前面的的空位，留下自己原来的位置作为空位，然后temp的值在与有序序列的倒数第二位比较，直至temp>有序序列的某一位的值，比较结束，temp填补空位
此例中：temp<a[0] ,则a[0]向前移动填补a[1]的空位，此时a[0]为空位，temp比较完了有序序列中所有的数，则temp值赋给空位

在这里插入图片描述
4.此时序列的前两个数已经有序，则取第三位a[2]作为哨兵temp，留下空位a[2]

仿照3的比较过程用temp与有序序列最后一个数比较，也就是temp与a[1]比较，此时temp>a[1]，则temp填入空位a[2].
5
5.现在轮到a[3]了，a[0]-a[2]已经是有序序列了，所以取a[3]为哨兵，留下空位a[3]
在这里插入图片描述
仿照3的比较过程用temp与有序序列最后一个数比较，也就是temp与a[2]比较，此时temp>a[2]，则temp填入空位a[3].

6.此时a[0]-a[3]已经有序，轮到了a[4],所以取a[4]为哨兵，留下空位a[4]

在这里插入图片描述
仿照3的比较过程用temp与有序序列最后一个数比较，也就是temp与a[3]比较,此时temp<a[3],则将a[3]后移填补空位a[4],留下空位
a[3]

temp继续比较，此时应该与有序序列中倒数第二个数比较也就是a[2],此时temp>a[2],所以temp填入空位a[3]
在这里插入图片描述
7.此时a[0]-a[4]已经成为有序序列，剩余的三个数a[5],a[6],a[7]交给读者自己思考，相信你一定可以还原出来整个过程的

接下来是是代码部分（c语言）

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#defineMAXSIZE 8
typedef int KeyType; //定义关键字类型
typedef int InfoType; //其他数据项类型
typedefstruct //记录类型
{
KeyType key; //关键字项
InfoType data; //其他数据项的类型InfoType
} RecType;
//排序的记录类型定义
/*
直接插入排序
参数说明：
arr:传入要排序的数组
n：数组的大小
/
void InsertSort(RecType R[] , int n)
{
int i;
int j;
RecType
temp; //R[0]默认为有序区，无序区从R[1]开始
for(i = 1; i < n; i++)
{
//外层for循环每次提取无序区的第一个关键字
temp = R[i];
/
R[j-1].key > temp.key：有序区中的关键字是否比无序区的第一个关键字大
j- -：从后往前，依次比较有序区中的每一个关键字
*/
for(j = i; j > 0 &&R[j-1].key > temp.key; j–)
{
//把有序区中的关键字依次往后移动
R[j] = R[j-1];
}
//如果无序区中的第一个关键字比有序区中的关键字大，那么无序区中的第一个关键字的位置插入到有序区中该关键字后面的位置
R[j].key = temp.key;
}
}
int main(void)
{
RecType R[MAXSIZE] = {0};
int arr[] = {49,38,65,97,76,13,27,49};
int i;
printf("--------排序前--------n");
for(i = 0; i < MAXSIZE; i++)
{
R[i].key = arr[i];
printf(“R[%d].key = %dn” , i, R[i].key);
}
//插入排序
InsertSort(R, MAXSIZE);
printf("--------排序后--------n");
for(i = 0; i < MAXSIZE; i++)
{
printf(“R[%d].key = %dn” , i, R[i].key);
}
return 0;
}