插入排序和折半插入排序实现

65 阅读 0 评论 43 点赞

我是靠谱客的博主虚拟悟空，最近开发中收集的这篇文章主要介绍插入排序和折半插入排序实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、实验（实训）目的
掌握插入排序的两种方法并加以实现：

二、实验（实训）原理或方法
直接插入排序：插入排序从第二个数开始，拿出第二个数进行向前插入排序，一直到最后一个数向前做插入排序。算法稳定。

折半插入排序:顺序地把待排序的序列中的各个元素按其关键字的大小，通过折半查找插入到已排序的序列的适当位置。

三、仪器设备、材料
VSCODE + gcc.exe
四、实验（实训）步骤
代码：复制或者截图（完整）

void insertSort(int *L, int n)
{
    int i, j;
    int flag;
    for (i = 1; i <= n - 1; i++)
    {
        if (L[i] < L[i - 1])
        {
            flag = L[i];
            for (j = i - 1; L[j] > flag; j--)
            {
                L[j + 1] = L[j];
                L[j] = flag;
            }/*将L[j]=flag;语句放在for循环外会出现数据重叠，L[j-1]=flag;语句放入循环外会在首部出现一个垃圾值，在循环外L[j+1]=flag;排序正确，原因是跳出循环的过程中j--导致索引提前一位*/
        }
    }
}

void binarySort(int *num, int count)
{
    int i, j, mid;
    for (i = 1; i < count; i++) //一一对数值进行二分插入排序
    {
        if (num[i] < num[i - 1]) //判断是否符合前一个数大于后一个数，不满足则进入语句
        {
            int temp = num[i];           //定义一个变量储存我们用来判断的值
            int left = 0, right = i - 1; //
            while (left <= right)        //锁定判断值得相应位置
            {
                mid = (left + right) / 2; //mid为初始值到判断值的中间位置
                if (num[mid] < temp)      //
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                } //while循环后left,right,mid三个值相等都可以作为num的索引值常为了方便理解习惯用mid作为其索引
            }
            //只是比较次数变多了，交换次数还是一样的
            for (j = i; j > mid; j--) //将数组中数值向索引的右端i依次移动直到判断值可以插入到排序位置且不损失其它数据
            {
                num[j] = num[j - 1];
            } //循环后j=mid=left=right
            num[j] = temp;
        }
    }
}

#include <stdio.h>
int main()
{
    int L[7] = {49, 38, 65, 97, 76, 13, 27};
    int S[7] = {49, 38, 65, 97, 76, 13, 27};
    int i;
    printf("二分排序结果为：");
    binarySort(L, 7);
    for (i = 0; i < 7; i++)
    {
        printf("%d ", L[i]);
    }
    putchar(25);
    printf("n插入排序结果为：");
    insertSort(S, 7);
    for (i = 0; i < 7; i++)
    {
        printf("%d ", S[i]);
    }
    putchar(25);
    return 0;
}

五、实训记录及结果
截图：显示源文件名称

六、实训心得及体会(总结)
此次实训的目的事掌握插入排序的两种方法并加以实现，通过对不同排序的实现过程我们发现折半插入排序是对插入排序算法的一种改进，所谓排序算法过程，就是不断的依次将元素插入前面已排好序的序列中。参与排序的元素依次增加从1到i每次递归的元素依次增加但交换次数每次循环固定为一次两种排序都较为稳定。