用系统计时器算时间复杂度代码,C代码库,德仔网

代码语言
代码分类
【C】用系统计时器算时间复杂度
作者:Dezai.CN / 发布于2011/8/1/ 527
<div><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">用系统计时器算时间复杂度。</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">
#include</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">stdio.h</span><span style="color: rgb(0,0,0)">></span><span style="color: rgb(0,0,0)">
#include</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">stdlib.h</span><span style="color: rgb(0,0,0)">></span><span style="color: rgb(0,0,0)">
#include</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,255)">string</span><span style="color: rgb(0,0,0)">.h</span><span style="color: rgb(0,0,0)">></span><span style="color: rgb(0,0,0)">
#include</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">time.h</span><span style="color: rgb(0,0,0)">></span><span style="color: rgb(0,0,0)">
</span><span style="color: rgb(0,0,255)">#define</span><span style="color: rgb(0,0,0)"> LIST_INIT_SIZE 50000</span><span style="color: rgb(0,0,0)">
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> bj1,yd1,n;
clock_t start_t,end_t;
typedef </span><span style="color: rgb(0,0,255)">struct</span><span style="color: rgb(0,0,0)"> 
{
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> key; 
}ElemType;
typedef </span><span style="color: rgb(0,0,255)">struct</span><span style="color: rgb(0,0,0)"> 
{
ElemType </span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">elem;
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> length;
}SqList;
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> addlist(SqList </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">L)
{
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i;
a: printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">请输入你要输入的个数:</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">);
scanf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">%d</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">,</span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">n);
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(n</span><span style="color: rgb(0,0,0)">></span><span style="color: rgb(128,0,128)">50000</span><span style="color: rgb(0,0,0)">)
{
 printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">超出范围重新输入!!!\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">);
 </span><span style="color: rgb(0,0,255)">goto</span><span style="color: rgb(0,0,0)"> a;
}
L.elem</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">(ElemType</span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">)malloc(LIST_INIT_SIZE</span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,255)">sizeof</span><span style="color: rgb(0,0,0)">(ElemType));
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(</span><span style="color: rgb(0,0,0)">!</span><span style="color: rgb(0,0,0)">L.elem)exit(</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">);
L.length</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;
</span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">;i</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">n</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">;i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">)
{
b: L.elem[i].key</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">rand();
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(L.elem[i].key</span><span style="color: rgb(0,0,0)">></span><span style="color: rgb(128,0,128)">30000</span><span style="color: rgb(0,0,0)">)</span><span style="color: rgb(0,0,255)">goto</span><span style="color: rgb(0,0,0)"> b;
 </span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">L.length;
}
}
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> SelectSort(SqList </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">L)</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">选择</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">{
start_t</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">clock();
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i,j,k,bj</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">,yd</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;
</span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">;i</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">L.length;i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">)
{
 k</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">i;
 </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(j</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">i</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">;j</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">L.length;j</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">)
 {
 bj</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(L.elem[j].key</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">L.elem[k].key)k</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">j;
 }
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(i</span><span style="color: rgb(0,0,0)">!=</span><span style="color: rgb(0,0,0)">k)
 {
 L.elem[</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">].key</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[i].key;
 L.elem[i].key</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[k].key;
 L.elem[k].key</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">].key;
 yd</span><span style="color: rgb(0,0,0)">+=</span><span style="color: rgb(128,0,128)">3</span><span style="color: rgb(0,0,0)">;
 }
}
end_t</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">clock();
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">比较次数为 %d移动次数为 %d\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">,bj,yd);
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">排序用时为 %f\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">,</span><span style="color: rgb(0,0,255)">float</span><span style="color: rgb(0,0,0)">(end_t</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(0,0,0)">start_t)</span><span style="color: rgb(0,0,0)">/</span><span style="color: rgb(0,0,0)">CLK_TCK);
}
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> qipao(SqList </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">L)</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">起泡</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">{
start_t</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">clock();
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">,j,bj</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">,yd</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;
</span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)">(i</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">L.length)
{
 </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(j</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">;j</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">L.length;j</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">)
 {
 bj</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(L.elem[j].key</span><span style="color: rgb(0,0,0)">></span><span style="color: rgb(0,0,0)">L.elem[j</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">].key)
 {
 L.elem[</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">].key</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[j].key;
 L.elem[j].key</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[j</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">].key;
 L.elem[j</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">].key</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">].key;
 yd</span><span style="color: rgb(0,0,0)">+=</span><span style="color: rgb(128,0,128)">3</span><span style="color: rgb(0,0,0)">;
 }
 }
 i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
}
end_t</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">clock();
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">比较次数为 %d移动次数为 %d\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">,bj,yd);
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">排序用时为 %f\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">,</span><span style="color: rgb(0,0,255)">float</span><span style="color: rgb(0,0,0)">(end_t</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(0,0,0)">start_t)</span><span style="color: rgb(0,0,0)">/</span><span style="color: rgb(0,0,0)">CLK_TCK);
}
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> InsertSort(SqList </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">L)</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">直接插入</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">{
start_t</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">clock();
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i,j,yd</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">,bj</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;
</span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">2</span><span style="color: rgb(0,0,0)">;i</span><span style="color: rgb(0,0,0)"><=</span><span style="color: rgb(0,0,0)">L.length;i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">)
{
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(L.elem[i].key</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">L.elem[i</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">].key)
 {
 L.elem[</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">].key</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[i].key;
 yd</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 j</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">i</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">;
 bj</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)">(L.elem[</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">].key</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">L.elem[j].key)
 {
 L.elem[j</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">].key</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[j].key;
 j</span><span style="color: rgb(0,0,0)">--</span><span style="color: rgb(0,0,0)">;
 yd</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 bj</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 }
 L.elem[j</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">].key</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">].key;
 yd</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 }
}
end_t</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">clock();
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">比较次数为 %d移动次数为 %d\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">,bj,yd);
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">排序用时为 %f\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">,</span><span style="color: rgb(0,0,255)">float</span><span style="color: rgb(0,0,0)">(end_t</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(0,0,0)">start_t)</span><span style="color: rgb(0,0,0)">/</span><span style="color: rgb(0,0,0)">CLK_TCK);
}
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> xier(SqList </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">L)</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">希尔</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">{
start_t</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">clock();
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i,d</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.length</span><span style="color: rgb(0,0,0)">/</span><span style="color: rgb(128,0,128)">2</span><span style="color: rgb(0,0,0)">,j,w</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">,k,yd</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">,bj</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;
</span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)">(w</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">d)
{
 w</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">w;i</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">L.length;i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">i</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)">d)
 {
 k</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">i;
 </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(j</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">i</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)">d;j</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">L.length;j</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">j</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)">d)
 {
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(L.elem[i].key</span><span style="color: rgb(0,0,0)">></span><span style="color: rgb(0,0,0)">L.elem[j].key)
 {
 k</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">j;
 bj</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 }
 }
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(i</span><span style="color: rgb(0,0,0)">!=</span><span style="color: rgb(0,0,0)">k)
 {
 L.elem[</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">].key</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[i].key;
 L.elem[i].key</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[k].key;
 L.elem[k].key</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">].key;
 yd</span><span style="color: rgb(0,0,0)">+=</span><span style="color: rgb(128,0,128)">3</span><span style="color: rgb(0,0,0)">;
 }
 w</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 }
 d</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">d</span><span style="color: rgb(0,0,0)">/</span><span style="color: rgb(128,0,128)">2</span><span style="color: rgb(0,0,0)">;
 w</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">;
}
end_t</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">clock();
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">比较次数为 %d移动次数为 %d\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">,bj,yd);
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">排序用时为 %f\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">,</span><span style="color: rgb(0,0,255)">float</span><span style="color: rgb(0,0,0)">(end_t</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(0,0,0)">start_t)</span><span style="color: rgb(0,0,0)">/</span><span style="color: rgb(0,0,0)">CLK_TCK);
}


</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> BeforeSort()
{
yd1</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">,bj1</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;
}
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> display(</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> m,</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> n)
{
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">比较次数为 %d移动次数为 %d\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">,m,n);
}
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> Partition(SqList </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">L,</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> low,</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> high)</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">快速排序 </span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">{
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> pivotkey;
L.elem[</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[low];
yd1</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
pivotkey</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[low].key;
</span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)"> (low</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">high) 
{
 yd1</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)">(low</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">high</span><span style="color: rgb(0,0,0)">&&</span><span style="color: rgb(0,0,0)">L.elem[high].key</span><span style="color: rgb(0,0,0)">>=</span><span style="color: rgb(0,0,0)">pivotkey)
 </span><span style="color: rgb(0,0,0)">--</span><span style="color: rgb(0,0,0)">high;
 L.elem[low]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[high];
 bj1</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 yd1</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)"> (low</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">high</span><span style="color: rgb(0,0,0)">&&</span><span style="color: rgb(0,0,0)">L.elem[low].key</span><span style="color: rgb(0,0,0)"><=</span><span style="color: rgb(0,0,0)">pivotkey)
 </span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">low;
 L.elem[high]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[low];
 bj1</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 yd1</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
}
L.elem[low]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">L.elem[</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">];
yd1</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
</span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> low;
}
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> QSort(SqList </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">L,</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> low,</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> high)
{ 
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> pivotloc;
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(low</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">high)
{
 pivotloc</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">Partition(L,low,high);
 QSort(L,low,pivotloc</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">);
 QSort(L,pivotloc</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">,high);
}
}
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> QuickSort(SqList </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">L)
{
start_t</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">clock();
BeforeSort();
QSort(L,</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">,L.length);
display(yd1,bj1);
end_t</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">clock();
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">排序用时为 %f\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">,</span><span style="color: rgb(0,0,255)">float</span><span style="color: rgb(0,0,0)">(end_t</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(0,0,0)">start_t)</span><span style="color: rgb(0,0,0)">/</span><span style="color: rgb(0,0,0)">CLK_TCK);
}
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> Merge(ElemType R[],ElemType R1[],</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> low,</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> m,</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> high)</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">归并</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,0)">{
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">low, j</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">m</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">, k</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">low;
</span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)">(i</span><span style="color: rgb(0,0,0)"><=</span><span style="color: rgb(0,0,0)">m</span><span style="color: rgb(0,0,0)">&&</span><span style="color: rgb(0,0,0)">j</span><span style="color: rgb(0,0,0)"><=</span><span style="color: rgb(0,0,0)">high)
{
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(R[i].key</span><span style="color: rgb(0,0,0)"><=</span><span style="color: rgb(0,0,0)">R[j].key)
 {
 bj1</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 R1[k]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">R[i];
 yd1</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 k</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 }
 </span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)">
 {
 bj1</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 R1[k]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">R[j];
 yd1</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 j</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 k</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 }
}
</span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)">(i</span><span style="color: rgb(0,0,0)"><=</span><span style="color: rgb(0,0,0)">m)
{
 R1[k]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">R[i];
 yd1</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 k</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
}
</span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)">(j</span><span style="color: rgb(0,0,0)"><=</span><span style="color: rgb(0,0,0)">high)
{
 R1[k]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">R[j];
 yd1</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 j</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 k</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
}
}
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> MergePass(ElemType R[],ElemType R1[],</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> length, </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> n)
{ 
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">,j;
</span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)">(i</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">2</span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">length</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">n)
{ 
 Merge(R,R1,i,i</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)">length</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">,i</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">2</span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">length</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">);
 i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">i</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">2</span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">length;
}
</span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(i</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)">length</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">n</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">)
 Merge(R,R1,i,i</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)">length</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">,n</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">);
</span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)">
 </span><span style="color: rgb(0,0,255)">for</span><span style="color: rgb(0,0,0)">(j</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">i;j</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">n;j</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">)
 R1[j]</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">R[j];
}
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> MSort(ElemType R[],ElemType R1[],</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> n)
{ 
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> length</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">;
</span><span style="color: rgb(0,0,255)">while</span><span style="color: rgb(0,0,0)"> (length</span><span style="color: rgb(0,0,0)"><</span><span style="color: rgb(0,0,0)">n)
{
 MergePass(R,R1,length,n);
 length</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">2</span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">length;
 MergePass(R1,R,length,n);
 length</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">2</span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">length;
}
}
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> MergeSort(SqList </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">L)
{
start_t</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">clock();
BeforeSort();
MSort(L.elem,L.elem,L.length);
display(yd1,bj1);
end_t</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">clock();
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">排序用时为 %f\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">,</span><span style="color: rgb(0,0,255)">float</span><span style="color: rgb(0,0,0)">(end_t</span><span style="color: rgb(0,0,0)">-</span><span style="color: rgb(0,0,0)">start_t)</span><span style="color: rgb(0,0,0)">/</span><span style="color: rgb(0,0,0)">CLK_TCK);
}

</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> main()
{
SqList L;
addlist(L);
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">起泡排序: \n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">);
qipao(L);
addlist(L);
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">直插排序: \n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">);
InsertSort(L);
addlist(L);
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">选择排序: \n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">);
SelectSort(L);
addlist(L);
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">希尔排序: \n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">);
xier(L);
addlist(L);
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">快速排续: \n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">);
QuickSort(L);
addlist(L); 
printf(</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">归并排序: \n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">);
MergeSort(L);
} </span></div>
试试其它关键字
　时间复杂度　
同语言下
可能有用的
Dezai.CN贡献的其它代码(4037)