快速排序
快速排序是一种利用分治的思想对集合进行排序的一种算法，选一个基准值 pivot，把数组切成两段：≤ pivot 的在左，≥ pivot 的在右，再递归排左右子区间。
快排的分治分三步：
- 选取基准值 x（pivot）。 一般取区间中某个位置的值（示例代码取
arr[l]）。 - 划分（partition）。 用两个指针 i、j 分别从两端向中间走：i 向右跳过所有小于 x 的元素，j 向左跳过所有大于 x 的元素；当 i 停在一个 ≥ x 的元素上、j 停在一个 ≤ x 的元素上时，交换二者。一趟走完后，左边全是 ≤ x 的元素，右边全是 ≥ x 的元素。
- 递归处理左右两个子区间，直到区间长度为 1 或 0（
l >= r时直接返回，因为一个元素天然有序）。
模板中的几个细节：
- 指针初始化为
i = l - 1、j = r + 1，并采用do...while先移动指针、再判断——保证两个指针每轮至少走一步，不会原地死循环。 - 基准值取
arr[l]时，递归划分必须用 j（即[l, j]与[j+1, r]）；若基准取arr[r]，则递归要用 i。基准取端点与划分边界要”错开”，否则在元素全相等之类的极端数组上会出现无限递归。 - 划分结束时左右区间的大小一定都比原区间小，因此递归一定终止。
复杂度： 平均 O(n log n)（每层划分 O(n)，共约 log n 层）；最坏情况（每次基准都取到最大/最小值，例如对已有序数组取端点）退化为 O(n²)。快排是不稳定排序——相等的元素可能因交换而改变相对顺序。
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
//此处可以使用BufferedReader速度比Scanner快 Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr = new int[100]; for (int i = 0; i < n; i++) { arr[i] = scanner.nextInt(); } quickSort(arr,0,n-1); for (int i = 0; i < n; i++) { System.out.println(arr[i]); } } public static void quickSort(int[] arr,int l,int r){ //判断数组长度，为1或者为0直接返回 if(l >= r){ return; } //选取基准值，基准值在选取时要注意处理边界，在选择j的时候边界不能选arr[r]，同理在选择i时边界是不能选取arr[l] int x = arr[l]; //因为是先移动指针再判断所以将左指针左移1位，右指针右移一位 int i = l - 1 ; int j = r + 1; //将数组分为两边，一边小于边界值x，一边大于边界值x while (i < j){ do i++;while (arr[i] < x); do j--;while (arr[j] > x); //若i所指数大于边界值x并且j所指数小于边界值x则进行交换 if(i < j){ int temp; temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } //递归 quickSort(arr,l,j); quickSort(arr,j+1,r);
}}归并排序
归并排序的核心在于**“分而治之” (Divide and Conquer)**。它的逻辑非常稳健：与其面对一个乱七八糟的长数组，不如不断把它切半，直到每个部分只剩下一个数字（一个数字自然是有序的），然后再一层层合并回来。
具体分三步：
- 分（divide）： 取中点
p = (l + r) >> 1，把区间[l, r]分成[l, p]和[p+1, r]两半；- 治（conquer）： 递归地对左右两半分别排序；
- 合（merge）： 此时两个子区间都已经有序，用双指针 i、j 分别指向两半开头，每次取
arr[i]与arr[j]中较小的一个放进临时数组 temp，直到其中一半取完，再把另一半剩余元素全部接上，最后把 temp 写回原数组对应位置。归并与快排都是分治，但归并的重头戏在”合并”（先递归、后处理），快排的重头戏在”划分”（先处理、后递归）。
性质： 时间复杂度稳定为 O(n log n)（与输入数据的分布无关），代价是需要 O(n) 的临时数组空间；归并是稳定排序——合并时写成
arr[i] <= arr[j]优先取左边，相等元素的相对顺序就保持不变。另外，只要在合并过程中统计”每取一个右边元素时，左边还剩多少元素”，就可以顺便求出逆序对的数量，这是归并排序的经典应用。
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Scanner;
public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[100]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } mergeSort(arr,0,n-1); for (int i = 0; i < n; i++) { System.out.println(arr[i]); }
} public static void mergeSort(int[] arr ,int l ,int r){ if(l >= r){ return; } int p = (l+r) >> 1; mergeSort(arr,l,p); mergeSort(arr,p+1,r); int k = 0; int i = l; int j = p+1; int[] temp = new int[100]; while (i<=p && j<=r){ if(arr[i] <= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } while (i<=p) temp[k++] = arr[i++]; while (j<=r) temp[k++] = arr[j++]; for (i = l,j = 0; i<=r ; i++,j++) { arr[i] = temp[j]; } }}冒泡排序
就像水底的气泡一样，大的元素通过不断地相邻比较和交换，每一轮都会“浮”到数组的末尾。
具体过程：第 1 轮从头到尾把相邻元素两两比较，大的向后”冒”，结束时最大元素到达最后一个位置；第 2 轮对前 n-1 个元素重复，使第二大元素到达倒数第二个位置……共进行 n-1 轮后数组整体有序。每轮内层只需比较到
n - 1 - i，因为末尾 i 个元素已经就位，无需再比。代码中的
swapped标记是一种优化：如果某一轮从头到尾没有发生任何交换，说明数组已经有序，直接提前退出——最好情况（数组本来就接近有序）下只需一轮扫描 O(n)。复杂度： 平均和最坏均为 O(n²)（比较次数约 n(n-1)/2）；是稳定排序。整体效率偏低，适合小数据量或作为教学演示。
public void bubbleSort(int[] arr) { int n = arr.length; // 外层循环控制排序轮数 for (int i = 0; i < n - 1; i++) { boolean swapped = false; // 优化：如果某一轮没有交换，说明已经有序 // 内层循环进行相邻比较 for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { // 交换 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swapped = true; } } if (!swapped) break; }}选择排序
每一轮都从“待排序”区域中直接选出一个最小（或最大）的元素，存放到序列的起始位置。
具体过程：第 1 轮在
[0, n-1]中找出最小元素的下标，与位置 0 交换；第 2 轮在[1, n-1]中找最小元素，与位置 1 交换……进行 n-1 轮后，前面 n-1 个位置就位，最后一个位置自然也就位了。与冒泡排序的区别：冒泡靠相邻交换”搬运”元素，每次比较都可能交换；选择排序每轮只记录最小值的下标，一轮结束时才交换一次，因此交换次数最多 n-1 次，远少于冒泡。
复杂度： 比较次数固定约 n(n-1)/2，时间复杂度 O(n²)；交换可能把元素跳过中间位置，因此它是不稳定排序。与冒泡一样属于简单但效率较低的入门排序。
public void selectionSort(int[] arr) { int n = arr.length; // 移动未排序序列的边界 for (int i = 0; i < n - 1; i++) { int minIndex = i; // 假设当前第一个是最小的
// 在剩余序列中寻找真正的最小值索引 for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } }
// 将找到的最小值与当前边界位置交换 if (minIndex != i) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }}二分
整数二分
二分的本质其实是不断缩小区间并且所找答案也包括在区间之内，当区间足够小的时候答案自然水落石出。
二分的使用前提与本质： 二分不只用于单调序列。更本质的条件是”两段性”——数组（或答案区间）可以被分成两段，前半段满足某种性质、后半段不满足（或反之），那么就可以用二分找出这两段的分界点。单调性是最常见的”两段性”情形，但二分能做的题不一定要求严格单调。
两个整数二分模板：
- 模板一（找左边界，即第一个 ≥ x 的位置）：
mid = (l + r) >> 1（下取整）；若arr[mid] >= x，说明答案在 mid 左边（含 mid），执行r = mid；否则执行l = mid + 1。区间只剩两个元素时 mid 落在 l 上，l = mid + 1保证区间一定缩小，不会死循环。 - 模板二（找右边界，即最后一个 ≤ x 的位置）：
mid = (l + r + 1) >> 1（上取整）；若arr[mid] <= x，说明答案在 mid 右边（含 mid），执行l = mid；否则执行r = mid - 1。区间只剩两个元素时 mid 落在 r 上，r = mid - 1保证区间一定缩小。
记忆口诀： 只要更新写成 l = mid，mid 就必须 +1（上取整）；更新写成 r = mid，mid 就不加 1（下取整）。每次把区间砍掉约一半，所以循环是 O(log n)。
关于”无解”： 二分模板本身永远有解——总能找到两段的分界点，但分界点未必是题目想要的答案。例如查找一个不存在的数 x 时，模板一返回的是”第一个 ≥ x 的位置”，该位置的值可能不等于 x，所以退出循环后需要再检查一次 arr[l] == x 之类的条件，才能判断题目意义上的无解（对应代码里输出 -1 -1 的分支）。
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Scanner;
public class Main {
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } for (int i = 0; i < m; i++) { int x = sc.nextInt();//需要进行查找的数 int l = 0 ; int r = n -1 ; //二分查找最开始出现的位置，边界为arr[mid] >= x while (l < r){ int mid = (l + r) >> 1; if(arr[mid] >= x) r = mid; else l = mid + 1; } //判断该数是否存在，在查找完最开始的位置之后，如果所查的数不存在，那么有arr[l] != x //此处无解指的是题目无解的一种情况，二分是一定有解的 if(arr[l] != x) System.out.println("-1 -1"); else{ System.out.println(l); l = 0 ; r = n -1 ; //二分查找最后出现的位置 while (l < r){ int mid = (l + r + 1) >> 1; if(arr[mid] <= x) l = mid; else r = mid -1; } System.out.println(l); } } }
}浮点数二分
浮点数二分与整数二分的思路完全相同，区别在于实数除法没有”整除边界”问题：mid = (l + r) / 2 直接除，更新时一律 l = mid 或 r = mid（不需要 ±1）。
精度控制： 浮点数不存在”l 与 r 相邻”的概念，所以循环条件改为 while (r - l > eps)——当区间长度小于一个足够小的精度阈值 eps 时结束，此时 l 与 r 的差距已经可以忽略，取 l 或 r 都可作为答案。经验做法是 eps 比题目要求的精度再多两位小数：例如要求保留 6 位小数，就取 eps = 1e-8，避免舍入误差影响最后一位。循环次数约为 O(log(区间长度 / eps))，非常快。
边界注意： 求 sqrt(x) 时若 x < 1（如 x = 0.04），其平方根 0.2 大于 x，初始区间 [0, x] 就不正确，上界应取 max(1, x)；若 x 可能为负数，则需要在二分之前单独特判。
求根号x的值
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); double x = sc.nextInt(); double l = 0; double r = x; while (r - l > 1e-8){ double mid = (l + r) / 2; if(mid * mid >= x) r = mid; else l = mid; } System.out.println(l); }
}import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Scanner;
public class Main {
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); //有序数组 int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } for (int i = 0; i < m; i++) { //需要进行查找的数 int x = sc.nextInt(); int l = 0 ; int r = n -1 ; //二分查找 while (l < r){ int mid = (l + r) >> 1; if(arr[mid] >= x) r = mid; else l = mid + 1; } System.out.println(arr[l]); } }
}如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时