插入排序

插入排序 在冒泡排序、选择排序编写代码之后，楼主渐渐找到了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 plaincopy 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. } 但楼主发现从后面查找插入的方式，代码复杂程度较低: [cpp] view plaincopy 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. } 四. 算法优化 插入排序中，总是先寻找插入位置，然后在实行挪动和插入过程;寻找插入位置采用顺序查找的方式(从 前向后或者从后向前)，既然需要插入的数组已经是有序的，那么可以采用二分查找来寻找插入位置， 提高算法效率，但算法的时间复杂度仍为O(n2)。 [cpp] view plaincopy 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. }