各種內(nèi)排序算法的實(shí)現(xiàn)及性能的比較(已修改)
2025-06-28 07:41 本頁面
【正文】 實(shí) 驗 報 告（2015/2016學(xué)年 第2學(xué)期）課程名稱數(shù)據(jù)結(jié)構(gòu)A實(shí)驗名稱各種內(nèi)排序算法的實(shí)現(xiàn)及性能的比較實(shí)驗時間2016年6月20日指導(dǎo)單位計算機(jī)科學(xué)與技術(shù)系指導(dǎo)教師駱健學(xué)生姓名班級學(xué)號學(xué)院(系) 管理學(xué)院專 業(yè)信息管理與信息系統(tǒng)一、 問題陳述（1） 驗證教材的各種內(nèi)排序算法（2） 分析各種內(nèi)排序算法的時間復(fù)雜度（3） 改進(jìn)教材中的快速排序法，使得當(dāng)子集和小于10個元素時改用直接插入排序（4） 使用隨機(jī)數(shù)發(fā)生器產(chǎn)生大數(shù)據(jù)集合，運(yùn)行上述 各排序算法，使系統(tǒng)時鐘測量個算法所需的實(shí)際時間，并進(jìn)行比較。系統(tǒng)時鐘包含在頭文件“”中。二、概要設(shè)計 ，為主程序。三、詳細(xì)設(shè)計①簡單選擇排序：將初始序列（A[0]~A[n1]）作為待排序序列，第一趟在待排序序列（A[0]~A[n1]）中找最小元素，與該序列中第一個元素A[0]交換，這樣子序列（A[0]）有序，下一趟排序在帶牌子序列（A[1]~A[n1]）中進(jìn)行。第i趟排序子序列（A[i1]~A[n1]）中進(jìn)行。經(jīng)過n1趟排序后使得初始序列有序。程序流程圖：開始i=0in1Small=ij=i+1jnA[j]A[small]Small=jSwap(A[i],A[small])j++結(jié)束NNNYYi++②直接插入排序：一個元素插入到有序表中，首先將其存入臨時變量temp，然后從后往前查找插入位置。當(dāng)temp小于表中元素時，就將該元素后移一個位置，繼續(xù)比較、移動，直到temp大于等于表中元素或者到了有序表的第一個元素結(jié)束，這時就可將temp存入剛后移的元素的位置了。程序流程圖：開始inint j=iT temp=A[i]j0amp。amp。tempA[j1]A[j]=A[j1]。jA[j]=tempi++結(jié)束NYYN③冒泡排序：第一趟在序列（A[0]~A[n1]）中從前往后進(jìn)行兩個相鄰元素的比較，若后者小，則交換，比較n1次；第一趟排序結(jié)束，最大元素被交換到A[n1]中（即沉底）下一趟排序只需在子序列（A[0]~A[n2]）中進(jìn)行；如果在某一趟排序中未進(jìn)行交換元素，說明子序列已經(jīng)有序，則不再進(jìn)行下一趟排序。程序流程圖：開始i=n1i0last=0。j=0jiA[j+1]A[j]Swap(A[j],A[j+1])Last=ji=last結(jié)束NNYY④快速排序：取第一個元素作為分割元素，初始化i=left,j=right+1,i從左往右尋找第一個大于等于分割元素的元素，j從右往左找第一個小于等于分割元素的元素并交換，i和j繼續(xù)移動，重復(fù)上述步驟，直到當(dāng)i=j時將j與第一個元素交換。程序流程圖：開始leftrighti=left。j=righti++A[i]A[left]jA[j]A[left]ijSwap(A[i],A[j])ijSwap(A[left],A[j])Qsort(A,left,j1)Qsort(A,j+1,right)結(jié)束NYYNYNNYYN⑤兩路合并排序：將有n 個元素的序列看成是n個長度為1的有序子序列，然后兩兩合并子序列，得到[n/2]個長度為2或1的有序子序列，再兩兩合并…直到得到一個長度為n的有序序列時結(jié)束。程序流程圖：開始int size=1Sizeni1=1i1+sizeni2=i1+sizej1=i21i2+size1n1j2=n1Merge(A,i1,j1,i2,j2)i1=j2+1size*=2結(jié)束j2=i2+size1NYYNNY四、程序代碼include //簡單選擇排序template class Tvoid SelectSort(T A[], int n){ int small。for (int i=0。 in1。 i+
法律信息相關(guān)推薦
鄂ICP備17016276號-1