計算機軟件及應(yīng)用ACM程序設(shè)計常用算法與數(shù)據(jù)結(jié)構(gòu)參考

1、ACM程序設(shè)計常用算法與 數(shù)據(jù)結(jié)構(gòu)參考 Tomsdinary目錄 TOC o 1-3 h z u HYPERLINK l _Toc240089722前言 PAGEREF _Toc240089722 h 6 HYPERLINK l _Toc240089723排序算法 PAGEREF _Toc240089723 h 7 HYPERLINK l _Toc240089724插入排序 PAGEREF _Toc240089724 h 7 HYPERLINK l _Toc240089725選擇排序 PAGEREF _Toc240089725 h 9 HYPERLINK l _Toc240089726冒泡排序

2、 PAGEREF _Toc240089726 h 10 HYPERLINK l _Toc240089727希爾排序 PAGEREF _Toc240089727 h 11 HYPERLINK l _Toc240089728隨機化快速排序 PAGEREF _Toc240089728 h 13 HYPERLINK l _Toc240089729歸并排序 PAGEREF _Toc240089729 h 16 HYPERLINK l _Toc240089730堆排序 PAGEREF _Toc240089730 h 18 HYPERLINK l _Toc240089731大整數(shù)處理 PAGEREF _To

3、c240089731 h 21 HYPERLINK l _Toc240089732包含頭文件 PAGEREF _Toc240089732 h 21 HYPERLINK l _Toc240089733定義 PAGEREF _Toc240089733 h 21 HYPERLINK l _Toc240089734實現(xiàn) PAGEREF _Toc240089734 h 23 HYPERLINK l _Toc240089735流輸出 PAGEREF _Toc240089735 h 23 HYPERLINK l _Toc240089736流輸入 PAGEREF _Toc240089736 h 23 HYPE

4、RLINK l _Toc240089737賦值 PAGEREF _Toc240089737 h 23 HYPERLINK l _Toc240089738轉(zhuǎn)換函數(shù) PAGEREF _Toc240089738 h 24 HYPERLINK l _Toc240089739規(guī)范化符號化 PAGEREF _Toc240089739 h 25 HYPERLINK l _Toc240089740帶符號乘法 PAGEREF _Toc240089740 h 26 HYPERLINK l _Toc240089741無符號取模 PAGEREF _Toc240089741 h 26 HYPERLINK l _Toc2

5、40089742整數(shù)乘法 PAGEREF _Toc240089742 h 27 HYPERLINK l _Toc240089743整數(shù)加法 PAGEREF _Toc240089743 h 29 HYPERLINK l _Toc240089744帶符號加法 PAGEREF _Toc240089744 h 31 HYPERLINK l _Toc240089745浮點乘法 PAGEREF _Toc240089745 h 32 HYPERLINK l _Toc240089746浮點加法 PAGEREF _Toc240089746 h 33 HYPERLINK l _Toc240089747帶符號減法

6、PAGEREF _Toc240089747 h 35 HYPERLINK l _Toc240089748整數(shù)減法 PAGEREF _Toc240089748 h 36 HYPERLINK l _Toc240089749浮點減法 PAGEREF _Toc240089749 h 38 HYPERLINK l _Toc240089750帶符號比較 PAGEREF _Toc240089750 h 40 HYPERLINK l _Toc240089751無符號比較 PAGEREF _Toc240089751 h 40 HYPERLINK l _Toc240089752無符號乘方 PAGEREF _Toc

7、240089752 h 42 HYPERLINK l _Toc240089753帶符號乘方 PAGEREF _Toc240089753 h 42 HYPERLINK l _Toc240089754使用方法 PAGEREF _Toc240089754 h 42 HYPERLINK l _Toc240089755高級數(shù)據(jù)結(jié)構(gòu) PAGEREF _Toc240089755 h 43 HYPERLINK l _Toc240089756普通二叉搜素樹 PAGEREF _Toc240089756 h 43 HYPERLINK l _Toc240089757包含頭文件 PAGEREF _Toc24008975

8、7 h 43 HYPERLINK l _Toc240089758定義 PAGEREF _Toc240089758 h 43 HYPERLINK l _Toc240089759實現(xiàn) PAGEREF _Toc240089759 h 46 HYPERLINK l _Toc240089760刪樹 PAGEREF _Toc240089760 h 49 HYPERLINK l _Toc240089761插入元素到樹 PAGEREF _Toc240089761 h 49 HYPERLINK l _Toc240089762復(fù)制樹 PAGEREF _Toc240089762 h 52 HYPERLINK l _

9、Toc240089763求樹的高度 PAGEREF _Toc240089763 h 55 HYPERLINK l _Toc240089764求葉子的個數(shù) PAGEREF _Toc240089764 h 56 HYPERLINK l _Toc240089765刪除元素 PAGEREF _Toc240089765 h 56 HYPERLINK l _Toc240089766使用方法 PAGEREF _Toc240089766 h 58 HYPERLINK l _Toc240089767基本線段樹模式 PAGEREF _Toc240089767 h 59 HYPERLINK l _Toc240089

10、768基本并查集模式 PAGEREF _Toc240089768 h 61 HYPERLINK l _Toc240089769散列實現(xiàn)的一種方式參考 PAGEREF _Toc240089769 h 62 HYPERLINK l _Toc240089770定義與實現(xiàn) PAGEREF _Toc240089770 h 62 HYPERLINK l _Toc240089771使用方法 PAGEREF _Toc240089771 h 71 HYPERLINK l _Toc240089772堆 PAGEREF _Toc240089772 h 71 HYPERLINK l _Toc240089773包含頭文

11、件 PAGEREF _Toc240089773 h 71 HYPERLINK l _Toc240089774定義與實現(xiàn) PAGEREF _Toc240089774 h 71 HYPERLINK l _Toc240089775使用方法 PAGEREF _Toc240089775 h 74 HYPERLINK l _Toc240089776圖相關(guān)算法 PAGEREF _Toc240089776 h 74 HYPERLINK l _Toc240089777圖的深度優(yōu)先和廣度優(yōu)先算法舉例 PAGEREF _Toc240089777 h 74 HYPERLINK l _Toc240089778無向圖最小

12、生成樹的Kruskal算法舉例 PAGEREF _Toc240089778 h 77 HYPERLINK l _Toc240089779無向圖最小生成樹的Prim算法舉例 PAGEREF _Toc240089779 h 79 HYPERLINK l _Toc240089780有向圖的單源最短路徑Dijkstra算法舉例 PAGEREF _Toc240089780 h 81 HYPERLINK l _Toc240089781有向圖的多源最短路徑Floyd算法舉例 PAGEREF _Toc240089781 h 82 HYPERLINK l _Toc240089782拓撲排序舉例 PAGEREF

13、_Toc240089782 h 84 HYPERLINK l _Toc240089783AOE網(wǎng)的算法舉例 PAGEREF _Toc240089783 h 86 HYPERLINK l _Toc240089784求圖的一個中心算法舉例 PAGEREF _Toc240089784 h 91 HYPERLINK l _Toc240089785求圖的P個中心算法舉例 PAGEREF _Toc240089785 h 93 HYPERLINK l _Toc240089786SPFA算法舉例 PAGEREF _Toc240089786 h 98 HYPERLINK l _Toc240089787割頂和塊的

14、算法舉例 PAGEREF _Toc240089787 h 100 HYPERLINK l _Toc240089788計算幾何算法 PAGEREF _Toc240089788 h 103 HYPERLINK l _Toc240089789向量模 PAGEREF _Toc240089789 h 103 HYPERLINK l _Toc240089790向量點積 PAGEREF _Toc240089790 h 104 HYPERLINK l _Toc240089791向量叉積 PAGEREF _Toc240089791 h 104 HYPERLINK l _Toc240089792左右判斷 PAGE

15、REF _Toc240089792 h 104 HYPERLINK l _Toc240089793相交判斷 PAGEREF _Toc240089793 h 104 HYPERLINK l _Toc240089794正規(guī)相交交點 PAGEREF _Toc240089794 h 105 HYPERLINK l _Toc240089795判斷多邊形凸 PAGEREF _Toc240089795 h 105 HYPERLINK l _Toc240089796任意多變形面積 PAGEREF _Toc240089796 h 106 HYPERLINK l _Toc240089797凸包問題的快包實現(xiàn)舉例

16、PAGEREF _Toc240089797 h 106 HYPERLINK l _Toc240089798STL算法參考 PAGEREF _Toc240089798 h 111 HYPERLINK l _Toc240089799accumulate() PAGEREF _Toc240089799 h 111 HYPERLINK l _Toc240089800adjacent_difference() PAGEREF _Toc240089800 h 111 HYPERLINK l _Toc240089801adjacent_find() PAGEREF _Toc240089801 h 112 H

17、YPERLINK l _Toc240089802binary_search() PAGEREF _Toc240089802 h 112 HYPERLINK l _Toc240089803copy() PAGEREF _Toc240089803 h 113 HYPERLINK l _Toc240089804copy_backward() PAGEREF _Toc240089804 h 113 HYPERLINK l _Toc240089805count() PAGEREF _Toc240089805 h 113 HYPERLINK l _Toc240089806count_if() PAGERE

18、F _Toc240089806 h 114 HYPERLINK l _Toc240089807equal() PAGEREF _Toc240089807 h 114 HYPERLINK l _Toc240089808equal_range() PAGEREF _Toc240089808 h 114 HYPERLINK l _Toc240089809fill() PAGEREF _Toc240089809 h 115 HYPERLINK l _Toc240089810fill_n() PAGEREF _Toc240089810 h 115 HYPERLINK l _Toc240089811fin

19、d() PAGEREF _Toc240089811 h 115 HYPERLINK l _Toc240089812find_if() PAGEREF _Toc240089812 h 115 HYPERLINK l _Toc240089813find_end() PAGEREF _Toc240089813 h 116 HYPERLINK l _Toc240089814find_first_of() PAGEREF _Toc240089814 h 116 HYPERLINK l _Toc240089815for_each() PAGEREF _Toc240089815 h 117 HYPERLIN

20、K l _Toc240089816generate() PAGEREF _Toc240089816 h 117 HYPERLINK l _Toc240089817generate_n() PAGEREF _Toc240089817 h 117 HYPERLINK l _Toc240089818includes() PAGEREF _Toc240089818 h 117 HYPERLINK l _Toc240089819inner_product() PAGEREF _Toc240089819 h 118 HYPERLINK l _Toc240089820inplace_merge() PAGE

21、REF _Toc240089820 h 118 HYPERLINK l _Toc240089821iter_swap() PAGEREF _Toc240089821 h 119 HYPERLINK l _Toc240089822lexicographical_compare() PAGEREF _Toc240089822 h 119 HYPERLINK l _Toc240089823lower_bound() PAGEREF _Toc240089823 h 120 HYPERLINK l _Toc240089824max() PAGEREF _Toc240089824 h 120 HYPERL

22、INK l _Toc240089825max_element() PAGEREF _Toc240089825 h 120 HYPERLINK l _Toc240089826min() PAGEREF _Toc240089826 h 121 HYPERLINK l _Toc240089827min_element() PAGEREF _Toc240089827 h 121 HYPERLINK l _Toc240089828merge() PAGEREF _Toc240089828 h 121 HYPERLINK l _Toc240089829mismatch() PAGEREF _Toc2400

23、89829 h 122 HYPERLINK l _Toc240089830next_permutation() PAGEREF _Toc240089830 h 122 HYPERLINK l _Toc240089831nnth_element() PAGEREF _Toc240089831 h 123 HYPERLINK l _Toc240089832partial_sort() PAGEREF _Toc240089832 h 123 HYPERLINK l _Toc240089833partial_sort_copy() PAGEREF _Toc240089833 h 124 HYPERLI

24、NK l _Toc240089834partial_sum() PAGEREF _Toc240089834 h 124 HYPERLINK l _Toc240089835prev_permutation() PAGEREF _Toc240089835 h 125 HYPERLINK l _Toc240089836random_shuffle() PAGEREF _Toc240089836 h 125 HYPERLINK l _Toc240089837remove() PAGEREF _Toc240089837 h 125 HYPERLINK l _Toc240089838remove_copy

25、() PAGEREF _Toc240089838 h 126 HYPERLINK l _Toc240089839remove_if() PAGEREF _Toc240089839 h 126 HYPERLINK l _Toc240089840remove_copy_if() PAGEREF _Toc240089840 h 126 HYPERLINK l _Toc240089841replace() PAGEREF _Toc240089841 h 126 HYPERLINK l _Toc240089842replace_copy() PAGEREF _Toc240089842 h 127 HYP

26、ERLINK l _Toc240089843replace_if() PAGEREF _Toc240089843 h 127 HYPERLINK l _Toc240089844replace_copy_if() PAGEREF _Toc240089844 h 127 HYPERLINK l _Toc240089845reverse() PAGEREF _Toc240089845 h 127 HYPERLINK l _Toc240089846reverse_copy() PAGEREF _Toc240089846 h 128 HYPERLINK l _Toc240089847rotate() P

27、AGEREF _Toc240089847 h 128 HYPERLINK l _Toc240089848rotate_copy() PAGEREF _Toc240089848 h 128 HYPERLINK l _Toc240089849search() PAGEREF _Toc240089849 h 128 HYPERLINK l _Toc240089850search_n() PAGEREF _Toc240089850 h 129 HYPERLINK l _Toc240089851set_difference() PAGEREF _Toc240089851 h 129 HYPERLINK

28、l _Toc240089852set_intersection() PAGEREF _Toc240089852 h 130 HYPERLINK l _Toc240089853set_symmetric_difference() PAGEREF _Toc240089853 h 130 HYPERLINK l _Toc240089854set_union() PAGEREF _Toc240089854 h 131 HYPERLINK l _Toc240089855sort() PAGEREF _Toc240089855 h 131 HYPERLINK l _Toc240089856stable_p

29、artition() PAGEREF _Toc240089856 h 132 HYPERLINK l _Toc240089857stable_sort() PAGEREF _Toc240089857 h 132 HYPERLINK l _Toc240089858swap() PAGEREF _Toc240089858 h 132 HYPERLINK l _Toc240089859swap_range() PAGEREF _Toc240089859 h 132 HYPERLINK l _Toc240089860transform() PAGEREF _Toc240089860 h 133 HYP

30、ERLINK l _Toc240089861unique() PAGEREF _Toc240089861 h 133 HYPERLINK l _Toc240089862unique_copy() PAGEREF _Toc240089862 h 134 HYPERLINK l _Toc240089863upper_bound() PAGEREF _Toc240089863 h 134 HYPERLINK l _Toc240089864make_heap() PAGEREF _Toc240089864 h 135 HYPERLINK l _Toc240089865pop_heap() PAGERE

31、F _Toc240089865 h 135 HYPERLINK l _Toc240089866push_heap() PAGEREF _Toc240089866 h 135 HYPERLINK l _Toc240089867sort_heap() PAGEREF _Toc240089867 h 136 HYPERLINK l _Toc240089868字符串處理 PAGEREF _Toc240089868 h 136 HYPERLINK l _Toc240089869KMP算法舉例 PAGEREF _Toc240089869 h 136 HYPERLINK l _Toc240089870C+語

32、言可用頭文件 PAGEREF _Toc240089870 h 138 HYPERLINK l _Toc240089871 PAGEREF _Toc240089871 h 138 HYPERLINK l _Toc240089872 PAGEREF _Toc240089872 h 138 HYPERLINK l _Toc240089873 PAGEREF _Toc240089873 h 138 HYPERLINK l _Toc240089874 PAGEREF _Toc240089874 h 138 HYPERLINK l _Toc240089875 PAGEREF _Toc240089875 h

33、 138 HYPERLINK l _Toc240089876 PAGEREF _Toc240089876 h 139 HYPERLINK l _Toc240089877 PAGEREF _Toc240089877 h 139 HYPERLINK l _Toc240089878 PAGEREF _Toc240089878 h 139 HYPERLINK l _Toc240089879 PAGEREF _Toc240089879 h 139 HYPERLINK l _Toc240089880 PAGEREF _Toc240089880 h 139 HYPERLINK l _Toc240089881

34、 PAGEREF _Toc240089881 h 139 HYPERLINK l _Toc240089882 PAGEREF _Toc240089882 h 139 HYPERLINK l _Toc240089883 PAGEREF _Toc240089883 h 139 HYPERLINK l _Toc240089884 PAGEREF _Toc240089884 h 140 HYPERLINK l _Toc240089885 PAGEREF _Toc240089885 h 140 HYPERLINK l _Toc240089886 PAGEREF _Toc240089886 h 140 H

35、YPERLINK l _Toc240089887 PAGEREF _Toc240089887 h 140 HYPERLINK l _Toc240089888 PAGEREF _Toc240089888 h 140 HYPERLINK l _Toc240089889 PAGEREF _Toc240089889 h 140 HYPERLINK l _Toc240089890 PAGEREF _Toc240089890 h 140 HYPERLINK l _Toc240089891 PAGEREF _Toc240089891 h 141 HYPERLINK l _Toc240089892 PAGER

36、EF _Toc240089892 h 141 HYPERLINK l _Toc240089893 PAGEREF _Toc240089893 h 141 HYPERLINK l _Toc240089894 PAGEREF _Toc240089894 h 141 HYPERLINK l _Toc240089895 PAGEREF _Toc240089895 h 141 HYPERLINK l _Toc240089896 PAGEREF _Toc240089896 h 141 HYPERLINK l _Toc240089897 PAGEREF _Toc240089897 h 141 HYPERLI

37、NK l _Toc240089898 PAGEREF _Toc240089898 h 141 HYPERLINK l _Toc240089899 PAGEREF _Toc240089899 h 142 HYPERLINK l _Toc240089900 PAGEREF _Toc240089900 h 142 HYPERLINK l _Toc240089901 PAGEREF _Toc240089901 h 142 HYPERLINK l _Toc240089902 PAGEREF _Toc240089902 h 142 HYPERLINK l _Toc240089903 PAGEREF _To

38、c240089903 h 142 HYPERLINK l _Toc240089904 PAGEREF _Toc240089904 h 142 HYPERLINK l _Toc240089905 PAGEREF _Toc240089905 h 142 HYPERLINK l _Toc240089906 PAGEREF _Toc240089906 h 142 HYPERLINK l _Toc240089907 PAGEREF _Toc240089907 h 143 HYPERLINK l _Toc240089908 PAGEREF _Toc240089908 h 143 HYPERLINK l _

39、Toc240089909 PAGEREF _Toc240089909 h 143 HYPERLINK l _Toc240089910 PAGEREF _Toc240089910 h 143 HYPERLINK l _Toc240089911 PAGEREF _Toc240089911 h 143 HYPERLINK l _Toc240089912 PAGEREF _Toc240089912 h 143 HYPERLINK l _Toc240089913 PAGEREF _Toc240089913 h 143 HYPERLINK l _Toc240089914 PAGEREF _Toc24008

40、9914 h 143 HYPERLINK l _Toc240089915 PAGEREF _Toc240089915 h 143 HYPERLINK l _Toc240089916 PAGEREF _Toc240089916 h 144 HYPERLINK l _Toc240089917 PAGEREF _Toc240089917 h 144 HYPERLINK l _Toc240089918 PAGEREF _Toc240089918 h 144 HYPERLINK l _Toc240089919 PAGEREF _Toc240089919 h 144 HYPERLINK l _Toc240

41、089920 PAGEREF _Toc240089920 h 144 HYPERLINK l _Toc240089921 PAGEREF _Toc240089921 h 144前言 如今的程序設(shè)計已不再是個人英雄時代了，程序的設(shè)計和開發(fā)實施需要靠團隊成員的積極配合和合作。軟件技術(shù)在當(dāng)今時代已不是信息技術(shù)競爭核心，對于技術(shù)知識的獲取變得不再重要。當(dāng)今IT競爭，靠的是先進的觀念，有效的溝通和合作，靠的是高瞻遠矚的預(yù)見能力，靠的是個人的想法而絕不是技能。當(dāng)然掌握好眾多技術(shù)是實現(xiàn)我們獨特創(chuàng)意的途徑，但絕不是我們可以屹立IT界的根本法寶。 隨著互聯(lián)網(wǎng)發(fā)展的不斷深入，技術(shù)知識的獲取不再成為問題。程序員不能

42、單靠通曉某一核心技術(shù)而獲得核心競爭力。當(dāng)今的IT界知識分享，知識交流，知識開放是主旋律，凡是開放的平臺，開放的個人，開放的公司才是真正擁有競爭力的，凡是那些封閉的平臺，封閉的個人，封閉的公司其發(fā)展的道路終會是艱難的。而這種開放的態(tài)度在中國程序員中更應(yīng)該得到普及與遵守。其根本在于中國程序員中的高手充其量也只是一個高級用戶，真正的技術(shù)掌握在技術(shù)公司那里。所以為什么還有保留一些使用技巧呢。不開放不分享不合作，優(yōu)秀的程序員中會淪為平庸的人。 基于以上思考和論斷，我將自己三年在算法設(shè)計和數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)過程中可供借鑒和參考使用的代碼總結(jié)如下。一方面作為我們隊參加ACM的內(nèi)部參考資料，另一方面分享出來供后來者

43、學(xué)習(xí)參考?；蛟S對諸位會有點幫助。同時也請您記住和接受以上觀點，在一個分享交流的環(huán)境你，你的技術(shù)進步會更加迅速。也希望那些有好代碼，好思想的高手將自己的智慧分享出來。整理出來。這不僅有利于個人學(xué)習(xí)總結(jié)，更有利于我們懷化學(xué)院ACM隊伍健康發(fā)展。排序算法插入排序/*函數(shù)名： InsertionSort功能： 插入排序模板參數(shù)說明：T必須支持小于操作參數(shù)說明： data待排序數(shù)組, size待排序數(shù)組大小前置條件： data!=NULL, size0后置條件： data按非降序排列用法： int arr=10,9,8,4,5,7,6,3,1,4; InsertionSort(arr, 10);*/te

44、mplate void InsertionSort (T data, int size)int i,j; T temp;for (i=1; i0 & temp0后置條件： data按f排列用法： bool cmp(int a, int b) return ab; int arr=10,9,8,4,5,7,6,3,1,4;InsertionSort(arr, 10, cmp);*/template void InsertionSort (T data, int size, Func f)int i,j; T temp;for (i=1; i0 & f(temp,dataj-1); -j)data

45、j=dataj-1;dataj=temp;選擇排序/*函數(shù)名： SelectionSort功能： 選擇排序模板參數(shù)說明：T必須支持小于操作參數(shù)說明： data待排序數(shù)組, size待排序數(shù)組大小前置條件： data!=NULL, size0后置條件： data按非降序排列用法： #include int arr=10,9,8,4,5,7,6,3,1,4;SelectionSort(arr, 10);*/template void SelectionSort (T data, int size)int i,j,k; for (i=0; isize-1; +i)k=i;for (j=i+1; js

46、ize; +j)if (dataj0后置條件： data按f排列用法： #include int arr=10,9,8,4,5,7,6,3,1,4;bool cmp(int a, int b) return ab; SelectionSort(arr, 10, cmp);*/template void SelectionSort (T data, int size, Func f)int i,j,k; for (i=0; isize-1; +i)k=i;for (j=i+1; j0后置條件： data按非降序排列用法： #include int arr=10,9,8,4,5,7,6,3,1,4

47、;BubbleSort(arr, 10);*/template void BubbleSort (T data, int size)int i,j;for (i=0; ii; -j)if (dataj0后置條件： data按f序排列用法： #include bool cmp(int a, int b) return ab; int arr=10,9,8,4,5,7,6,3,1,4;BubbleSort(arr, 10, cmp);*/template void BubbleSort (T data, int size, Func f)int i,j;for (i=0; ii; -j)if (f

48、(dataj,dataj-1)std:swap(dataj, dataj-1);希爾排序/*函數(shù)名： ShellSort功能： 希爾排序模板參數(shù)說明：T必須支持小于操作參數(shù)說明： data待排序數(shù)組, size待排序數(shù)組大小前置條件： data!=NULL, size0后置條件： data按非降序序排列用法： int arr=10,9,8,4,5,7,6,3,1,4;ShellSort(arr, 10);*/template void ShellSort (T data, int size)int i, j, hCnt, h;int array20, k;T temp;for (h=1, i=

49、0; h=0; -i)h=arrayi;for (hCnt=h; hCnt2*h; +hCnt) for (j=hCnt; j=0 & temp0后置條件： data按f排列用法： bool cmp(int a, int b) return ab; int arr=10,9,8,4,5,7,6,3,1,4;ShellSort(arr, 10, cmp);*/template void ShellSort (T data, int size, Func f)int i, j, hCnt, h;int array20, k;T temp;for (h=1, i=0; h=0; -i)h=array

50、i;for (hCnt=h; hCnt2*h; +hCnt) for (j=hCnt; j=0 & f(temp,datak-h)datak=datak-h;k-=h;datak=temp;j+=h;隨機化快速排序/*函數(shù)名： quick_sort功能： 快速排序輔助過程*/template void quick_sort (T data, int frist, int last)int lower=frist+1;int upper=last;int t=rand()%(last-frist)+frist;std:swap(datafrist, datat);T& bound=datafri

51、st;while (lower=upper)while (datalowerbound)+lower;while (bounddataupper)-upper;if (lowerupper)std:swap(datalower, dataupper);+lower;-upper;else+lower;std:swap(dataupper, datafrist);if (fristupper-1)quick_sort(data, frist, upper-1);if (upper+10后置條件： data按f排列用法： #include #include #include int arr=10,

52、9,8,4,5,7,6,3,1,4;QuickSort(arr, 10);*/template void QuickSort (T data, int size)int i, max;if (size2)return;for (i=1, max=0; isize; +i) if (datamaxdatai)max=i;std:swap(datasize-1, datamax);srand(time(0);quick_sort(data, 0, size-2);/*函數(shù)名： quick_sort功能： 快速排序輔助過程*/template void quick_sort (T data, int

53、 frist, int last, Func& f)int lower=frist+1;int upper=last;int t=rand()%(last-frist)+frist;std:swap(datafrist, datat);T& bound=datafrist;while (lower=upper)while (f(datalower,bound)+lower;while (f(bound,dataupper)-upper;if (lowerupper)std:swap(datalower, dataupper);+lower;-upper;else+lower;std:swap(

54、dataupper, datafrist);if (fristupper-1)quick_sort(data, frist, upper-1, f);if (upper+10后置條件： data按f排列用法： #include #include #include bool cmp(int a, int b) return ab; int arr=10,9,8,4,5,7,6,3,1,4;QuickSort(arr, 10, cmp);*/template void QuickSort (T data, int size, Func f)int i, max;if (size2)return;f

55、or (i=1, max=0; i0后置條件： data按非降序排列用法： #include int arr=10,9,8,4,5,7,6,3,1,4;MergeSort(arr, 10);*/template void MergeSort (T data, int size)if ( size1 )/預(yù)處理int mid=size/2;int numOfleft=mid;int numOfright=size-mid;T* left=new TnumOfleft;T* right=new TnumOfright;/分std:copy(data, data+numOfleft, left);s

56、td:copy(data+numOfleft, data+size, right);MergeSort(left, numOfleft);MergeSort(right, numOfright);/合std:merge(left, left+numOfleft, right, right+numOfright, data);/清理delete left;delete right;/*函數(shù)名： MergeSort功能： 歸并排序模板參數(shù)說明：T元素類型, Func函數(shù)對象或指針參數(shù)說明： data待排序數(shù)組, size待排序數(shù)組大小,f函數(shù)對象或指針前置條件： data!=NULL, size0

57、后置條件： data按f排列用法： #include bool cmp(int a, int b) return ab; int arr=10,9,8,4,5,7,6,3,1,4;MergeSort(arr, 10，cmp);*/template void MergeSort (T data, int size, Func f)if ( size1 )int mid=size/2;int numOfleft=mid;int numOfright=size-mid;T* left=new TnumOfleft;T* right=new TnumOfright;std:copy(data, dat

58、a+numOfleft, left);std:copy(data+numOfleft, data+size, right);MergeSort(left, numOfleft, f);MergeSort(right, numOfright, f);std:merge(left, left+numOfleft, right, right+numOfright, data, f);delete left;delete right;堆排序/*函數(shù)名： heap_down功能： 堆排序輔助過程*/template void heap_down (T data, int i, const int& si

59、ze)int p=i*2+1;while ( psize )if ( p+1size )if ( datapdatap+1 )+p;if ( datai0后置條件： data按非降序排列用法： #include int arr=10,9,8,4,5,7,6,3,1,4;MergeSort(arr, 10);*/template void HeapSort (T data, int size)int i;for (i=(size-1)/2; i=0; -i)heap_down(data, i, size);for (i=size-1; i0; -i)std:swap(data0, datai);

60、heap_down(data, 0, i);/*函數(shù)名： heap_down功能： 堆排序輔助過程*/template void heap_down (T data, int i, const int& size, Func& f)int p=i*2+1;while ( psize )if ( p+10后置條件： data按f排列用法： #include bool cmp(int a, int b) return ab; int arr=10,9,8,4,5,7,6,3,1,4;HeapSort(arr, 10，cmp);*/template void HeapSort (T data, in