C语言插入排序算法及实例代码
插入排序是排序算法的一种,下面小编为大家整理了C 语言插入排序算法及实例代码,希望能帮到大家!
这里以从小到大排序为例进行讲解。
基本思想及举例说明
插入排序的基本思想是,将元素逐个添加到已经排序好的数组中去,同时要求,插入的元素必须在正确的位置,这样原来排序好的数组是仍然有序的。
在实际使用中,通常是排序整个无序数组,所以把这个无序数组分为两部分排序好的子数组和待插入的元素。第一轮时,将第一个元素作为排序好的子数组,插入第二个元素;第二轮,将前两个元素作为排序好的数组,插入第三个元素。以此类推,第i轮排序时,在前i个元素的子数组中插入第i+1个元素。直到所有元素都加入排序好数组。
下面,以对 3 2 4 1 进行选择排序说明插入过程,使用j记录元素需要插入的`位置。排序目标是使数组从小到大排列。
第1轮
[ 3 ] [ 2 4 1 ] (最初状态,将第1个元素分为排序好的子数组,其余为待插入元素)
[ 3 ] [ 2 4 1 ] (由于3>2,所以待插入位置j=1)
[ 2 3 ] [ 4 1 ] (将2插入到位置j)
第2轮
[ 2 3 ] [ 4 1 ] (第1轮排序结果)
[ 2 3 ] [ 4 1 ] (由于2<4,所以先假定j=2)
[ 2 3 ] [ 4 1 ] (由于3<4,所以j=3)
[ 2 3 4 ] [ 1 ] (由于4刚好在位置3,无需插入)
第3轮
[ 2 3 4 ] [ 1 ] (第2轮排序结果)
[ 2 3 4 ] [ 1 ] (由于1<2,所以j=1)
[1 2 3 4 ] (将1插入位置j,待排序元素为空,排序结束)
算法总结及实现
选择排序对大小为N的无序数组R[N]进行排序,进行N-1轮选择过程。首先将第1个元素作为已经排序好的子数组,然后将剩余的N-1个元素,逐个插入到已经排序好子数组;。因此,在第 i轮排序时,前i个元素总是有序的,将第i+1个元素插入到正确的位置。
#include#include#define N 8void _sort(int a[],int n);//插入排序实现,这里按从小到大排序void _sort(int a[],int n)//n为数组a的元素个数{ //进行N-1轮插入过程 for(int i=1; i<n; i++) { //首先找到元素a[i]需要插入的位置 int j=0; while( (a[j]<a[i]) && (jj; k--) { a[k] = a[k-1]; } a[j] = temp; } }}int main(){ int num[N] = {89, 38, 11, 78, 96, 44, 19, 25}; _sort(num, N); for(int i=0; i<N; i++) printf("%d ", num[i]); printf("n"); system("pause"); return 0;}
注意:插入排序是一种稳定的排序算法,不会改变原有序列中相同数字的顺序。
插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。
-
C/C++面试常考关键字
导语:结构式语言的显著特点是代码及数据的分隔化,即程序的各个部分除了必要的信息交流外彼此独立。下面就由小编为大家介绍一下C/C++面试常考关键字,欢迎大家阅读!C/C++面试常考关键字总结:ic关键字的作用?1)、static申明的变量为静态全局变量,该变量存储在静态数据区,...
-
C语言中文件操作详解及实例代码
在文件操作中除了打开操作以及读写操作,还有几种比较常见的操作。以下是本站小编搜索整理的关于这些操作中涉及到的函数,,需要的朋友可以参考本文!想了解更多相关信息请持续关注我们应届毕业生考试网!一.移动位置指针的函数rewind函数和fseek函数,这两个函数的原...
-
2017全国计算机二级《C语言》考试题及答案
在备考复习阶段,需通过大量试题练习,加深对考点的理解和掌握。以下是本站小编搜索整理的一份全国计算机二级《C语言》考试题及答案,供参考练习,希望对大家有所帮助!想了解更多相关信息请持续关注我们应届毕业生考试网!一、选择题1).我们所写的每条C语句,经过编译最...
-
C语言scanf函数应用问题解答
C语言的输入是由系统提供的库函数完成的。scanf函数是C语言中最常用且功能最强的输入函数,但该函数如使用不慎,就会出现错误或得不到预想的结果。以下结果都是基于VC++6.0运行环境。一、格式说明符和输入项的三对应(类型、个数、顺序)scanf函数格式中的格式说明(“%...