排序模板

快速排序

public class QuickSort {
  public static void sort(int[] q, int l, int r) {
    if (l >= r) return;
    
    int i = l - 1, j = r + 1, k = q[l + r >> 1];
    while (i < j) {
      do i++; while (q[i] < k);
      do j--; while (q[j] > k);
      if (i < j) Tools.swap(q, i, j);
    }
    sort(q, l, j); sort(q, j + 1, r);
  }
}

归并排序

public class MergeSort {
  final static int N = 10010;
  
  public static void sort(int[] q, int l, int r) {
    if (l >= r) return;
    
    int mid = l + r >> 1;
    sort(q, l, mid); sort(q, mid + 1, r);
    
    int[]	tmp = new int[N];
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
      if (q[i] < q[j]) tmp[k++] = q[i++];
      else tmp[k++] = q[j++];
    }
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    for (i = l, j = 0; i < r;) q[i++] = tmp[j++];
  }
}

搜索模板

二分搜索

public class BinarySearch {
  public static void search(int[] q, int k) {
    int i = 0, j = q.length - 1;
    
    while (i < j) {
      int mid = i + j >> 1;
      if (q[mid] >= k) j = mid;
      else i = mid + 1;
    }
    System.out.print(i + " ");
    
    i = 0; j = q.length - 1;
    while (i < j) {
    	int mid = i + j + 1 >> 1;
      if (q[mid] <= k) i = mid;
      else j = mid - 1;
    }
    System.out.println(i);
  }
}

二分模板的各种情况说明

• 当数组中存在查找的值时
  • >= , <= 分别取得该元素 $I_$ ，$I_$ 的坐标，即取得该元素
  • > , < 分别取得该元素 $I_ + 1$ 与 $I_ + 1$ 的坐标，即跳过该元素
• 当数组中不存在该元素时
  • >= 与 > 含义无差别
  • <= 与 < 含义无差别

二分开方

public class BinarySearch {
  public static double prescribe(double x) {
    double i = 0, j = x;
    
    while (j - i > 1e-5) {
      double mid = (i + j) / 2;
      if (mid * mid > x) i = mid;
      else j = mid;
    }
    
    return i;
  }
}

• 参考来源
  • ACWing - 算法基础课