算法第二章总结

一、分治法体会

　　分治法的主要思想就是将一个规模较大的问题，分解成若干个想的、规模小的问题。但经常会出现一次分解后，规模依旧较大的情况。这时就要用到递归的方法对其进行递归分解。所以，递归在分治法的使用中占据着重要地位。

　　分治法最重要的几个例子，如下：

　　　　1、快速排序（QuickSort）：

 1 public class QuickSort {
 2
 3     public static void quickSort(int[] a){
 4         quickSort(a, 0, a.length - 1);
 5     }
 6
 7     private static void quickSort(int[] a, int left, int right){
 8         int pivotpos;
 9         if(left < right){
10             pivotpos = Partition(a, left ,right);
11             quickSort(a, left, pivotpos-1);
12             quickSort(a, pivotpos+1, right);
13         }
14     }
15     private static int Partition(int[] a, int p, int r){
16         int i = p, j = r + 1;
17         int pivot = a[p];
18
19         while(true){
20             while(a[++i] < pivot){}
21             while(a[--j] > pivot){}
22             if(i < j){
23                 swap(a, i, j);
24             }
25             else{
26                 break;
27             }
28         }
29
30         swap(a, j, p);
31         return j;
32     }
33
34     private static void swap(int[] a, int x, int y){
35         int temp = a[x];
36         a[x] = a[y];
37         a[y] = temp;
38     }
39
40 }

View Code

　　　　2、二分查找：

 1 public class MergeSort {
 2
 3     public static void mergeSort(int[] a){
 4         int[] tempArray = new int[a.length];
 5
 6         mergeSort(a, tempArray, 0, a.length - 1);
 7     }
 8
 9     private static void mergeSort(int[] a, int[] tempArray, int left, int right){
10         if(left < right){
11             int center = (left + right) / 2;
12             mergeSort(a, tempArray, left, center);
13             mergeSort(a, tempArray, center + 1, right);
14             merge(a, tempArray, left, center + 1, right);
15         }
16     }
17
18     private static void merge(int[] a, int[] tempArray, int leftPos, int rightPos, int rightEnd) {
19         int leftEnd = rightPos - 1;
20         int tempPos = leftPos;
21         int num = rightEnd - leftPos + 1;
22
23         while(leftPos <= leftEnd && rightPos <= rightEnd){
24             if(a[leftPos] <= a[rightPos]){
25                 tempArray[tempPos++] = a[leftPos++];
26             }else{
27                 tempArray[tempPos++] = a[rightPos++];
28             }
29         }
30
31         while(leftPos <= leftEnd){
32             tempArray[tempPos++]  = a[leftPos++];
33         }
34         while(rightPos <= rightEnd){
35             tempArray[tempPos++]  = a[rightPos++];
36         }
37
38         for(int i = 0; i < num; i++, rightEnd--){
39             a[rightEnd] = tempArray[rightEnd];
40         }
41
42     }
43
44 }

View Code

以上代码参考自https://blog.csdn.net/why_still_confused/article/details/51755899（虽是Java语言，但本人认为完成度较好）

二、结对编程汇报

　　主要是通过分配任务完成，合作不足，交流较少，思维方式差距较大，较难理解，没有明显互助提升。