1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告幾種排序算法的演示一、需求分析：1、操作環(huán)境：Microsoft Visual Studio 20052、程序?qū)嵤┕δ埽和ㄟ^用戶輸入的數(shù)據(jù)，經(jīng)過程序，最終從小到大輸出。排序包括教材中介紹的幾種常用排序方法：直接插入對齊、半插入對齊、冒泡對齊、快速對齊、對齊選擇、堆疊對齊、反轉(zhuǎn)對齊。每個排序的詳細信息將顯示在每個排序過程中。3、輸入程序：輸入所需排序方法的序號。輸入排序后的數(shù)據(jù)數(shù)。輸入特定數(shù)據(jù)點。4、程序輸出：輸出每個排序結(jié)果以及最后的排序結(jié)果二、設(shè)計說明：1、算法設(shè)計思路：a交換對齊(氣泡對齊，快速對齊)交換排序的基本想法是按關(guān)鍵字比較排序表中的數(shù)據(jù)元素兩次，并在發(fā)生逆序的

2、情況下交換位置(即排序順序與排序后的順序相反)，直到所有數(shù)據(jù)元素都是連續(xù)的。b對齊插入(對齊直接插入，半剖面插入對齊)插入排序的基本想法是，每當(dāng)將數(shù)據(jù)元素插入到某些排序的序列中時，確保插入順序保持不變。設(shè)置最初僅包含一個數(shù)據(jù)元素的有序初始序列。然后，在此初始序列中繼續(xù)插入數(shù)據(jù)元素，直到最后一個數(shù)據(jù)元素插入到排序序列中，整個排序操作就完成了。排序c選擇(簡單選擇排序，堆排序)排序的基本理念是首先在具有n個數(shù)據(jù)元素的排序表中選擇具有最小關(guān)鍵字的數(shù)據(jù)元素，然后依次重復(fù)其馀n-1個數(shù)據(jù)元素中具有最小關(guān)鍵字的數(shù)據(jù)元素(整個數(shù)據(jù)表中的第二個最小數(shù)據(jù)元素)，直到每行(例如，第I行，i=1，n-1)始終是當(dāng)前

3、剩下的n-i 1個排序目標(biāo)數(shù)據(jù)元素中具有最小鍵的數(shù)據(jù)元素，作為排序數(shù)據(jù)元素順序中的第I個數(shù)據(jù)元素。在N-1行選擇結(jié)束之前，如果只剩下一個數(shù)據(jù)點排序，則不再需要選擇。數(shù)據(jù)元素序列按選定順序排序，排序完成。d合并對齊(兩個方向合并對齊)雙向合并排序的基本想法是假設(shè)初始排序表中有n個數(shù)據(jù)元素，首先將其視為從長度為1的開始到結(jié)束的n個排序的子表(稍后稱為合并項)，然后創(chuàng)建兩個關(guān)聯(lián)，將全長為2的合并項(如果n為奇數(shù)，則最后合并項的長度為1)導(dǎo)入n/2。再加兩個，這樣重復(fù)將指定長度為n的順序。1、主要數(shù)據(jù)結(jié)構(gòu)設(shè)計說明：程序的數(shù)據(jù)結(jié)構(gòu)是堆、線性表。2、流程的主要流程圖：開始主菜單選擇對齊操作合并定序排序簡單

4、的選擇快速排序冒泡排序插入一半直接插入輸出每個排序結(jié)果結(jié)束排序系統(tǒng)3、程序的主要模塊，a主菜單b排序模塊：直接插入a對齊b折疊插入對齊c氣泡對齊d快速排序e簡單選擇排序f堆排序g排序4、程序的主要函數(shù)和偽代碼模板a類Templateclass sortlistPrivate:Int currentsize/數(shù)據(jù)表中的數(shù)據(jù)元素數(shù)Public:Type * arr/存儲數(shù)據(jù)元素的矢量(排序表)sortlist(): currentsize(0) arr=new typemax size；/構(gòu)造函數(shù)sortlist(int n) arr=new typemaxsize；current size=n；

5、Void insert (int I，type x) arrI=x； sort list() deletearr；/析構(gòu)函數(shù)Void swap(type x，type y)/數(shù)據(jù)點x和y交換位置 type temp=x；x=y；Y=tempvoid insertionsort()；/直接插入排序void binaryinsertsort()；/半插入排序void bubble sort()；/排序氣泡void select sort()；/對簡單選擇排序Void quicksort(int low，int high)；/快速排序void heap sort()；/排列堆疊void merge

6、sort(sort list table)；/合并排序void filter down(const int start)；/創(chuàng)建最大堆void merge pass(sortlistsourcetable、sortlistmergedtable、const intlen)；/回來一次Voidmerge (sortlistsourcetable、sortlistmergedtable、const int left、const int mid、const int right)；/兩種合并算法b直接插入對齊Template /排序直接插入void sortlist :3360 insertion o

7、rt()Template /排序直接插入void sortlist :3360 insertion ort()Type tempint j；for(int I=1)；I=current size-1；I)temp=arrI；j=I-1；While(j=0temp/半剖面插入對齊void sortlist 3363603360 binaryinnsertsort()Type tempInt left，rightfor(int I=1)；I=leftK-)/向后移動arrk 1=arrk；arrleft=temp；Cout num 行排序結(jié)果為： ；for(int t=0)；T/冒泡排序void

8、sortlist :3360 bubble sort()int I=1；int finish=0；/0表示尚未排序While(iarrj 1)/反向順序Swap(arrj，arrj 1)；/相鄰元素交換位置finish=0；/結(jié)束排序標(biāo)志設(shè)置為，表示此旅行發(fā)生了交換，沒有排序I；Cout num 行排序結(jié)果為： ；for(int t=0)；tvoid sortlist :3360 select sort()/簡單選擇排序int k；for(int I=0)；I=current size-1；I)k=I；for(int j=I 1；J/快速排序在void sortlist 33603360 qu

9、ick sort(int low，int high)/排序等待區(qū)low，high中執(zhí)行遞歸快速排序Int i=low，j=hightype temp=arrlow；/將間隙的第一個位置匯入至預(yù)設(shè)位置if(I=arrI)I；If(i/最大堆void sortlist :3360 filter down(const int start)/向下調(diào)整使start到currentsize-1的子表成為最大堆Int i=start，j=2 * I 1；/j是I的左邊孩子Int tablesize=currentsizetype temp=arrI；While(j=currentsize-1)if(j=ar

10、rj)break；else arrI=arrj；I=j；j=2 * j 1；arrI=temp；(2)排序堆Template /排序堆Void sortlist:heapsort()Int tablesize=currentsizefor(int I=(current size-2)/2；I=0；I-)降級過濾器(I)；/初始堆for(int I=current size-1；I=1；I-)Swap(arr0、arrI)；/與堆頂部元素交換最后一個元素current size-；過濾器降級(0)；/重建最大堆Cout num 行排序結(jié)果為： ；for(int t=0)；tvoid sortlist 336033601 merge(sortlistsourcetable、sortlistmergedtable、const int left、const int mid、const int rightInt i=left，j=mid 1，k=left/初始化指針/i是上一段中當(dāng)前元素的位置，j是后續(xù)段中當(dāng)前元素的位置，k是輔助數(shù)組的當(dāng)前位置While(i=midj=right)if(source table .