C++常用排序法分析

1、【Word版本下载可任意编辑】 C+常用排序法分析 首先介绍一个计算时间差的函数，它在 void BubbleSort(int* pData,int Count) int iTemp; for(int i=1;i=i;j-) if(pData iTemp = pData; pData = pData; pData = iTemp; void main() int data = 10,9,8,7,6,5,4; BubbleSort(data,7); for (int i=0;i10,9,7,8-10,7,9,8-7,10,9,8(交换3次) 第二轮：7,10,9,8-7,10,8,9-7,8,1

2、0,9(交换2次) 轮：7,8,10,9-7,8,9,10(交换1次) 循环次数：6次 交换次数：6次 其他： 轮：8,10,7,9-8,10,7,9-8,7,10,9-7,8,10,9(交换2次) 第二轮：7,8,10,9-7,8,10,9-7,8,10,9(交换0次) 轮：7,8,10,9-7,8,9,10(交换1次) 循环次数：6次 交换次数：3次 上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换， 显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+.+n-1。 写成公式就是1/2*(n-1)*n。 现在注意，我们给出O方

3、法的定义： 若存在一常量K和起点n0，使当n=n0时，有f(n) void ExchangeSort(int* pData,int Count) int iTemp; for(int i=0;i9,10,8,7-8,10,9,7-7,10,9,8(交换3次) 第二轮：7,10,9,8-7,9,10,8-7,8,10,9(交换2次) 轮：7,8,10,9-7,8,9,10(交换1次) 循环次数：6次 交换次数：6次 其他： 轮：8,10,7,9-8,10,7,9-7,10,8,9-7,10,8,9(交换1次) 第二轮：7,10,8,9-7,8,10,9-7,8,10,9(交换1次) 轮：7,8,

4、10,9-7,8,9,10(交换1次) 循环次数：6次 交换次数：3次 从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样 也是1/2*(n-1)*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以 只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。 3.选择法： 现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下） 这种方法类似我们人为的排序习惯：从数据中选择的同个值交换，在从省下的部分中 选择的与第二个交换，这样往复下去。 #include (iTemp=9)10,9,8,7-(iTemp=

5、8)10,9,8,7-(iTemp=7)7,9,8,10(交换1次) 第二轮：7,9,8,10-7,9,8,10(iTemp=8)-(iTemp=8)7,8,9,10(交换1次) 轮：7,8,9,10-(iTemp=9)7,8,9,10(交换0次) 循环次数：6次 交换次数：2次 其他： 轮：8,10,7,9-(iTemp=8)8,10,7,9-(iTemp=7)8,10,7,9-(iTemp=7)7,10,8,9(交换1次) 第二轮：7,10,8,9-(iTemp=8)7,10,8,9-(iTemp=8)7,8,10,9(交换1次) 轮：7,8,10,9-(iTemp=9)7,8,9,10(

6、交换1次) 循环次数：6次 交换次数：3次 遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。 我们来看他的交换。由于每次外层循环只产生交换（只有一个值）。所以f(n) void InsertSort(int* pData,int Count) int iTemp; int iPos; for(int i=1;i=0) & (iTemp pData = pData; iPos-; pData = iTemp; void main() int data = 10,9,8,7,6,5,4; InsertSort(data,7); for (int i=0;i9,

7、10,8,7(交换1次)(循环1次) 第二轮：9,10,8,7-8,9,10,7(交换1次)(循环2次) 轮：8,9,10,7-7,8,9,10(交换1次)(循环3次) 循环次数：6次 交换次数：3次 其他： 轮：8,10,7,9-8,10,7,9(交换0次)(循环1次) 第二轮：8,10,7,9-7,8,10,9(交换1次)(循环2次) 轮：7,8,10,9-7,8,9,10(交换1次)(循环1次) 循环次数：4次 交换次数：2次 上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中的，其实不是， 因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环

8、的次数f(n) void run(int* pData,int left,int right) int i,j; int middle,iTemp; i = left; j = right; middle = pData; /求中间值 do while(pDatai)，递归右半边 if(righti) run(pData,i,right); void QuickSort(int* pData,int Count) run(pData,0,Count-1); void main() int data = 10,9,8,7,6,5,4; QuickSort(data,7); for (int i=

9、0;i void Bubble2Sort(int* pData,int Count) int iTemp; int left = 1; int right =Count -1; int t; do /正向的部分 for(int i=right;i=left;i-) if(pData iTemp = pData; pData = pData; pData = iTemp; t = i; left = t+1; /反向的部分 for(i=left;i int ShellPass(int * array,int d) /一趟增量为d的希尔插入排序 int temp; int k=0; for(int

10、 i=d+1;i1); cout(CMyData& data ); private: char* m_strDatamember; int m_iDataSize; ; / MyData.cpp文件 / CMyData:CMyData(): m_iIndex(0), m_iDataSize(0), m_strDatamember(NULL) CMyData:CMyData() if(m_strDatamember != NULL) delete m_strDatamember; m_strDatamember = NULL; CMyData:CMyData(int Index,char* st

11、rData): m_iIndex(Index), m_iDataSize(0), m_strDatamember(NULL) m_iDataSize = strlen(strData); m_strDatamember = new char; strcpy(m_strDatamember,strData); CMyData& CMyData:operator =(CMyData &SrcData) m_iIndex = SrcData.m_iIndex; m_iDataSize = SrcData.GetDataSize(); m_strDatamember = new char; strcp

12、y(m_strDatamember,SrcData.GetData(); return *this; bool CMyData:operator (CMyData& data ) return m_iIndexdata.m_iIndex; / / /主程序部分 #include void run(T* pData,int left,int right) int i,j; T middle,iTemp; i = left; j = right; /下面的比较都调用我们重载的操作符函数 middle = pData; /求中间值 do while(pDatai)，递归右半边 if(righti) run(pData,i,right); template void QuickSort(T* pData,int Count) run(pData,0,Count-1); void main() CMyData data = CMyData(8,xulion), CMyData(7,sanzoo), CMyDa