各種排序算法.doc

排序算法是一種基本并且常用的算法。由于實(shí)際工作中處理的數(shù)量巨大，所以排序算法對(duì)算法本身的速度要求很高。而一般我們所謂的算法的性能主要是指算法的復(fù)雜度，一般用O方法來表示。在后面我將給出詳細(xì)的說明。既然是入門那么排序是入門必須要學(xué)的，下面總結(jié)下排序的幾種常見的算法。1：冒泡法也是和基本的一個(gè)排序方法。原理：將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上浮2：插入法：原理：逐一取出元素，在已經(jīng)排序的元素序列中從后向前掃描，放到適當(dāng)?shù)奈恢茫ㄆ鸪?，已?jīng)排序的元素序列為空）3：選擇法：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小元素，然后放到排序序列末尾。以此遞歸。4：堆排序利用堆（heaps）這種數(shù)據(jù)結(jié)構(gòu)來構(gòu)造的一種排序算法。堆是一個(gè)近似完全二叉樹結(jié)構(gòu)，并同時(shí)滿足堆屬性：即子節(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。5：箱排序設(shè)置若干個(gè)箱子，把關(guān)鍵字等于 k 的記錄全都裝入到第 k 個(gè)箱子里 ( 分配 ) ，然后按序號(hào)依次將各非空的箱子首尾連接起來 ( 收集 ) 。6：希爾排序選擇一個(gè)步長(zhǎng)(Step) ,然后按間隔為步長(zhǎng)的單元進(jìn)行排序.遞歸,步長(zhǎng)逐漸變小,直至為1.7：桶排序桶排序的思想是把 0 ， 1) 劃分為 n 個(gè)大小相同的子區(qū)間，每一子區(qū)間是一個(gè)桶。對(duì)于排序的算法我想先做一點(diǎn)簡(jiǎn)單的介紹，也是給這篇文章理一個(gè)提綱。我將按照算法的復(fù)雜度，從簡(jiǎn)單到難來分析算法。第一部分是簡(jiǎn)單排序算法，后面你將看到他們的共同點(diǎn)是算法復(fù)雜度為O(N*N)（因?yàn)闆]有使用word,所以無法打出上標(biāo)和下標(biāo)）。第二部分是高級(jí)排序算法，復(fù)雜度為O(Log2(N)。這里我們只介紹一種算法。另外還有幾種算法因?yàn)樯婕皹渑c堆的概念，所以這里不于討論。第三部分類似動(dòng)腦筋。這里的兩種算法并不是最好的（甚至有最慢的），但是算法本身比較奇特，值得參考（編程的角度）。同時(shí)也可以讓我們從另外的角度來認(rèn)識(shí)這個(gè)問題。第四部分是我送給大家的一個(gè)餐后的甜點(diǎn)一個(gè)基于模板的通用快速排序。由于是模板函數(shù)可以對(duì)任何數(shù)據(jù)類型排序（抱歉，里面使用了一些論壇專家的呢稱）?，F(xiàn)在，讓我們開始吧：一、簡(jiǎn)單排序算法由于程序比較簡(jiǎn)單，所以沒有加什么注釋。所有的程序都給出了完整的運(yùn)行代碼，并在我的VC環(huán)境下運(yùn)行通過。因?yàn)闆]有涉及MFC和WINDOWS的內(nèi)容，所以在BORLAND C+的平臺(tái)上應(yīng)該也不會(huì)有什么問題的。在代碼的后面給出了運(yùn)行過程示意，希望對(duì)理解有幫助。1.冒泡法：這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因?yàn)樗墓ぷ骺磥硐笫敲芭荩?include void BubbleSort(int* pData,int Count)int iTemp;for(int i=1;i=i;j-)if(pDatajPDATAJ-1)iTemp = pDataj-1;pDataj-1 = pDataj;pDataj = iTemp;void main()int data = 10,9,8,7,6,5,4;BubbleSort(data,7);for (int i=0;i7;i+)coutDATAI ?;倒序(最糟情況)第一輪：10,9,8,7-10,9,7,8-10,7,9,8-7,10,9,8(交換3次)第二輪：7,10,9,8-7,10,8,9-7,8,10,9(交換2次)第一輪：7,8,10,9-7,8,9,10(交換1次)循環(huán)次數(shù)：6次交換次數(shù)：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次)循環(huán)次數(shù)：6次交換次數(shù)：3次上面我們給出了程序段，現(xiàn)在我們分析它：這里，影響我們算法性能的主要部分是循環(huán)和交換，顯然，次數(shù)越多，性能就越差。從上面的程序我們可以看出循環(huán)的次數(shù)是固定的，為1+2+.+n-1。寫成公式就是1/2*(n-1)*n。現(xiàn)在注意，我們給出O方法的定義：若存在一常量K和起點(diǎn)n0，使當(dāng)n=n0時(shí)，有f(n)=K*g(n),則f(n) = O(g(n)。（呵呵，不要說沒學(xué)好數(shù)學(xué)呀，對(duì)于編程數(shù)學(xué)是非常重要的?。┈F(xiàn)在我們來看1/2*(n-1)*n，當(dāng)K=1/2，n0=1，g(n)=n*n時(shí)，1/2*(n-1)*n=1/2*n*n=K*g(n)。所以f(n)=O(g(n)=O(n*n)。所以我們程序循環(huán)的復(fù)雜度為O(n*n)。再看交換。從程序后面所跟的表可以看到，兩種情況的循環(huán)相同，交換不同。其實(shí)交換本身同數(shù)據(jù)源的有序程度有極大的關(guān)系，當(dāng)數(shù)據(jù)處于倒序的情況時(shí)，交換次數(shù)同循環(huán)一樣（每次循環(huán)判斷都會(huì)交換），復(fù)雜度為O(n*n)。當(dāng)數(shù)據(jù)為正序，將不會(huì)有交換。復(fù)雜度為O(0)。亂序時(shí)處于中間狀態(tài)。正是由于這樣的原因，我們通常都是通過循環(huán)次數(shù)來對(duì)比算法。2.交換法：交換法的程序最清晰簡(jiǎn)單，每次用當(dāng)前的元素一一的同其后的元素比較并交換。#include void ExchangeSort(int* pData,int Count)int iTemp;for(int i=0;iCOUNT-1;I+)for(int j=i+1;jCOUNT;J+)if(pDatajPDATAI)iTemp = pDatai;pDatai = pDataj;pDataj = iTemp;void main()int data = 10,9,8,7,6,5,4;ExchangeSort(data,7);for (int i=0;i7;i+)coutDATAI ?;倒序(最糟情況)第一輪：10,9,8,7-9,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次)循環(huán)次數(shù)：6次交換次數(shù)：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,10,9-7,8,9,10(交換1次)循環(huán)次數(shù)：6次交換次數(shù)：3次從運(yùn)行的表格來看，交換幾乎和冒泡一樣糟。事實(shí)確實(shí)如此。循環(huán)次數(shù)和冒泡一樣也是1/2*(n-1)*n，所以算法的復(fù)雜度仍然是O(n*n)。由于我們無法給出所有的情況，所以只能直接告訴大家他們?cè)诮粨Q上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。3.選擇法：現(xiàn)在我們終于可以看到一點(diǎn)希望：選擇法，這種方法提高了一點(diǎn)性能（某些情況下）這種方法類似我們?nèi)藶榈呐判蛄?xí)慣：從數(shù)據(jù)中選擇最小的同第一個(gè)值交換，在從省下的部分中選擇最小的與第二個(gè)交換，這樣往復(fù)下去。#include void SelectSort(int* pData,int Count)int iTemp;int iPos;for(int i=0;iCOUNT-1;I+)iTemp = pDatai;iPos = i;for(int j=i+1;jCOUNT;J+)if(pDatajITEMP)iTemp = pDataj;iPos = j;pDataiPos = pDatai;pDatai = iTemp;void main()int data = 10,9,8,7,6,5,4;SelectSort(data,7);for (int i=0;i7;i+)coutDATAI ?;倒序(最糟情況)第一輪：10,9,8,7-(iTemp=9)10,9,8,7-(iTemp=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次)循環(huán)次數(shù)：6次交換次數(shù)：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(交換1次)循環(huán)次數(shù)：6次交換次數(shù)：3次遺憾的是算法需要的循環(huán)次數(shù)依然是1/2*(n-1)*n。所以算法復(fù)雜度為O(n*n)。我們來看他的交換。由于每次外層循環(huán)只產(chǎn)生一次交換（只有一個(gè)最小值）。所以f(n)=n所以我們有f(n)=O(n)。所以，在數(shù)據(jù)較亂的時(shí)候，可以減少一定的交換次數(shù)。4.插入法：插入法較為復(fù)雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應(yīng)的位置插入，然后繼續(xù)下一張#include void InsertSort(int* pData,int Count)int iTemp;int iPos;for(int i=1;i=0) & (iTempPDATAIPOS)pDataiPos+1 = pDataiPos;iPos-;pDataiPos+1 = iTemp;void main()int data = 10,9,8,7,6,5,4;InsertSort(data,7);for (int i=0;i7;i+)coutDATAI ?;倒序(最糟情況)第一輪：10,9,8,7-9,10,8,7(交換1次)(循環(huán)1次)第二輪：9,10,8,7-8,9,10,7(交換1次)(循環(huán)2次)第一輪：8,9,10,7-7,8,9,10(交換1次)(循環(huán)3次)循環(huán)次數(shù)：6次交換次數(shù)：3次其他：第一輪：8,10,7,9-8,10,7,9(交換0次)(循環(huán)1次)第二輪：8,10,7,9-7,8,10,9(交換1次)(循環(huán)2次)第一輪：7,8,10,9-7,8,9,10(交換1次)(循環(huán)1次)循環(huán)次數(shù)：4次交換次數(shù)：2次上面結(jié)尾的行為分析事實(shí)上造成了一種假象，讓我們認(rèn)為這種算法是簡(jiǎn)單算法中最好的，其實(shí)不是，因?yàn)槠溲h(huán)次數(shù)雖然并不固定，我們?nèi)钥梢允褂肙方法。從上面的結(jié)果可以看出，循環(huán)的次數(shù)f(n)=1/2*n*(n-1)=1/2*n*n。所以其復(fù)雜度仍為O(n*n)（這里說明一下，其實(shí)如果不是為了展示這些簡(jiǎn)單排序的不同，交換次數(shù)仍然可以這樣推導(dǎo)）。現(xiàn)在看交換，從外觀上看，交換次數(shù)是O(n)（推導(dǎo)類似選擇法），但我們每次要進(jìn)行與內(nèi)層循環(huán)相同次數(shù)的=操作。正常的一次交換我們需要三次=而這里顯然多了一些，所以我們浪費(fèi)了時(shí)間。最終，我個(gè)人認(rèn)為，在簡(jiǎn)單排序算法中，選擇法是最好的。二、高級(jí)排序算法：高級(jí)排序算法中我們將只介紹這一種，同時(shí)也是目前我所知道（我看過的資料中）的最快的。它的工作看起來仍然象一個(gè)二叉樹。首先我們選擇一個(gè)中間值middle程序中我們使用數(shù)組中間值，然后把比它小的放在左邊，大的放在右邊（具體的實(shí)現(xiàn)是從兩邊找，找到一對(duì)后交換）。然后對(duì)兩邊分別使用這個(gè)過程（最容易的方法遞歸）。1.快速排序：#include void run(int* pData,int left,int right)int i,j;int middle,iTemp;i = left;j = right;middle = pData(left+right)/2; /求中間值dowhile(pDataiMIDDLE) (iright)= &= 從左掃描大于中值的數(shù) i+;while(pDatajmiddle) & (jleft)/從右掃描大于中值的數(shù)j-;if(i=j)/找到了一對(duì)值/交換iTemp = pDatai;pDatai = pDataj;pDataj = iTemp;i+;j-;while(i=j);/如果兩邊掃描的下標(biāo)交錯(cuò)，就停止（完成一次）/當(dāng)左邊部分有值(leftJ)，遞歸左半邊if(lefti)，遞歸右半邊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=0;i7;i+)coutDATAI ?;這里我沒有給出行為的分析，因?yàn)檫@個(gè)很簡(jiǎn)單，我們直接來分析算法：首先我們考慮最理想的情況1.數(shù)組的大小是2的冪，這樣分下去始終可以被2整除。假設(shè)為2的k次方，即k=log2(n)。2.每次我們選擇的值剛好是中間值，這樣，數(shù)組才可以被等分。第一層遞歸，循環(huán)n次，第二層循環(huán)2*(n/2).所以共有n+2(n/2)+4(n/4)+.+n*(n/n) = n+n+n+.+n=k*n=log2(n)*n所以算法復(fù)雜度為O(log2(n)*n)其他的情況只會(huì)比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那么他將變成交換法（由于使用了遞歸，情況更糟）。但是你認(rèn)為這種情況發(fā)生的幾率有多大？呵呵，你完全不必?fù)?dān)心這個(gè)問題。實(shí)踐證明，大多數(shù)的情況，快速排序總是最好的。如果你擔(dān)心這個(gè)問題，你可以使用堆排序，這是一種穩(wěn)定的O(log2(n)*n)算法，但是通常情況下速度要慢于快速排序（因?yàn)橐亟M堆）。三、其他排序1.雙向冒泡：通常的冒泡是單向的，而這里是雙向的，也就是說還要進(jìn)行反向的工作。代碼看起來復(fù)雜，仔細(xì)理一下就明白了，是一個(gè)來回震蕩的方式。寫這段代碼的作者認(rèn)為這樣可以在冒泡的基礎(chǔ)上減少一些交換（我不這么認(rèn)為，也許我錯(cuò)了）。反正我認(rèn)為這是一段有趣的代碼，值得一看。#include 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(pDataiPDATAI-1)iTemp = pDatai;pDatai = pDatai-1;pDatai-1 = iTemp;t = i;left = t+1;/反向的部分for(i=left;iRIGHT+1;I+)if(pDataiPDATAI-1)iTemp = pDatai;pDatai = pDatai-1;pDatai-1 = iTemp;t = i;right = t-1;while(left=right);void main()int data = 10,9,8,7,6,5,4;Bubble2Sort(data,7);for (int i=0;i7;i+)coutDATAI ?;2.SHELL排序這個(gè)排序非常復(fù)雜，看了程序就知道了。首先需要一個(gè)遞減的步長(zhǎng)，這里我們使用的是9、5、3、1（最后的步長(zhǎng)必須是1）。工作原理是首先對(duì)相隔9-1個(gè)元素的所有內(nèi)容排序，然后再使用同樣的方法對(duì)相隔5-1個(gè)元素的排序以次類推。#include void ShellSort(int* pData,int Count)int step4;step0 = 9;step1 = 5;step2 = 3;step3 = 1;int iTemp;int k,s,w;for(int i=0;i4;i+)k = stepi;s = -k;for(int j=k;jCOUNT;J+)iTemp = pDataj;w = j-k;/求上step個(gè)元素的下標(biāo)if(s =0)s = -k;s+;pDatas = iTemp;while(iTemp=0) & (w=Count)pDataw+k = pDataw;w = w-k;pDataw+k = iTemp;void main()int data = 10,9,8,7,6,5,4,3,2,1,-10,-1;ShellSort(data,12);for (int i=0;i12;i+)coutDATAI ?;呵呵，程序看起來有些頭疼。不過也不是很難，把s=0的塊去掉就輕松多了，這里是避免使用0步長(zhǎng)造成程序異常而寫的代碼。這個(gè)代碼我認(rèn)為很值得一看。這個(gè)算法的得名是因?yàn)槠浒l(fā)明者的名字D.L.SHELL。依照參考資料上的說法：“由于復(fù)雜的數(shù)學(xué)原因避免使用2的冪次步長(zhǎng)，它能降低算法效率?！绷硗馑惴ǖ膹?fù)雜度為n的1.2次冪。同樣因?yàn)榉浅?fù)雜并“超出本書討論范圍”的原因（我也不知道過程），我們只有結(jié)果了。四、基于模板的通用排序：這個(gè)程序我想就沒有分析的必要了，大家看一下就可以了。不明白可以在論壇上問。MyData.h文件/class CMyDatapublic:CMyData(int Index,char* strData);CMyData();virtual CMyData();int m_iIndex;int GetDataSize() return m_iDataSize; ;const char* GetData() return m_strDatamember; ;/這里重載了操作符：CMyData& operator =(CMyData &SrcData);bool operator (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* strData):m_iIndex(Index),m_iDataSize(0),m_strDatamember(NULL)m_iDataSize = strlen(strData);m_strDatamember = new charm_iDataSize+1;strcpy(m_strDatamember,strData);CMyData& CMyData:operator =(CMyData &SrcData)m_iIndex = SrcData.m_iIndex;m_iDataSize = SrcData.GetDataSize();m_strDatamember = new charm_iDataSize+1;strcpy(m_strDatamember,SrcData.GetData();return *this;bool CMyData:operator (CMyData& data )return m_iIndex(CMyData& data )return m_iIndexdata.m_iIndex;/主程序部分#include #include MyData.htemplate void run(T* pData,int left,int right)int i,j;T middle,iTemp;i = left;j = right;/下面的比較都調(diào)用我們重載的操作符函數(shù)middle = pData(left+right)/2; /求中間值dowhile(pDataiMIDDLE) (iright)= &= 從左掃描大于中值的數(shù) i+;while(pDatajmiddle) & (jleft)/從右掃描大于中值的數(shù)j-;if(i=j)/找到了一對(duì)值/交換iTemp = pDatai;pDatai = pDataj;pDataj = iTemp;i+;j-;while(i=j);/如果兩邊掃描的下標(biāo)交錯(cuò)，就停止（完成一次）/當(dāng)左邊部分有值(leftJ)，遞歸左半邊if(lefti)，遞歸右半邊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),CMyData(6,wangjun),CMyData(5,VCKBASE),CMyData(4,jacky2000),CMyData(3,cwally),CMyData(2,VCUSER),CMyData(1,isdong);QuickSort(data,8);for (int i=0;i8;i+)coutDATAI.M_IINDEX  ?datai.getdata()?n?; coutn;這里共包括（直接插入排序，冒泡排序，選擇排序，快速排序，堆排序）五種。由于我這是第一次編圖形界面，開始沒有考慮太多，只想編出來就行了，所以編界面的部分全寫在了主函數(shù)里，顯的比較亂。開始出來的那個(gè)對(duì)話框是要你輸密碼（a）第三個(gè)對(duì)話框是輸入要排的數(shù)的個(gè)數(shù)，如果小于50，則將每次排的過程都輸出，否則，一次性全部輸出。#include#include#include#include#include#define Up 0x4800#define Down 0x5000#define Enter 0x1c0d#define NO_ENTER 10#define LEN 20000int dataLEN+1;int long_n;int g,h=1;FILE *fp;void Insort(int data)int i,j;for(i=2;i=long_n;i+)data0=data;j=i-1;while(data0DATAJ) dataj+1=dataj;j-;dataj+1=data0;if(long_n=50)if(long_n=50)printf(n);printf( Insert Sortn);printf( %d times:n,i-1);printf( );for(g=1;g=long_n;g+)printf(%d ,datag);if(g=8) printf(n);printf( );getch();void Bubble_sort(int data)int i,j,t;for(j=1;j=long_n;j+)for(i=1;idatai+1)t=data;data=datai+1;datai+1=t;if(long_n=50)if(long_n=50)printf(n);printf( Bubble Sortn);printf( %d times:n,j);printf( );for(g=1;g=long_n;g+)printf(%d ,datag);if(g=8) printf(n);printf( );getch(); void Selectsort(int data)int i,j,min,temp;for(i=1;i=long_n;i+)min=i;for(j=i+1;jdataj)min=j;temp=data;data=datamin;datamin=temp;if(long_n=50)if(long_n=50)printf(n);printf( Select Sortn);printf( %d times:n,i);printf( );for(g=1;g=long_n;g+)printf(%d ,datag);if(g=8) printf(n);printf( );getch(); void Quick_sort(int data,int low,int high)int pivotloc;if(long_n=50)if(long_n=50)if(h!=0)printf(n);printf( Quick Sortn);printf( %d times:n,h);printf( );for(g=1;g=long_n;g+)printf(%d ,datag);if(g=8) printf(n);printf( );getch(); h+;if(lowHIGH) pivotloc=Partition(data,low,high);Quick_sort(data,low,pivotloc-1);Quick_sort(data,pivotloc+1,high);if(long_n=50)if(long_n=50)printf(n);printf( Quick Sortn);printf( %d times:n,h);printf( );h+;for(g=1;g=long_n;g+)printf(%d ,datag);if(g=8) printf(n);printf( );getch();int Partition(int data,int low,int high)int pivotkey;data0=datalow;pivotkey=datalow;while(lowHIGH) while(low=pivotkey) -high;datalow=datahigh;while(lowHIGH&DATALOWPIVOTKEY) datahigh=datalow;datalow=data0;return low;void HeapAdjust(int data,int s,int m)int j,rc;rc=datas;for(j=2*s;j=m;j*=2)if(jdataj+1) +j;if(rcDATAJ) datas=dataj;s=j;datas=rc;void Heap_sort(int data)int i,temp;for(i=long_n/2;i0;-i)HeapAdjust(data,i,long_n);for(i=long_n;i1;-i)if(long_n=50)if(long_n=50)printf(n);printf( Heap Sortn);printf( %d times:n,h);printf( );h+;for(g=1;g=long_n;g+)printf(%d ,datag);if(g=8) printf(n);printf( );getch();temp=data1;data1=data;data=temp;HeapAdjust(data,1,i-1);main()int gdriver=DETECT,gmode;int x,y,ch,y_pos,b_k,position,lon,wide,c_lon,c_wide,deltx,delty,middle,count,depth;time_t start,end;char *key=a;char *key1;struct numberint left;int top;int right;int bottom;number6;struct characterint x;int y;char title20;c_size6;strcpy(c_size0.title,Insert sort);strcpy(c_size1.title,Bubble sort);strcpy(c_size2.title,Select sort);strcpy(c_size3.title,Quick sort);strcpy(c_size4.title,Heap sort);strcpy(c_size5.title,Quit);fp=fopen(sort.txt,w+);while(1)textcolor(YELLOW);clrscr();gotoxy(20,10);putch(218);for(b_k=0;b_k30;b_k+) putch(196);putch(191);for(b_k=0;b_k2;b_k+)gotoxy(20,11+b_k);putch(179);gotoxy(51,11+b_k); putch(179);gotoxy(20,12);putch(192);for(b_k=0;b_k30;b_k+) putch(196);putch(217);gotoxy(21,11);printf(please iuput the key:);scanf(%s,key1);if(strcmp(key1,key)=0) break;else printf(nnn);printf( Error!);getch();clrscr();loop: lon=150;wide=250;c_lon=165;c_wide=260;deltx=100;delty=30;middle=40;count=1;depth=1;initgraph(&gdriver,&gmode,);setbkcolor(BLUE);cleardevice();for(x=0;x6;x+)numberx.left=wide;numberx.right=wide+deltx;numberx.top=lon;numberx.bottom=lon+delty;lon+=middle;for(x=0;x6;x+)c_sizex.x=c_wide;c_sizex.y=c_lon;c_lon+=delty+10;for(x=0;x6;x+)setfillstyle(1,7);bar(numberx.left,numberx.top,numberx.right,numberx.bottom);setcolor(5);line(numberx.left,numberx.bottom,numberx.right,numberx.bottom);line(numberx.right,numberx.top,numberx.right,numberx.bottom);setcolor(12);for(x=0;x1)position-;setcolor(12);outtextxy(c_sizex.x,c_sizex.y,c_sizex.title);x-;setcolor(4);outtextxy(c_sizex.x,c_sizex.y,c_sizex.title);printf(7);break;case Down:if(position6)position+;setcolor(12);outtextxy(c_sizex.x,c_sizex.y,c_sizex.title);x+;setcolor(4);outtextxy(c_sizex.x,c_sizex.y, c_sizex.title);printf(7);break;case Enter: y=position;break;cleardevice();closegraph();randomize();if(y=6) fclose(fp);exit(0);textcolor(YELLOW);clrscr();gotoxy(20,10);putch(218);for(b_k=0;b_k30;b_k+) putch(196);putch(191);for(b_k=0;b_k2;b_k+)gotoxy(20,11+b_k);putch(179);gotoxy(51,11+b_k); putch(179);gotoxy(20,12);putch(192);for(b_k=0;b_k30;b_k+) putch(196);putch(217);gotoxy(21,11);printf(please iuput the number:);scanf(%d,&long_n);printf(nnn);for(x=1;x=long_n;x+)datax=rand()%5000;if(long_n=50)printf( the orginal datas:n);printf( );for(x=1;x=long_n;x+)printf(%d ,datax);if(x%11=0)printf(n);printf(nn);switch(y)case 1: start=time(NULL);Insort(data);end=time(NULL); break;case 2: start=time(NULL);Bubble_sort(data);en