c++经典算法

26. int a; 27. cin>>a;

28. if(a == 0) 29. return NULL; 30. node *root=new node(); 31. root->value=a;

32. root->left=build_tree(); 33. root->right=build_tree(); 34. 35. cout<<\<value == v)

44. return true; 45. else find(root->left,v-root->value) || find(root->right,v-roo

t->value); 46. }

4.你熟悉的排序算法并描述算法复杂度。

快速排序

[cpp] view plain copy

1. #include 2. using namespace std; 3. 4. 5. 6. 7.

int partition(int a[],int low,int high) {

int key=a[low]; //用子表的第一个记录作杻轴记录 while(low < high) //从表的两端交替地向中间扫描

8. {

9. while(low < high && a[high] >= key) 10. --high; 11. { //将比杻轴记录小的记录交换到低端

12. int temp=a[low]; 13. a[low]=a[high];

14. a[high]=temp; 15. } 16. 17. while(low < high && a[low] <= key)

18. ++low; 19. { //将比杻轴记录大的记录交换到低端 20. int temp=a[low]; 21. a[low]=a[high];

22. a[high]=temp; 23. } 24. } 25. return low; //返回杻轴所在的位置 26. } 27. 28. void qsort(int a[],int b,int e) 29. { 30. if(b < e) 31. { 32. int m=partition(a,b,e); 33. qsort(a,b,m-1); 34. qsort(a,m+1,e); 35. } 36. } 37. 38. int main() 39. { 40. int a[]={2,3,7,8,3,5}; 41. qsort(a,0,5); 42. for(int i=0;i<6;i++) 43. cout<

归并排序

[cpp] view plain copy

1. #include 2. using namespace std;

3.

4. void display(int a[],int size) 5. 6. 7. 8.

{

for(int i=0;i

9. } 10. 11. void mmerge(int *a,int low,int middle ,int high ) 12. { 13. int fronArray[100],postArray[100]; 14. int front=middle-low+1; 15. int post=high-middle; 16. for(int i=0;i

25. int i=0,j=0; 26. for(int k=low;k<=high;k++) 27. { 28. if(fronArray[i]

33. } 34. 35. void merge_sort(int *a,int low,int high) 36. { 37. if(low

47. { 48. int a[]={9,3,5,7,6,8,10,22,21,34}; 49. display(a,10); 50. merge_sort(a,0,9); 51. display(a,10); 52. 53. return 0; 54. }

堆排序

[cpp] view plain copy

1. /* 2. 堆排序

3. (1)用大根堆排序的基本思想

4. ① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区

5. ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换， 6. 由此得到新的无序区R[1..n-1]和有序区R[n]，且满足

R[1..n-1].keys≤R[n].key

7. ③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为

堆。

8. 然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]

交换， 9. 由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系

R[1..n- 2].keys≤R[n-1..n].keys， 10. 同样要将R[1..n-2]调整为堆。

11. …… 12. 直到无序区只有一个元素为止。 13. (2)大根堆排序算法的基本操作： 14. ① 初始化操作：将R[1..n]构造为初始堆； 15. ② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。 16. 注意： 17. ①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。 18. ②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。 19. 堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前， 20. 且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。 21. */ 22. 23. #include 24.

25. using namespace std; 26. 27. //生成大根堆

28. void HeapAdjust(int SortData[],int StartIndex, int Length) 29. { 30. while(2*StartIndex+1 < Length) 31. { 32. int MaxChildrenIndex = 2*StartIndex+1 ; 33. if(2*StartIndex+2 < Length ) 34. { 35. //比较左子树和右子树，记录最大值的Index

36. if(SortData[2*StartIndex+1]

37. { 38. MaxChildrenIndex = 2*StartIndex+2; 39. } 40. } 41. if(SortData[StartIndex] < SortData[MaxChildrenIndex]) 42. { 43. //交换i与MinChildrenIndex的数据

44. int tmpData =SortData[StartIndex]; 45. SortData[StartIndex] =SortData[MaxChildrenIndex]; 46. SortData[MaxChildrenIndex] =tmpData; 47. //堆被破坏，需要重新调整 48. StartIndex = MaxChildrenIndex ; 49. }

50. else 51. { 52. //比较左右孩子均大则堆未破坏，不再需要调整 53. break; 54. } 55. } 56. } 57. 58. //堆排序

59. void HeapSortData(int SortData[], int Length) 60. { 61. int i=0; 62. 63. //将Hr[0,Length-1]建成大根堆 64. for (i=Length/2-1; i>=0; i--) 65. { 66. HeapAdjust(SortData, i, Length); 67. }