數(shù)據結構各種排序算法的時間性能(編輯修改稿)
2025-07-22 07:23 本頁面
【文章內容簡介】 ++。 } } } QueryPerformanceCounter(amp。Count2)。//獲取時間Count2 d=(double)()/(double)*。//計算時間差，d的單位為ms. cout冒泡排序算法對thisRanNum個隨機數(shù)排序時間為d ms.endl。 cout冒泡排序算法對thisRanNum個隨機數(shù)交換次數(shù)為thisSortNum次。endl。 } (5) 堆排序：堆排序與其他排序算法最大的區(qū)別是它依靠一種特殊的數(shù)據結構——堆來進行排序。堆是一種完全二叉樹，并且根節(jié)點不大于左右子樹中的所有節(jié)點，n[i]=n[2*i]amp。amp。n[i]=n[2*i+1]。因此堆排序算法首先要將給出的無序數(shù)組構造成一個堆，然后輸出根節(jié)點（最小元素），將剩余元素重新恢復成堆，再次輸出根節(jié)點。依次類推，直至最后一個節(jié)點輸出，此時堆排序完成。void Sort::heapRestor(unsigned long int *s,int i,int m) { int ma。 if((i=m/2)amp。amp。(s[i]min(s[2*i],s[2*i+1]))) { if(s[2*i]s[2*i+1]) { ma=s[i]。 s[i]=s[2*i]。 s[2*i]=ma。 thisheapRestor(s,2*i,m)。 } else { ma=s[i]。 s[i]=s[2*i+1]。 s[2*i+1]=ma。 thisheapRestor(s,2*i+1,m)。 } thisSortNum=thisSortNum+2。 } else if(i=m/2) thisSortNum++。}void Sort::heapCreat(unsigned long int *s,int m){ int num。 for(num=m/2。num=1。num) thisheapRestor(s,num,m)。}void Sort::heapSort(unsigned long int *s1,unsigned long int *s2){ thissetNum()。 int i,num。 num=thisRanNum。 LARGE_INTEGER Freg。 LARGE_INTEGER Count1,Count2。 QueryPerformanceFrequency(amp。Freg)。 QueryPerformanceCounter(amp。Count1)。//獲取時間Count1 double d。 thisheapCreat(s1,thisRanNum)。 for(i=0。ithisRanNum。i++) { s2[i]=s1[1]。 s1[1]=s1[num]。 thisheapRestor(s1,1,num)。 } QueryPerformanceCounter(amp。Count2)。//獲取時間Count2 d=(double)()/(double)*。//計算時間差，d的單位為ms. cout堆排序算法對thisRanNum個隨機數(shù)排序時間為為d ms.endl。 cout堆排序算法對thisRanNum個隨機數(shù)交換次數(shù)為thisSortNum次。endl。} (6) 合并排序：這里的合并排序和下邊要描述的快速排序都采用了分而治之的思想，但兩者仍然有很大差異。合并排序是將一個無序數(shù)組n[1…r]分成兩個數(shù)組n[1…r/2]與n[r/2+1…r]，分別對這兩個小數(shù)組進行合并排序，然后再將這兩個數(shù)組合并成一個大數(shù)組。由此我們看出合并排序時一個遞歸過程（非遞歸合并排序這里不做討論）。合并排序的主要工作便是“合并”，兩個小規(guī)模數(shù)組合并成大的，兩個大的再合并成更大的，當然元素比較式在合并的過程中進行的。void Sort::mergeSort(unsigned long int *s,int left,int right){ int i。 if(left right){ i=(left + right)/2。 mergeSort(s,left, i)。 mergeSort(s, i + 1, right)。 Merge(s, left, i, right)。 }}int Sort::partition(unsigned long int *s,int low,int high){ int key,i,p,r。 p=low。 r=high。 key=s[p]。 while(pr) { for(i=r。ip。i) { if(s[i]=key) { s[p]=s[r]。 p++。 thisSortNum++。 break。 } r。 thisSortNum++。 } for(i=p。ir。i++) { if(s[i]key) { s[r]=s[p]。 r。 thisSortNum++。 break。 } p++。 thisSortNum++。 } } s[p]=key。 return p
化學相關推薦
鄂ICP備17016276號-1