首页 > 代码库 > 直接插入排序（带哨兵和不带哨兵）

直接插入排序（带哨兵和不带哨兵）

2024-07-09 23:08:29   217人阅读

前言

插入排序(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]后移一个位置
  2. 若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]={2,87,39,49,34,62,53,6,44,98};ElementType arr1[11]={0,2,87,39,49,34,62,53,6,44,98};//不使用哨兵，每一次循环需要比较两次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];            else                break;        }        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");    return 0;}

运行结果如下：


联系
我们