发布日期:2015-12-31 10:47 来源: 标签: 编程语言 C教程 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<stdio.h>
#include<stdlib.h>
#define N 8
void insert_sort(int a[],int n);
//插入排序实现,这里按从小到大排序
void insert_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]) && (j<i))
{
j++;
}
//将元素插入到正确的位置
if(i != j)  //如果i==j,说明a[i]刚好在正确的位置
{
int temp = a[i];
for(int k = i; k > j; k--)
{
a[k] = a[k-1];
}
a[j] = temp;
}
}
}
int  main()
{
int num[N] = {89, 38, 11, 78, 96, 44, 19, 25};
insert_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语言是一种结构化语言。它层次清晰,便于按模块化方式组织程序,易于调试和维护。