首页 > 代码库 > 插入法排序

插入法排序

2024-07-24 00:56:56   220人阅读

转自http://blog.csdn.net/cjf_iceking/article/details/7916194

 

在冒泡排序、选择排序编写代码之后，楼主渐渐找到了coding的信心，熟能生巧，就像写词唱曲之前，都得先背诵大量的诗词，熟悉各路歌曲，才能走出自己的路线，有自己的杰作。好吧，来让楼主继续进行"社会主义初级阶段"的任务，这次是插入排序。

一. 算法描述

    插入排序：插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。

以下面5个无序的数据为例：

65 27 59 64 58 （文中仅细化了第四次插入过程）

第1次插入: 27 65 59 64 58

第2次插入: 27 59 65 64 58

第3次插入: 27 59 64 65 58

第4次插入: 27 58 59 64 65

二. 算法分析

平均时间复杂度：O(n2)

空间复杂度：O(1)  (用于记录需要插入的数据)

稳定性：稳定

三. 算法实现

从前向后查找的插入排序：
[cpp] view plaincopyprint?
  1. /******************************************************** 
  2. *函数名称：InsertSort 
  3. *参数说明：pDataArray 无序数组； 
  4. *          iDataNum为无序数据个数 
  5. *说明：    插入排序 
  6. *********************************************************/  
  7. void InsertSort(int* pDataArray, int iDataNum)  
  8. {  
  9.     for (int i = 1; i < iDataNum; i++)    //从第2个数据开始插入   
  10.     {  
  11.         int j = 0;  
  12.         while (j < i && pDataArray[j] <= pDataArray[i])    //寻找插入的位置   
  13.             j++;  
  14.           
  15.         if (j < i)    //i位置之前，有比pDataArray[i]大的数，则进行挪动和插入   
  16.         {  
  17.             int k = i;  
  18.             int temp = pDataArray[i];  
  19.             while (k > j)    //挪动位置   
  20.             {  
  21.                 pDataArray[k] = pDataArray[k-1];  
  22.                 k--;  
  23.             }  
  24.             pDataArray[k] = temp;    //插入   
  25.         }  
  26.     }  
  27. }  
/*********************************************************函数名称：InsertSort*参数说明：pDataArray 无序数组；*		   iDataNum为无序数据个数*说明：    插入排序*********************************************************/void InsertSort(int* pDataArray, int iDataNum){	for (int i = 1; i < iDataNum; i++)    //从第2个数据开始插入	{		int j = 0;		while (j < i && pDataArray[j] <= pDataArray[i])    //寻找插入的位置			j++;				if (j < i)    //i位置之前，有比pDataArray[i]大的数，则进行挪动和插入		{			int k = i;			int temp = pDataArray[i];			while (k > j)    //挪动位置			{				pDataArray[k] = pDataArray[k-1];				k--;			}			pDataArray[k] = temp;    //插入		}	}}
但楼主发现从后面查找插入的方式，代码复杂程度较低：
[cpp] view plaincopyprint?
  1. /******************************************************** 
  2. *函数名称：InsertSort 
  3. *参数说明：pDataArray 无序数组； 
  4. *          iDataNum为无序数据个数 
  5. *说明：    插入排序 
  6. *********************************************************/  
  7. void InsertSort(int* pDataArray, int iDataNum)  
  8. {  
  9.     for (int i = 1; i < iDataNum; i++)    //从第2个数据开始插入   
  10.     {  
  11.         int j = i - 1;  
  12.         int temp = pDataArray[i];    //记录要插入的数据   
  13.         while (j >= 0 && pDataArray[j] > temp)    //从后向前，找到比其小的数的位置   
  14.         {  
  15.             pDataArray[j+1] = pDataArray[j];    //向后挪动   
  16.             j--;  
  17.         }  
  18.   
  19.         if (j != i - 1)    //存在比其小的数   
  20.             pDataArray[j+1] = temp;  
  21.     }  
  22. }  
/*********************************************************函数名称：InsertSort*参数说明：pDataArray 无序数组；*		   iDataNum为无序数据个数*说明：    插入排序*********************************************************/void InsertSort(int* pDataArray, int iDataNum){	for (int i = 1; i < iDataNum; i++)    //从第2个数据开始插入	{		int j = i - 1;		int temp = pDataArray[i];    //记录要插入的数据		while (j >= 0 && pDataArray[j] > temp)    //从后向前，找到比其小的数的位置		{			pDataArray[j+1] = pDataArray[j];    //向后挪动			j--;		}		if (j != i - 1)    //存在比其小的数			pDataArray[j+1] = temp;	}}

四. 算法优化

插入排序中，总是先寻找插入位置，然后在实行挪动和插入过程；寻找插入位置采用顺序查找的方式（从前向后或者从后向前），既然需要插入的数组已经是有序的，那么可以采用二分查找方法来寻找插入位置，提高算法效率，但算法的时间复杂度仍为O(n2)。

[cpp] view plaincopyprint?
  1. //查找数值iData在长度为iLen的pDataArray数组中的插入位置   
  2. int FindInsertIndex(int *pDataArray, int iLen, int iData)  
  3. {  
  4.     int iBegin = 0;  
  5.     int iEnd = iLen - 1;  
  6.     int index = -1;    //记录插入位置   
  7.     while (iBegin <= iEnd)  
  8.     {  
  9.         index = (iBegin + iEnd) / 2;  
  10.         if (pDataArray[index] > iData)  
  11.             iEnd = index - 1;  
  12.         else  
  13.             iBegin = index + 1;   
  14.     }  
  15.     if (pDataArray[index] <= iData)  
  16.         index++;  
  17.     return index;  
  18. }  
  19.   
  20. /******************************************************** 
  21. *函数名称：BinaryInsertSort 
  22. *参数说明：pDataArray 无序数组； 
  23. *          iDataNum为无序数据个数 
  24. *说明：    二分查找插入排序 
  25. *********************************************************/  
  26. void BinaryInsertSort(int* pDataArray, int iDataNum)  
  27. {  
  28.     for (int i = 1; i < iDataNum; i++)    //从第2个数据开始插入   
  29.     {  
  30.         int index = FindInsertIndex(pDataArray, i, pDataArray[i]);    //二分寻找插入的位置   
  31.           
  32.         if (i != index)    //插入位置不为i，才挪动、插入   
  33.         {  
  34.             int j = i;  
  35.             int temp = pDataArray[i];  
  36.             while (j > index)    //挪动位置   
  37.             {  
  38.                 pDataArray[j] = pDataArray[j-1];  
  39.                 j--;  
  40.             }  
  41.             pDataArray[j] = temp;    //插入   
  42.         }  
  43.     }  
  44. }  

插入法排序


联系
我们