{"id":44,"date":"2007-04-25T07:11:45","date_gmt":"2007-04-24T23:11:45","guid":{"rendered":"http:\/\/127.0.0.1\/website_linux\/blog\/?p=44"},"modified":"2007-04-25T07:11:45","modified_gmt":"2007-04-24T23:11:45","slug":"%e5%87%a0%e7%a7%8d%e6%8e%92%e5%ba%8f%e7%ae%97%e6%b3%95%e7%9a%84%e6%95%88%e7%8e%87%e6%af%94%e8%be%83","status":"publish","type":"post","link":"https:\/\/opgogo.com\/blog2\/?p=44","title":{"rendered":"\u51e0\u79cd\u6392\u5e8f\u7b97\u6cd5\u7684\u6548\u7387\u6bd4\u8f83"},"content":{"rendered":"

\/*
\n\u4e0b\u9762\u7684\u7a0b\u5e8f\u662f\u6211\u7684\u4e0a\u5b66\u671f\u6570\u636e\u7ed3\u6784\u7684\u8bfe\u7a0b\u8bbe\u8ba1
\n\u5e0c\u671b\u5bf9\u5373\u5c06\u5b66\u4e60\u6570\u636e\u7ed3\u6784\u7684\u670b\u53cb\u6709\u4e00\u70b9\u70b9\u5e2e\u52a9
\n\u56e0\u4e3a\u9a6c\u4e0a\u5c31\u8981\u79bb\u5f00\u7f51\u7edc2\u4e2a\u6708\u4e86\uff0c\u7b97\u662f\u4e00\u70b9\u70b9\u4e34\u522b\u7684\u793c\u7269
\nliond8 2004-3-20
\n*\/
\n# include “stdio.h”
\n# include “stdlib.h”
\n# include “string.h”
\n# include “time.h”
\n# include “windows.h”
\n# include “winbase.h”<\/p>\n

# define MAXSIZE 1024*5
\n# define TRUE 1
\n# define FALSE 0<\/p>\n

typedef int BOOL;<\/p>\n

typedef struct StudentData
\n{
\nint num; \/* this is a key word*\/
\n}Data;<\/p>\n

typedef struct LinkList
\n{
\nint Length;
\nData Record[MAXSIZE];
\n}LinkList;<\/p>\n

int RandArray[MAXSIZE];<\/p>\n

\/****************banner*******************************\/
\nvoid banner()
\n{
\nprintf(“\\n\\n\\t\\t******************************************\\n”);
\nprintf(“\\t\\t \u6570\u636e\u7ed3\u6784\u8bfe\u7a0b\u8bbe\u8ba1\\n”);
\nprintf(“\\t\\tMade by LionD8. 2003.6.30\\n”);
\nprintf(“\\t\\tPlese press enter.\\n”);
\nprintf(“\\t\\t******************************************”);
\ngetchar();
\nsystem(“cls.exe”);
\n}
\n\/******************\u968f\u673a\u751f\u6210\u51fd\u6570************************\/<\/p>\n

void RandomNum()
\n{
\nint i;
\nsrand((int)time( NULL ));
\nfor(i=0; iRecord[i].num=RandArray[i];
\nL->Length=i;
\n}<\/p>\n

BOOL LT(int i, int j,int* CmpNum)
\n{
\n(*CmpNum)++;
\nif (iLength; i++)
\nfprintf(f,”%d\\n”,L->Record[i].num);
\nfclose(f);
\n}<\/p>\n

\/**********\u897f\u5c14\u6392\u5e8f*************\/<\/p>\n

void ShellInsert(LinkList* L,int dk, int* CmpNum, int* ChgNum)
\n{
\nint i, j;
\nData Temp;
\nfor(i=dk; iLength;i++)
\n{
\nif( LT(L->Record[i].num, L->Record[i-dk].num, CmpNum) )
\n{
\nmemcpy(&Temp,&L->Record[i],sizeof(Data));
\nfor(j=i-dk; j>=0 && LT(Temp.num, L->Record[j].num, CmpNum) ; j-=dk)
\n{
\n(*ChgNum)++;
\nmemcpy(&L->Record[j+dk],&L->Record[j],sizeof(Data));
\n}
\nmemcpy(&L->Record[j+dk],&Temp,sizeof(Data));
\n}
\n}
\n}<\/p>\n

void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum)
\n{
\nint k;
\nfor (k=0; kRecord[low],sizeof(Data));
\nPivotKey=L->Record[low].num;
\nwhile (low < high)\n{\nwhile (lowRecord[high].num >= PivotKey)
\n{
\nhigh–;
\n(*CmpNum)++;
\n}
\n(*ChgNum)++;
\nmemcpy(&L->Record[low],&L->Record[high],sizeof(Data));
\nwhile (lowRecord[low].num <= PivotKey)\n{\nlow++;\n(*CmpNum)++;\n}\n(*ChgNum)++;\nmemcpy(&L->Record[high],&L->Record[low],sizeof(Data));
\n}
\nmemcpy(&L->Record[low],&Temp,sizeof(Data));
\nreturn low;
\n}<\/p>\n

void QSort (LinkList* L, int low, int high, int* CmpNum, int* ChgNum)
\n{
\nint PivotLoc=0;
\nif (low < high)\n{\nPivotLoc=Partition(L,low,high,CmpNum,ChgNum);\nQSort(L,low,PivotLoc-1,CmpNum,ChgNum);\nQSort(L,PivotLoc+1,high,CmpNum,ChgNum);\n}\n}\n\nvoid QuickSort (LinkList* L, int* CmpNum, int* ChgNum)\n{\nQSort(L,0,L->Length-1,CmpNum,ChgNum);
\n}<\/p>\n

\/*********************************************\/<\/p>\n

\/***********\u5806\u6392\u5e8f****************************\/<\/p>\n

void HeapAdjust (LinkList* L,int s, int m, int* CmpNum, int* ChgNum)
\n{
\nData Temp;
\nint j=0;
\ns++;
\nmemcpy(&Temp,&L->Record[s-1],sizeof(Data));
\nfor (j=2*s; j<=m ; j*=2)\n{\nif(jRecord[j-1].num,L->Record[j].num,CmpNum)) ++j;
\nif(!LT(Temp.num,L->Record[j-1].num,CmpNum)) break;
\n(*ChgNum)++;
\nmemcpy(&L->Record[s-1],&L->Record[j-1],sizeof(Data));
\ns=j;
\n}
\nmemcpy(&L->Record[s-1],&Temp,sizeof(Data));
\n}<\/p>\n

void HeapSort (LinkList* L, int* CmpNum, int* ChgNum)
\n{
\nint i=0;
\nData Temp;
\nfor (i=L->Length\/2-1; i>=0; i–)
\nHeapAdjust(L,i,L->Length,CmpNum,ChgNum);
\nfor (i=L->Length; i>1; i–)
\n{
\nmemcpy(&Temp,&L->Record[0],sizeof(Data));
\n(*ChgNum)++;
\nmemcpy(&L->Record[0],&L->Record[i-1],sizeof(Data));
\nmemcpy(&L->Record[i-1],&Temp,sizeof(Data));
\nHeapAdjust(L,0,i-1,CmpNum,ChgNum);
\n}
\n}<\/p>\n

\/****************\u5192\u6ce1\u6392\u5e8f****************************\/
\nvoid BubbleSort(LinkList* L, int* CmpNum, int* ChgNum)
\n{
\nint i,j;
\nData temp;
\nfor (i=0; iRecord[j].num,L->Record[j+1].num,CmpNum))
\n{
\n(*ChgNum)++;
\nmemcpy(&temp,&L->Record[j],sizeof(Data));
\nmemcpy(&L->Record[j],&L->Record[j+1],sizeof(Data));
\nmemcpy(&L->Record[j+1],&temp,sizeof(Data));
\n}
\n}
\n}
\n}<\/p>\n

\/**********************************************************\/<\/p>\n

\/******************\u9009\u62e9\u6392\u5e8f********************************\/
\nint SelectMinKey(LinkList* L,int k,int* CmpNum)
\n{
\nint Min=k;
\nfor ( ; kLength; k++)
\n{
\nif(!LT(L->Record[Min].num,L->Record[k].num,CmpNum))
\nMin=k;
\n}
\nreturn Min;
\n}<\/p>\n

void SelSort(LinkList* L, int* CmpNum, int* ChgNum)
\n{
\nint i, j;
\nData temp;
\nfor(i=0; iLength; i++)
\n{
\nj=SelectMinKey(L,i,CmpNum);
\nif(i!=j)
\n{
\n(*ChgNum)++;
\nmemcpy(&temp,&L->Record[i],sizeof(Data));
\nmemcpy(&L->Record[i],&L->Record[j],sizeof(Data));
\nmemcpy(&L->Record[j],&temp,sizeof(Data));
\n}
\n}
\n}<\/p>\n

\/**************************************************************\/<\/p>\n

void SelectSort()
\n{
\nprintf(“\\n 0. InsertSort.”);
\nprintf(“\\n 1. ShellSort.”);
\nprintf(“\\n 2. QuickSort.”);
\nprintf(“\\n 3. HeapSort.”);
\nprintf(“\\n 4. BubbleSort.”);
\nprintf(“\\n 5. SelectSort.”);
\nprintf(“\\n 6. AllAbove.”);
\nprintf(“\\n \\t\\t\\t\\t Please Select Num:”);
\n}<\/p>\n

\/**********************************************************\/<\/p>\n

\/**********************************************************\/
\nvoid AllAbove(LinkList* L,int* CmpNum, int* ChgNum)
\n{
\nint TempTime,i;
\nint SpendTime;
\nint dlta[3]={7,3,1};
\nint Indata[1]={1};<\/p>\n

TempTime=(int)GetTickCount();
\nShellSort(L,Indata,1,&CmpNum[0],&ChgNum[0]);
\nSpendTime=(int)GetTickCount()-TempTime;
\nprintf(“\\n\\tInserSort:”);
\nprintf(“\\n\\tCompare number=%d\\tChange number=%d\\tSepndTime=%dms”,CmpNum[0],ChgNum[0],SpendTime);<\/p>\n

for(i=0; iRecord[i].num=RandArray[i]; \/\/\u968f\u673a\u6570\u5217\u590d\u4f4d
\nTempTime=(int)GetTickCount();
\nShellSort(L, dlta, 3,&CmpNum[1],&ChgNum[1]);
\nSpendTime=(int)GetTickCount()-TempTime;
\nprintf(“\\n\\tShellSort:”);
\nprintf(“\\n\\tCompare number=%d\\tChange number=%d\\tSepndTime=%dms”,CmpNum[1],ChgNum[1],SpendTime);<\/p>\n

for(i=0; iRecord[i].num=RandArray[i]; \/\/\u968f\u673a\u6570\u5217\u590d\u4f4d
\nTempTime=(int)GetTickCount();
\nQuickSort(L,&CmpNum[2],&ChgNum[2]);
\nSpendTime=(int)GetTickCount()-TempTime;
\nprintf(“\\n\\tQuickSort:”);
\nprintf(“\\n\\tCompare number=%d\\tChange number=%d\\tSepndTime=%dms”,CmpNum[2],ChgNum[2],SpendTime);<\/p>\n

for(i=0; iRecord[i].num=RandArray[i]; \/\/\u968f\u673a\u6570\u5217\u590d\u4f4d
\nTempTime=(int)GetTickCount();
\nHeapSort(L,&CmpNum[3],&ChgNum[3]);
\nSpendTime=(int)GetTickCount()-TempTime;
\nprintf(“\\n\\tHeapSort:”);
\nprintf(“\\n\\tCompare number=%d\\tChange number=%d\\tSepndTime=%dms”,CmpNum[3],ChgNum[3],SpendTime);<\/p>\n

for(i=0; iRecord[i].num=RandArray[i]; \/\/\u968f\u673a\u6570\u5217\u590d\u4f4d
\nTempTime=(int)GetTickCount();
\nBubbleSort(L,&CmpNum[4],&ChgNum[4]);
\nSpendTime=(int)GetTickCount()-TempTime;
\nprintf(“\\n\\tBubbleSort:”);
\nprintf(“\\n\\tCompare number=%d\\tChange number=%d\\tSepndTime=%dms”,CmpNum[4],ChgNum[4],SpendTime);<\/p>\n

for(i=0; iRecord[i].num=RandArray[i]; \/\/\u968f\u673a\u6570\u5217\u590d\u4f4d
\nTempTime=(int)GetTickCount();
\nSelSort(L,&CmpNum[5],&ChgNum[5]);
\nSpendTime=(int)GetTickCount()-TempTime;
\nprintf(“\\n\\tSelectSort:”);
\nprintf(“\\n\\tCompare number=%d\\tChange number=%d\\tSepndTime=%dms”,CmpNum[5],ChgNum[5],SpendTime);<\/p>\n

}<\/p>\n

void main()
\n{
\nint select=0;
\nint dlta[3]={7,3,1};
\nint Indata[1]={1};
\nint CmpNum[6],ChgNum[6];
\nint SpendTime=0;
\nint TempTime;
\nLinkList L;
\nInitLinkList(&L);<\/p>\n

memset(CmpNum,0,sizeof(CmpNum));
\nmemset(ChgNum,0,sizeof(ChgNum));
\nbanner();<\/p>\n

SelectSort();
\nscanf(“%d”,&select);
\nswitch (select)
\n{
\ncase 0:
\nTempTime=(int)GetTickCount();
\nShellSort(&L,Indata,1,&CmpNum[select],&ChgNum[select]);
\nSpendTime=(int)GetTickCount()-TempTime;
\nprintf(“\\tInserSort:”);
\nprintf(“\\n\\n\\tCompare number=%d\\tChange number=%d\\tSepndTime=%dms”,CmpNum[select],ChgNum[select],SpendTime);
\nbreak;
\ncase 1:
\nTempTime=(int)GetTickCount();
\nShellSort(&L, dlta, 3,&CmpNum[select],&ChgNum[select]);
\nSpendTime=(int)GetTickCount()-TempTime;
\nprintf(“\\tShellSort:”);
\nprintf(“\\n\\n\\tCompare number=%d\\tChange number=%d\\tSepndTime=%dms”,CmpNum[select],ChgNum[select],SpendTime);
\nbreak;
\ncase 2:
\nTempTime=(int)GetTickCount();
\nQuickSort(&L,&CmpNum[select],&ChgNum[select]);
\nSpendTime=(int)GetTickCount()-TempTime;
\nprintf(“\\tQuickSort:”);
\nprintf(“\\n\\n\\tCompare number=%d\\tChange number=%d\\tSepndTime=%dms”,CmpNum[select],ChgNum[select],SpendTime);
\nbreak;
\ncase 3:
\nTempTime=(int)GetTickCount();
\nHeapSort(&L,&CmpNum[select],&ChgNum[select]);
\nSpendTime=(int)GetTickCount()-TempTime;
\nprintf(“\\tHeapSort:”);
\nprintf(“\\n\\n\\tCompare number=%d\\tChange number=%d\\tSepndTime=%dms”,CmpNum[select],ChgNum[select],SpendTime);
\nbreak;
\ncase 4:
\nTempTime=(int)GetTickCount();
\nBubbleSort(&L,&CmpNum[select],&ChgNum[select]);
\nSpendTime=(int)GetTickCount()-TempTime;
\nprintf(“\\tBubbleSort:”);
\nprintf(“\\n\\n\\tCompare number=%d\\tChange number=%d\\tSepndTime=%dms”,CmpNum[select],ChgNum[select],SpendTime);
\nbreak;
\ncase 5:
\nTempTime=(int)GetTickCount();
\nSelSort(&L,&CmpNum[select],&ChgNum[select]);
\nSpendTime=(int)GetTickCount()-TempTime;
\nprintf(“\\tSelectSort:”);
\nprintf(“\\n\\n\\tCompare number=%d\\tChange number=%d\\tSepndTime=%dms”,CmpNum[select],ChgNum[select],SpendTime);
\nbreak;
\ncase 6:
\nAllAbove(&L,CmpNum,ChgNum);
\nbreak;
\ndefault:
\nprintf(“\\n Input error !”);
\n}<\/p>\n

Display(&L);
\nprintf(“\\n\\n\\tTest over, please press enter!\\n”);
\ngetchar();
\ngetchar();
\n}<\/p>\n

\/*
\n\u6d4b\u8bd5\u7ed3\u679c
\n\u5bf91024\u00d75\u5927\u5c0f\u7684\u968f\u673a\u6570\u5217\u6392\u5e8f6\u79cd\u7b97\u6cd5\u7684\u6d4b\u8bd5\u7ed3\u679c\u5206\u522b\u5982\u4e0b:
\n1.InserSort:
\nCompare number=6407568 Change number=6397342 SepndTime=1349ms
\n2. ShellSort:
\nCompare number=1044703 Change number=1017712 SepndTime=127ms
\n3. QuickSort:
\nCompare number=72478 Change number=30118 SepndTime=0ms
\n4. HeapSort:
\nCompare number=110696 Change number=58691 SepndTime=18ms
\n5. BubbleSort:
\nCompare number=13104640 Change number=6849429 SepndTime=1992ms
\n6. SelectSort:
\nCompare number=13109760 Change number=5111 SepndTime=1188ms
\n*\/<\/p>\n","protected":false},"excerpt":{"rendered":"

\/* \u4e0b\u9762\u7684\u7a0b\u5e8f\u662f\u6211\u7684\u4e0a\u5b66\u671f\u6570\u636e\u7ed3\u6784\u7684\u8bfe\u7a0b\u8bbe\u8ba1 \u5e0c\u671b\u5bf9\u5373\u5c06\u5b66\u4e60\u6570\u636e\u7ed3\u6784\u7684\u670b\u53cb\u6709\u4e00\u70b9\u70b9\u5e2e\u52a9 \u56e0\u4e3a\u9a6c\u4e0a\u5c31\u8981\u79bb\u5f00\u7f51\u7edc2\u4e2a\u6708\u4e86\uff0c\u7b97\u662f\u4e00\u70b9\u70b9\u4e34\u522b\u7684\u793c\u7269 liond8 2004-3-20 *\/ # include… <\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false},"categories":[28],"tags":[],"class_list":["post-44","post","type-post","status-publish","format-standard","hentry","category-computer"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/opgogo.com\/blog2\/index.php?rest_route=\/wp\/v2\/posts\/44","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/opgogo.com\/blog2\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/opgogo.com\/blog2\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/opgogo.com\/blog2\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/opgogo.com\/blog2\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=44"}],"version-history":[{"count":0,"href":"https:\/\/opgogo.com\/blog2\/index.php?rest_route=\/wp\/v2\/posts\/44\/revisions"}],"wp:attachment":[{"href":"https:\/\/opgogo.com\/blog2\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=44"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/opgogo.com\/blog2\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=44"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/opgogo.com\/blog2\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=44"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}