【算法】哨兵思想 -- 待进一步总结
  KRe60ogUm4le 2024年05月31日 57 0

前言

插入排序(insertion sort)的基本思想:每次将一个待排序的记录,按其关键字大小插入到前面已经排序好的序列中,直到全部记录插入完成为止.

直接插入排序

基本思想

假设待排序的记录存放在数组R[1..n]中。初始时,R[1]自成1个有序区,无序区为R[2..n].从i = 2起直到i = n 为止,依次将R[i]插入当前的有序区R[1..i - 1]中,生成含n个记录的有序区.

排序方法

将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i - 1, i - 2, ....,1)的关键字比较:

  1. 若R[j]的关键字大于R[i]的关键字,则将R[j]后移一个位置

  1. 若R[j]的关键字小于或等于R[i]的关键字,则查找过程结束,j + 1即为R[i]插入位置

关键字比R[i]的关键字大的记录均已后移,所以j + 1的位置已经腾空,只要将R[i]直接插入到此位置即可完成一趟直接插入排序

c语言实现代码

InsertSort.c

#include<stdio.h>

typedef int ElementType;

ElementType arr[10]

ElementType arr1[11

//不使用哨兵,每一次循环需要比较两次void InsertSort(ElementType A[],int N)

{

int i,j;

ElementType temp;

for(i=1;i<N;i++)

{

temp=A[i];

for(j=i;j>0;j--)

{

if(A[j-1]>temp)

A[j]=A[j-1];

elsebreak;

}

A[j]=temp;

}

}

 

/*

使用A[0]作为哨兵,哨兵有两个作用:

1 暂时存放待插入的元素

2 防止数组下标越界,将j>0与A[j]>temp结合成只有一次比较A[j]>A[0],

这样for循环只做了一次比较,提高了效率,无哨兵的情况需要比较两次,for循环有两个判断条件

*/void WithSentrySort(ElementType A[],int N)

{

int i,j;

for(i=2;i<N;i++)

{

A[0]=A[i];

for(j=i-1;A[j]>A[0];j--)

{

A[j+1]=A[j];

}

A[j+1]=A[0];

}

}

 

void Print(ElementType A[],int N)

{

int i;

for(i=0;i<N;i++)

{

printf(" %d ",A[i]);

}

}

int main()

{

Print(arr,10);

printf("\n");

InsertSort(arr,10);

Print(arr,10);

printf("\n");

WithSentrySort(arr1,11);

Print(arr1,11);

printf("\n");

return0;

}

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2024年05月31日 0

暂无评论

推荐阅读
  KRe60ogUm4le   2024年05月31日   36   0   0 c++算法
  KRe60ogUm4le   2024年05月31日   33   0   0 c++算法
KRe60ogUm4le
最新推荐 更多

2024-05-31