随手小代码——在归并排序中对小数组采用插入排序

请通过右侧公告中的“联系邮箱（wlsandwho@foxmail.com）”联系我

未经作者授权勿用于学术性引用。

未经作者授权勿用于商业出版、商业印刷、商业引用以及其他商业用途。　　　　　　　　　　　　　　　　

本文不定期修正完善，为保证内容正确，建议移步原文处阅读。 <--------总有一天我要自己做一个模板干掉这只土豆

本文链接：http://www.cnblogs.com/wlsandwho/p/4684198.html

耻辱墙：http://www.cnblogs.com/wlsandwho/p/4206472.html

=======================================================================

这个思考题好奇怪的样子，还是先写写代码吧。

  1 #include <iostream>
  2 
  3 using namespace std;
  4 
  5 void InsertionSortByWLS(int nArray[],int nLen)
  6 {
  7     int nTemp=0;
  8 
  9     for (int nIndex=1;nIndex<nLen;nIndex++)
 10     {
 11         nTemp=nArray[nIndex];
 12 
 13         int nCmpIndex;
 14         for (nCmpIndex=nIndex;nCmpIndex>0 && nArray[nCmpIndex-1]>nTemp;nCmpIndex--)
 15         {
 16             nArray[nCmpIndex]=nArray[nCmpIndex-1];
 17         }
 18 
 19         if (nCmpIndex<nIndex)
 20         {        
 21             nArray[nCmpIndex]=nTemp;
 22         }
 23     }
 24 }
 25 
 26 void MergeTwoParts(int nArr[],int nPos1,int nPos2,int nPos3)
 27 {
 28     int nSize=nPos3-nPos1+1;
 29     int* nTempArr=new int[nSize];
 30     memset(nTempArr,0,sizeof(int)*nSize);
 31 
 32     int nLeftIndex=nPos1;
 33     int nRightIndex=nPos2;
 34 
 35     int nTempIndex=0;
 36 
 37     while(nLeftIndex<nPos2 && nRightIndex<=nPos3)
 38     {
 39         if (nArr[nLeftIndex]<=nArr[nRightIndex])
 40         {
 41             nTempArr[nTempIndex++]=nArr[nLeftIndex++];
 42         }
 43         else
 44         {
 45             nTempArr[nTempIndex++]=nArr[nRightIndex++];
 46         }
 47     }
 48 
 49     while (nRightIndex<=nPos3)
 50     {
 51         nTempArr[nTempIndex++]=nArr[nRightIndex++];
 52     }
 53 
 54     while (nLeftIndex<nPos2)
 55     {
 56         nTempArr[nTempIndex++]=nArr[nLeftIndex++];
 57     }
 58 
 59     memcpy(nArr+nPos1,nTempArr,nSize*sizeof(int));
 60 
 61     delete[] nTempArr;
 62 }
 63 
 64 void MergeSortViaInsertionSortByWLS(int nArr[],int nStartPos,int nEndPos,int nLenforIS)
 65 {
 66 //     if (nStartPos<nEndPos)
 67 //     {    
 68 //         int nDivide=(nStartPos+nEndPos)/2;
 69 //
 70 //         MergeSortByWLS(nArr,nStartPos,nDivide);
 71 //         MergeSortByWLS(nArr,nDivide+1,nEndPos);
 72 //
 73 //         MergeTwoParts(nArr,nStartPos,nDivide+1,nEndPos);
 74 //     }
 75 
 76     if (nStartPos<nEndPos)
 77     {
 78         int nDivide=(nStartPos+nEndPos)/2;
 79 
 80         if (nDivide-nStartPos<nLenforIS  && nStartPos<nDivide)
 81         {
 82             InsertionSortByWLS(nArr+nStartPos,nDivide-nStartPos+1);
 83         }
 84         else
 85         {
 86             MergeSortViaInsertionSortByWLS(nArr,nStartPos,nDivide,nLenforIS);
 87         }
 88 
 89         if (nEndPos-nDivide+1<nLenforIS && nDivide<nEndPos )
 90         {
 91             InsertionSortByWLS(nArr+nDivide+1,nEndPos-nDivide);
 92         }
 93         else
 94         {
 95             MergeSortViaInsertionSortByWLS(nArr,nDivide+1,nEndPos,nLenforIS);
 96         }
 97 
 98         MergeTwoParts(nArr,nStartPos,nDivide+1,nEndPos);
 99     }
100 }
101 
102 
103 int _tmain(int argc, _TCHAR* argv[])
104 {
105     int nTestArray2[13]={99,35,50,10,101,5,66,100,6,88,22,111,33};
106 
107     MergeSortViaInsertionSortByWLS(nTestArray2,0,12,5);
108 
109     for (int i=0;i<13;i++)
110     {
111         cout<<nTestArray2[i]<<" ";
112     }
113     cout<<endl;
114 
115     return 0;
116 }

这样应该更好点

 1 void MergeSortViaInsertionSortByWLS2(int nArr[],int nStartPos,int nEndPos,int nLenforIS)
 2 {
 3     if (nStartPos>=nEndPos)
 4     {
 5         return;
 6     }
 7 
 8     if (nEndPos-nStartPos<nLenforIS)
 9     {
10         InsertionSortByWLS(nArr,nEndPos-nStartPos+1);
11     }
12     else
13     {
14         int nDivide=(nStartPos+nEndPos)/2;
15 
16         MergeSortViaInsertionSortByWLS(nArr,nStartPos,nDivide,nLenforIS);
17         MergeSortViaInsertionSortByWLS(nArr,nDivide+1,nEndPos,nLenforIS);
18 
19         MergeTwoParts(nArr,nStartPos,nDivide+1,nEndPos);
20     }
21 }

测试（添加windows.h）

 1 int _tmain(int argc, _TCHAR* argv[])
 2 {
 3     int nTestArray2[27]={3,1,5,9,6,7,2,8,4,0,99,77,88,66,55,32,21,65,54,78,98,51,53,65,95,15,35};
 4 
 5     LARGE_INTEGER nBeginTime;
 6     LARGE_INTEGER nEndTime;
 7 
 8     QueryPerformanceCounter(&nBeginTime); // 开始计时
 9 
10     MergeSortViaInsertionSortByWLS(nTestArray2,0,26,9);
11 
12     QueryPerformanceCounter(&nEndTime);// 结束计时
13     cout <<nEndTime.QuadPart-nBeginTime.QuadPart<< endl;
14 
15 
16     for (int i=0;i<27;i++)
17     {
18         cout<<nTestArray2[i]<<" ";
19     }
20     cout<<endl;
21 
22     return 0;
23 }