查找和排序的實(shí)現(xiàn)

1、 實(shí)驗(yàn): 查找和排序的實(shí)現(xiàn)1.實(shí)驗(yàn)?zāi)康?）掌握折半查找,順序查找和黃金比例查找的方法；2）掌握直接插入排序，折半插入排序和快速排序的方法。2. 實(shí)驗(yàn)內(nèi)容： (1) 建立順序表;(2）實(shí)現(xiàn)以下算法：輸入要查詢(xún)的值，經(jīng)過(guò)順序查找和折半查找還有黃金比例查找，找出該元素的位置。順序表經(jīng)過(guò)直接插入排序，折半插入排序和快速排序后輸出。 3. 設(shè)計(jì)思想1(非遞減序列)順序查找：從表中最后一個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較，若相等，則查找成功。2(非遞減序列)折半查找：以處于區(qū)間中間位置記錄的關(guān)鍵字和給定值比較，若相等則成功，如不等，則縮小范圍，直至新的區(qū)間中間位置記錄的關(guān)鍵字等于給定值或區(qū)間大

2、小小于零時(shí)為止3. (非遞減序列)黃金比例查找：以處于區(qū)間黃金比例處（0.618）位置記錄的關(guān)鍵字和給定值比較，注意，不能直接用mid=(low+high)*0.618，這樣mid會(huì)溢出，應(yīng)該改為mid=(high-low)*0.618+low。4.直接插入排序：每次從無(wú)序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。它是由兩層嵌套循環(huán)組成的。外層循環(huán)標(biāo)識(shí)并決定待比較的數(shù)值。內(nèi)層循環(huán)為待比較數(shù)值確定其最終位置。直接插入排序?qū)儆诜€(wěn)定的排序，最壞時(shí)間復(fù)雜性為O(n2)，空間復(fù)雜度為O(1)。5. 折半插入排序：是對(duì)插入排序算法的一種改進(jìn)，由于排序算法過(guò)程中，就是不斷的依次將元素

3、插入前面已排好序的序列中。由于前半部分為已排好序的數(shù)列，這樣我們不用按順序依次尋找插入點(diǎn)，可以采用折半查找的方法來(lái)加快尋找插入點(diǎn)的速度。6.快速排序：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。4.代碼實(shí)現(xiàn)#include #include #define LIST_INIT_SIZE100#define LISTNCREMENT10typedef struct SqListint *elem;int length;int listsize

4、;SqList;void InitList_Sq(SqList &L)/數(shù)據(jù)結(jié)構(gòu)初始化，構(gòu)造空的表L.elem=(int *)malloc(LIST_INIT_SIZE *sizeof(int);if(!L.elem) exit(1);L.length=0;L.listsize=LIST_INIT_SIZE;void Creat(SqList &L)/建立順序表int n;coutn;cout請(qǐng)按非遞減順序輸入元素: endl;for(int i=1;iL.elemi;L.length=n;int search_Seq(SqList L,int key,int &d)/順序查找 L.elem0

5、=key; int i; d=d+1; for(i=L.length;key!=L.elemi;-i) d=d+1; return i; int halfserch(SqList L,int key2,int &k)L.elem0=key2; int low=1;int high;int mid;high=L.length;k=0;while(low=high)mid=(low+high)/2;k=k+1;if(key2=L.elemmid)return mid;else if (key2=L.elemmid)high=mid-1;else low=mid+1;return 0;int New

6、serch(SqList L,int key,int &d)L.elem0=key; int low=1;int high;int mid;high=L.length;d=0;while(low=high)mid=(high-low)*0.618+low;d=d+1;if(key=L.elemmid)return mid;else if (key=L.elemmid)high=mid-1;else low=mid+1;return 0;void main()SqList L;cout創(chuàng)建順序表endl;InitList_Sq(L);Creat(L);int a,b,c,d,e;d=0;cout請(qǐng)輸入要查詢(xún)的值:a; c=search_Seq(L,a,d);cout做順序查找的執(zhí)行次數(shù)為：dendl;cout經(jīng)過(guò)順序查找，您查詢(xún)的元素位置是：cendl; b=halfserch(L,a,d);cout做折半查找的執(zhí)行次數(shù)為：dendl; cout經(jīng)過(guò)折半查找，您