学步园

#include <algorithm><br /> #include <cmath><br /> #include <time.h><br /> #include <Windows.h><br /> #include <iostream><br /> using namespace std;<br /> typedef long long int _INT64;<br /> const unsigned len = 10000;<br /> _INT64 x[len] = {0};<br /> void getRandArrayNoRepeat()<br /> {<br /> for (unsigned i=0; i<len; ++i)<br /> x[i] = i;<br /> random_shuffle(x, x+len);<br /> }<br /> void insertSort1()<br /> {<br /> for (unsigned i=1; i<len; ++i)<br /> for (unsigned j=i; j>0 && x[j-1]>x[j]; --j)<br /> {<br /> _INT64 t = x[j];<br /> x[j] = x[j-1];<br /> x[j-1] = t;<br /> }<br /> }<br /> void insertSort2()<br /> {<br /> for (unsigned i=1; i<len; ++i)<br /> {<br /> _INT64 t = x[i];<br /> unsigned j;<br /> for (j=i; j>0 && x[j-1]>t; --j)<br /> x[j] = x[j-1];<br /> x[j] = t;<br /> }<br /> }<br /> int main()<br /> {<br /> //test1<br /> getRandArrayNoRepeat();<br /> DWORD stime = GetTickCount();<br /> insertSort1();<br /> DWORD test1 = GetTickCount();<br /> cout << "insertSort1's running time = " << test1 - stime << " ms." <<'/n';<br /> //test2<br /> getRandArrayNoRepeat();<br /> stime = GetTickCount();<br /> insertSort2();<br /> DWORD test2 = GetTickCount();<br /> cout << "insertSort2's running time = " << test2 - stime << " ms." <<'/n'<br /> return 0;<br /> } 

insertSort1's running time = 266 ms.

insertSort2's running time = 156 ms.

请按任意键继续. . .

insertSort2()要比insertSort1()快15%

但是当数组大小变成100万个时，排序时间几乎需要1个小时。

所以，下一篇准备测试一下快速排序算法