目录
插入排序法的介绍
什么是插入排序法?
稳定性分析
插入排序基本思想
例子分析
实现代码
运行结果
插入排序法的介绍
什么是插入排序法?
插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 ;
稳定性分析
如果待排序的序列中存在两个或两个以上具有相同关键词的数据,排序后这些数据的相对次序保持不变,即它们的位置保持不变,通俗地讲,就是两个相同的数的相对顺序不会发生改变,则该算法是稳定的;如果排序后,数据的相对次序发生了变化,则该算法是不稳定的。关键词相同的数据元素将保持原有位置不变,所以该算法是稳定的;
插入排序基本思想
插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入,直到整个序列排为有序的过程,称为插入排序;
如图
例子分析
如对数列 5 2 4 1 插入排序
第一次:用数列下标为1的数 2与5比较,5>2,所以交换位置,数列变为 2 5 4 1;
第一次后的数列为 2 5 4 1
第二次:然后下标增加,用下标为2的数 4与5比较,4<5,所以交换位置,变为 2 4 5 1 ,然后4与2比较,4>2,不用交换;
第二次后的数列 为 2 4 5 1
第三次:用下标为3的数 1 与5比较,5>1,所以交换,变为 2 4 1 5,然后1与4比较,4>1,交换,变为 2 1 4 5,再用1与2比较,2>1,交换,变为 1 2 4 5;
最后排完数列变为 1 2 4 5
实现代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void Print(int arr[], int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%d ",arr[i]); //结果打印函数
}
printf("\n");
}
void Sort_arr(int arr[],int n) //排序的函数
{
int tmp = 0;
int i = 0;
int j = 0;
for (i = 1; i < n; i++)
{
tmp = arr[i];
for (j = i - 1; j >= 0; j--)
{
if (tmp > arr[j])
{
break;
}
else
{
arr[j + 1] = arr[j];
}
}
arr[j+1] = tmp;
Print(arr, 10); //打印排序过程
}
}
int main()
{
int a[10] = { 12,18,2,6,21,8,10,-6,11,9};
Sort_arr(a, 10);
Print(a,10);
return 0;
}
运行结果
文章来源:https://www.toymoban.com/news/detail-480119.html
文章来源地址https://www.toymoban.com/news/detail-480119.html
到了这里,关于直接插入排序--C语言(附详细代码)(附图详解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!