C语言之直接插入排序法（2）

矫情吗；* 2022-08-07 07:49 164阅读 0赞

直接插入排序(straight insertion sort)的做法是：

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序属于稳定的排序，最坏 [时间复杂性][Link 1]为O(n^2)， [空间复杂度][Link 2]为O(1)。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

###  基本思想 ###

待排序记录 R1，R2，… ，Rn–1, Rn

第一步：R1

第二步：(R1 ), R2

第三步：(R1 , R2), R3

……

第 j 步：(R1，R2，… ，Rj–1), Rj

……

第 n 步: (R1，R2，… ，Rn–1), Rn．

例：j=5

原有序表中关键词比Rj大的记录数：dj

比较次数：dj+1 移动次数： dj+2

### 过程实例 ###

例：

原有序表：(9 15 23 28 37) 20

找插入位置 : (9 15 ^ 23 28 37) 20

新有序表: (9 15 20 23 28 37)

### 算法实现代码 ###

\#include "stdafx.h"  
  
//直接插入排序  
void Inert\_Sort(int \*a,int len)  
\{  
 int i,j,k,temp;  
 for(i=1;i<len;i++)  
 \{  
 temp=\*(a+i);  
 for(j=i-1;j>=0&&temp<\*(a+j);j--)  
 \{  
 //if(temp<\*(a+j))  
 \*(a+j+1)=\*(a+j);  
 \}  
 \*(a+j+1)=temp;  
 \}  
\}  
  
int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{  
 int a\[\]=\{12,3,23,4,54,21,65,23,32,55\};  
 int len=sizeof(a)/sizeof(int);  
 int i;  
  
 for(i=0;i<len;i++)  
 printf("%d\\t",a\[i\]);  
  
  Inert\_Sort(a,len);  
  
 for(i=0;i<len;i++)  
 printf("%d\\t",a\[i\]);  
  
 return 0;  
\}

[Link 1]: http://baike.baidu.com/view/1858612.htm
[Link 2]: http://baike.baidu.com/view/540497.htm