實(shí)驗(yàn)四排序?qū)嶒?yàn)報(bào)告

數(shù)據(jù)構(gòu)造實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)四排序?qū)W生姓名：班級(jí)：班內(nèi)序號(hào)：學(xué)號(hào)：日期：12月21日實(shí)驗(yàn)規(guī)定題目2使用鏈表實(shí)現(xiàn)下面多個(gè)排序算法，并進(jìn)行比較。排序算法：1、插入排序2、冒泡排序3、快速排序4、簡(jiǎn)樸選擇排序5、其它規(guī)定：1、測(cè)試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)。2、對(duì)于這三類數(shù)據(jù)，比較上述排序算法中核心字的比較次數(shù)和移動(dòng)次數(shù)（其中核心字交換計(jì)為3次移動(dòng)）。3、對(duì)于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時(shí)間，精確到微秒（選作）。4、對(duì)2和3的成果進(jìn)行分析，驗(yàn)證上述多個(gè)算法的時(shí)間復(fù)雜度。編寫測(cè)試main()函數(shù)測(cè)試線性表的對(duì)的性。2、程序分析2.1存儲(chǔ)構(gòu)造闡明：本程序排序序列的存儲(chǔ)由鏈表來完畢。其存儲(chǔ)構(gòu)造以下圖所示。(1)單鏈表存儲(chǔ)構(gòu)造：結(jié)點(diǎn)地址：1000HA[2]結(jié)點(diǎn)地址：1000H1080H……頭指針地址：1020HA[0]頭指針地址：1020H10C0H……地址：1080HA[3]地址：1080HNULL……地址：10C0HA[1]地址：10C0H1000H……（2）結(jié)點(diǎn)構(gòu)造structNode{ intdata; Node*next;};示意圖：intdataNode*next intdataNode*next2.2核心算法分析一：核心算法(一)直接插入排序voidLinkSort::InsertSort()直接插入排序是插入排序中最簡(jiǎn)樸的排序辦法，其基本思想是：依次將待排序序列中的每一種統(tǒng)計(jì)插入到一種已排好的序列中，直到全部統(tǒng)計(jì)都排好序。（1）算法自然語言1.將整個(gè)待排序的統(tǒng)計(jì)序列劃分成有序區(qū)和無序區(qū)，初始時(shí)有序區(qū)為待排序統(tǒng)計(jì)序列中的第一種統(tǒng)計(jì)，無序區(qū)涉及全部剩余待排序的統(tǒng)計(jì)；2.將不必去的第一種統(tǒng)計(jì)插入到有序區(qū)的適宜位置中，從而使無序區(qū)減少一種統(tǒng)計(jì)，有序區(qū)增加一種統(tǒng)計(jì)；3.重復(fù)執(zhí)行2，直到無序區(qū)中沒有統(tǒng)計(jì)為止。（2）源代碼voidLinkSort::InsertSort() //從第二個(gè)元素開始，尋找前面那個(gè)比它大的{ Node*P=front->next; //要插入的節(jié)點(diǎn)的前驅(qū) while(P->next) { Node*S=front; //用來比較的節(jié)點(diǎn)的前驅(qū) while(1) { CompareCount++; if(P->next->data<S->next->data) //P的后繼比S的后繼小則插入 { insert(P,S); break; } S=S->next; if(S==P) //若一趟比較結(jié)束，且不需要插入 { P=P->next; break;} } }}(3)時(shí)間和空間復(fù)雜度最佳狀況下，待排序序列為正序，時(shí)間復(fù)雜度為O（n）。最壞狀況下，待排序序列為逆序，時(shí)間復(fù)雜度為O（n2）。直接插入排序只需要一種統(tǒng)計(jì)的輔助空間，用來作為待插入統(tǒng)計(jì)的暫存單元和查找統(tǒng)計(jì)的插入位置過程中的“哨兵”。直接插入排序是一種穩(wěn)定的排序辦法。直接插入排序算法簡(jiǎn)樸容易實(shí)現(xiàn)，當(dāng)序列中的統(tǒng)計(jì)基本有序或帶排序統(tǒng)計(jì)較少時(shí)，他是最佳的排序辦法。但當(dāng)待排序的統(tǒng)計(jì)個(gè)數(shù)較多時(shí)，大量的比較和移動(dòng)操作使直接插入排序算法的效率減低。rr1≤r2≤……≤ri-1riri+1……rn有序區(qū)無序區(qū)直接插入排序的基本思想插入到適宜位置直接插入排序過程直接插入排序過程初始鍵值序列［12］1592063124第一趟排序成果［1215］92063124第二趟排序成果［91215］2063124第三趟排序成果［9121520］63124第四趟排序成果［69121520］3124第五趟排序成果［6912152031］24第六趟排序成果［691215202431］（二）冒泡排序voidLinkSort::BubbleSort()冒泡排序是交換排序中最簡(jiǎn)樸的排序辦法，其基本思想是：兩兩比較相鄰統(tǒng)計(jì)的核心碼，如果反序則交換，直到?jīng)]有反序的統(tǒng)計(jì)為止。本程序采用改善的冒泡程序。（1）算法自然語言1.將整個(gè)待排序的統(tǒng)計(jì)序列劃分成有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)涉及全部待排序的統(tǒng)計(jì)。2.對(duì)無序區(qū)從前向后依次將相鄰統(tǒng)計(jì)的核心碼進(jìn)行比較，若反序則交換，從而使得核心碼小的統(tǒng)計(jì)向前移，核心碼大的統(tǒng)計(jì)向后移（像水中的氣泡，體積大的先浮上來）。3.將最后一次交換的位置pos，做為下一趟無序區(qū)的末尾。4.重復(fù)執(zhí)行2和3，直到無序區(qū)中沒有反序的統(tǒng)計(jì)。（2）源代碼voidLinkSort::BubbleSort(){ Node*P=front->next; while(P->next) //第一趟排序并查找無序范疇 { CompareCount++; if(P->data>P->next->data) swap(P,P->next); P=P->next; } Node*pos=P; P=front->next; while(pos!=front->next) { Node*bound=pos; pos=front->next; while(P->next!=bound) { CompareCount++; if(P->data>P->next->data) { swap(P,P->next); pos=P->next; } P=P->next; } P=front->next; }}(3)時(shí)間和空間復(fù)雜度在最佳狀況下，待排序統(tǒng)計(jì)序列為正序，算法只執(zhí)行了一趟，進(jìn)行了n-1次核心碼的比較，不需要移動(dòng)統(tǒng)計(jì)，時(shí)間復(fù)雜度為O（n）；在最壞狀況下，待排序統(tǒng)計(jì)序列為反序，時(shí)間復(fù)雜度為O（n2），空間復(fù)雜度為O(1)。 冒泡排序是一種穩(wěn)定的排序辦法。rrjrj+1ri+1≤……≤rn-1≤rn無序區(qū)有序區(qū)1≤j≤i-1已經(jīng)位于最后位置起泡排序的基本思想反序則交換初始鍵值序列初始鍵值序列［5013559727384965］第一趟排序成果［13505527384965］97第二趟排序成果［1350273849］556597第三趟排序成果［13273849］50556597第四趟排序成果1327384950556597冒泡排序過程（三）快速排序voidLinkSort::Qsort()（1）算法自然語言1.首先選一種軸值（即比較的基準(zhǔn)），將待排序統(tǒng)計(jì)分割成獨(dú)立的兩部分，左側(cè)統(tǒng)計(jì)的核心碼均不大于或等于軸值，右側(cè)統(tǒng)計(jì)的核心碼均不不大于或等于軸值。2.然后分別對(duì)這兩部分重復(fù)上述過程，直到整個(gè)序列有序。3.整個(gè)快速排序的過程遞歸進(jìn)行。（2）源代碼voidLinkSort::Qsort(){ Node*End=front; while(End->next) { End=End->next; } Partion(front,End);}voidLinkSort::Partion(Node*Start,Node*End){ if(Start->next==End||Start==End) //遞歸返回 return; Node*Mid=Start; //基準(zhǔn)值前驅(qū) Node*P=Mid->next; while(P!=End&&P!=End->next) { CompareCount++; if(Mid->next->data>P->next->data) //元素值不大于軸點(diǎn)值，則將該元素插在軸點(diǎn)之前 { if(P->next==End) //若該元素為End，則將其前驅(qū)設(shè)為End End=P; insert(P,Mid); Mid=Mid->next; } elseP=P->next; } Partion(Start,Mid); //遞歸解決基準(zhǔn)值左側(cè)鏈表 Partion(Mid->next,End); //遞歸解決基準(zhǔn)值右側(cè)鏈表}（3）時(shí)間和空間復(fù)雜度在最佳的狀況下，時(shí)間復(fù)雜度為O（nlog2n）。在最壞的狀況下，時(shí)間復(fù)雜度為O（n2）。 快速排序是一種不穩(wěn)定的排序辦法。[[r1……ri-1]ri[ri+1……rn]均≤ri軸值均≥ri位于最后位置快速排序的基本思想圖解（四）簡(jiǎn)樸選擇排序基本思想為：第i趟排序通過n-i次核心碼的比較，在n-i+1（1≤i≤n-1）各統(tǒng)計(jì)中選用核心碼最小的統(tǒng)計(jì)，并和第i個(gè)統(tǒng)計(jì)交換作為有序序列的第i個(gè)統(tǒng)計(jì)。（1）算法自然語言1.將整個(gè)統(tǒng)計(jì)序列劃分為有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)含有待排序的全部統(tǒng)計(jì)。2.在無序區(qū)中選用核心碼最小的統(tǒng)計(jì)，將它與無序區(qū)中的第一種統(tǒng)計(jì)交換，使得有序區(qū)擴(kuò)展了一種統(tǒng)計(jì)，而無序區(qū)減少了一種統(tǒng)計(jì)。3.不停重復(fù)2，直到無序區(qū)之剩余一種統(tǒng)計(jì)為止。（2）源代碼voidLinkSort::SelectSort(){ Node*S=front; while(S->next->next) { Node*P=S; Node*Min=P; while(P->next)//查找最小統(tǒng)計(jì)的位置 { CompareCount++; if(P->next->data<Min->next->data) Min=P; P=P->next; } insert(Min,S); S=S->next; }}（3）時(shí)間和空間復(fù)雜度簡(jiǎn)樸選擇排序最佳、最壞和平均的時(shí)間復(fù)雜度為O（n2）。簡(jiǎn)樸選擇排序是一種不穩(wěn)定的排序辦法。初始鍵值序列初始鍵值序列［49276597761338］第一趟排序成果13［276597764938］第二趟排序成果1327［6597764938］第三趟排序成果132738［97764965］第四趟排序成果13273849［769765］第五趟排序成果1327384965［9776］第六趟排序成果13273849657697簡(jiǎn)樸選擇排序的過程示例（五）輸出比較成果函數(shù)（含計(jì)算函數(shù)體執(zhí)行時(shí)間代碼）（1）算法自然語言1、依次調(diào)用直接插入排序、冒泡排序、快速排序、簡(jiǎn)樸選擇排序的函數(shù)體，進(jìn)行序列的排序，并輸出對(duì)應(yīng)的比較次數(shù)、移動(dòng)次數(shù)。2、獲取現(xiàn)在系統(tǒng)時(shí)間。在調(diào)用函數(shù)之前設(shè)定一種調(diào)用代碼前的時(shí)間，在調(diào)用函數(shù)之后再次設(shè)定一種調(diào)用代碼后的時(shí)間，兩個(gè)時(shí)間相減就是代碼運(yùn)行時(shí)間。闡明：運(yùn)用QueryPerformanceFrequency()可獲取計(jì)時(shí)器頻率；QueryPerformanceCounter()用于得到高精度計(jì)時(shí)器的值。（2）源代碼voidprintResult(LinkSort&a,LinkSort&b,LinkSort&c,LinkSort&d){ _LARGE_INTEGERtime_start;//開始時(shí)間_LARGE_INTEGERtime_over;//結(jié)束時(shí)間doubledqFreq;//計(jì)時(shí)器頻率LARGE_INTEGERf;//計(jì)時(shí)器頻率QueryPerformanceFrequency(&f);dqFreq=(double)f.QuadPart;a.print();doubleTimeCount; CompareCount=0;MoveCount=0;TimeCount=0; QueryPerformanceCounter(&time_start);//統(tǒng)計(jì)起始時(shí)間 a.InsertSort(); QueryPerformanceCounter(&time_over);//統(tǒng)計(jì)結(jié)束時(shí)間 TimeCount=((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000; cout<<"排序成果：";a.print(); cout<<"1.插入。比較次數(shù)："<<setw(3)<<CompareCount<<";移動(dòng)次數(shù)："<<setw(3)<<MoveCount<<";時(shí)間:"<<TimeCount<<"us"<<endl; CompareCount=0;MoveCount=0;TimeCount=0; QueryPerformanceCounter(&time_start);//統(tǒng)計(jì)起始時(shí)間 b.BubbleSort(); QueryPerformanceCounter(&time_over);//統(tǒng)計(jì)結(jié)束時(shí)間 TimeCount=((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000; cout<<"2.冒泡。比較次數(shù)："<<setw(3)<<CompareCount<<";移動(dòng)次數(shù)："<<setw(3)<<MoveCount<<";時(shí)間:"<<TimeCount<<"us"<<endl; CompareCount=0;MoveCount=0;TimeCount=0; QueryPerformanceCounter(&time_start);//統(tǒng)計(jì)起始時(shí)間 c.Qsort(); QueryPerformanceCounter(&time_over);//統(tǒng)計(jì)結(jié)束時(shí)間 TimeCount=((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000; cout<<"3.快速。比較次數(shù)："<<setw(3)<<CompareCount<<";移動(dòng)次數(shù)："<<setw(3)<<MoveCount<<";時(shí)間:"<<TimeCount<<"us"<<endl; CompareCount=0;MoveCount=0;TimeCount=0; QueryPerformanceCounter(&time_start);//統(tǒng)計(jì)起始時(shí)間 d.SelectSort(); QueryPerformanceCounter(&time_over);//統(tǒng)計(jì)結(jié)束時(shí)間 TimeCount=((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000; cout<<"4.選擇。比較次數(shù)："<<setw(3)<<CompareCount<<";移動(dòng)次數(shù)："<<setw(3)<<MoveCount<<";時(shí)間:"<<TimeCount<<"us"<<endl;}（3）時(shí)間和空間復(fù)雜度時(shí)間復(fù)雜度O(1)(由于不包含循環(huán)體)。2.3其它排序辦法平均狀況最佳狀況最壞狀況輔助空間直接插入排序O(n2)O(n)O(n2)O(1)希爾排序O(nlog2n)~O(n2)O(n1.3)O(n2)O(1)起泡排序O(n2)O(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)~O(n)簡(jiǎn)樸選擇排序O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)歸并排序O(nlog2n)O(nlog2