算法模板

一、基础算法

1、快排

 1 public static void quickSort(int l, int r, int[] arr) {
 2         if (l >= r) {
 3             return;
 4         }
 5         int base = arr[(r - l) / 2 + l];
 6         int i = l - 1, j = r + 1;
 7         while (i < j) {
 8             do i++; while (arr[i] < base);
 9             do j--; while (arr[j] > base);
10             if (i < j) swap(i, j, arr);
11         }
12         quickSort(l, j, arr);
13         quickSort(j + 1, r, arr);
14     }

2、归并

 1 public static void mergeSort(int l, int r, int[] arr) {
 2         if (l >= r) {
 3             return;
 4         }
 5         int mid = (l + r) / 2;
 6         mergeSort(l, mid, arr);
 7         mergeSort(mid + 1, r, arr);
 8         int i = l, j = mid + 1, k = 0;
 9         int[] tmp = new int[r - l + 1];
10         while (i <= mid && j <= r) {
11             if (arr[i] <= arr[j]) {
12                 tmp[k++] = arr[i++];
13             } else {
14                 tmp[k++] = arr[j++];
15             }
16         }
17         while (i <= mid) {
18             tmp[k++] = arr[i++];
19         }
20         while (j <= r) {
21             tmp[k++] = arr[j++];
22         }
23         // 最后将临时数组存储到arr中
24         for (int m = l, n = 0; m <= r; m++, n++) {
25             arr[m] = tmp[n];
26         }
27     }

3、整数二分

 1 bool check(int x) {/* ... */} // 检查x是否满足某种性质
 2 
 3 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
 4 int bsearch_1(int l, int r)
 5 {
 6     while (l < r)
 7     {
 8         int mid = l + r >> 1;
 9         if (check(mid)) r = mid;    // check()判断mid是否满足性质
10         else l = mid + 1;
11     }
12     return l;
13 }
14 // 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
15 int bsearch_2(int l, int r)
16 {
17     while (l < r)
18     {
19         int mid = l + r + 1 >> 1;
20         if (check(mid)) l = mid;
21         else r = mid - 1;
22     }
23     return l;
24 }

4、高精度加法

 1 public static List bigAdd(List v1, List v2) {
 2     List v3 = new ArrayList<>();
 3     // 进位
 4     int t = 0;
 5     for (int i = 0, j = 0; i < v1.size() || j < v2.size(); i++, j++) {
 6         if (i < v1.size() && v1.get(i) > 0) {
 7             t += v1.get(i);
 8         }
 9         if (j < v2.size() && v2.get(j) > 0) {
10             t += v2.get(j);
11         }
12         v3.add(t % 10);
13         // 更新t
14         t /= 10;
15     }
16     if (t > 0) {
17         v3.add(1);
18     }
19     return v3;
20 }