c语言直接插入排序


插入排序

插入排序的基本思想是按关键字的大小将记录插入到一个有序的文件的适当位置,并且插入后使文件仍然有序。
因为源文件是有序的,再插入一个文件时,需要采用顺序查找的方式 或折半查找法,找出应该插入的位置。


直接插入排序 原理

直接插入的排序方法是最简单的排序方法之一。
直接插入排序的基本思想:
每一次将一个待排序的记录按其关键字值的大小插入到已经排序的文件中的适当位置上,知道全部插入完成。


例:
记录存放在r[1…n]之中,
先把整个数组划分为两个部分,r[1..i-1] 已排好序的部分
r[i,n] 是没有进行排序的数据。
插入排序对未排序中的r[i]插入到r[1..i-1]中,使r[1..i-1]成为有序,r[i]的每次插入操作都完成一次排序,随着有序区的不断扩大,最终使r[1 ..n]全部有序。


插入排序实现方法

void insertSort(数据类型 r[],int n)
  {
     for(i=2;i <= n;i++){
       if(r[i] <  r[i-1])
        {
          r[0] = r[i]; //引入临时缓冲变量r[0]
          for(j =i-1;r[0] < r[j];--j)
              r[j+1] = r[j];
              r[j+1] =r[0];
        }
   
     }
    
  }
 
 

例:
数组
19 , 01 , 23 ,17 , 19 , 55 , 84 ,15
第一次 {01 19} 23 17 ...
第二次 {01 19 23 } 17 19 55 ..
第三次 {01 17 19 23} 19 55 84 15
第四次 {01 17 19 19 23} 55 84 15
第五次 {01 17 19 19 23 55 } 84 15
第六次 {01 17 19 19 23 55 84 } 15
第七次 {01 15 17 19 19 23 55 84 }