插入排序算法详解及实现

偏执的太偏执、 2022-08-23 05:51 165阅读 0赞

插入排序相对冒泡排序而言是一种较为快捷方便的排序算法。

冒泡排序：[http://blog.csdn.net/llzk\_/article/details/51547923][http_blog.csdn.net_llzk_article_details_51547923]

插入排序原理很简单，讲一组数据分成两组，我分别将其称为有序组与待插入组。每次从待插入组中取出一个元素，与有序组的元素进行比较，并找到合适的位置，将该元素插到有序组当中。就这样，每次插入一个元素，有序组增加，待插入组减少。直到待插入组元素个数为0。当然，插入过程中涉及到了元素的移动。

为了排序方便，我们一般将数据第一个元素视为有序组，其他均为待插入组。

下面以升序为例进行一次图解：

![Center][]

代码为：

#include<stdio.h>
      void InsertionSort(int *num,int n) 
      {
      	int i = 0;
      	int j = 0;
      	int tmp = 0;
      	for(i = 1;i<n;i++)
      	{
          tmp = num[i];//从待插入组取出第一个元素。 
    	  j = i-1; //i-1即为有序组最后一个元素（与待插入元素相邻）的下标 
    	  while(j>=0&&tmp<num[j])  //注意判断条件为两个，j>=0对其进行边界限制。第二个为插入判断条件 
    	  {
    	    num[j+1] = num[j];//若不是合适位置，有序组元素向后移动 
    		j--; 
    	  }
    	  num[j+1] = tmp;//找到合适位置，将元素插入。 
    	}
      }
      int main() 
      {
      	int i = 0;
      	int num[8]={9,3,4,2,6,7,5,1};
      	InsertionSort(num,8); 
      	/*这个函数必须知道元素的个数，所以将元素个数传入。
    	有心者可以在函数内部用sizeof求出元素个数 */
      	for(i=0;i<8;i++)
      	{
         	printf("%d ",num[i]);
    	}
      	return 0;
      }

执行结果：

![Center 1][]

[http_blog.csdn.net_llzk_article_details_51547923]: http://blog.csdn.net/llzk_/article/details/51547923
[Center]: /images/20220721/efd2c38ede6347ceb662f1498a95c4b6.png
[Center 1]: /images/20220721/7e2794b797994905a4ff723209a84875.png