Java常用排序算法原理与性能测试
深入理解并掌握Java常用排序算法是程序员的必备技能。本文系统梳理了包括冒泡、插入、选择、希尔、归并、快速及堆排序在内的多种算法原理与Java实现，并结合实际性能测试报告，对比不同规模数据下的执行效率，帮助你挑选最佳排序方案。
排序算法性能测试报告
为了直观展示各算法的效率差异，我们使用长度为20000的随机数组进行性能测试。每个算法重复运行20次取平均值，测试结果如下：
- bubbleSort：766 ms
- bubbleSortAdvanced：662 ms
- bubbleSortAdvanced2：647 ms
- selectSort：252 ms
- insertSort：218 ms
- insertSortAdvanced：127 ms
- insertSortAdvanced2：191 ms
- binaryTreeSort：3 ms
- shellSort：2 ms
- shellSortAdvanced：2 ms
- shellSortAdvanced2：1 ms
- mergeSort：3 ms
- quickSort：1 ms
- heapSort：2 ms
从数据可以看出，传统的冒泡排序在大数据量下表现极差，几乎是最慢的选择；而希尔排序、快速排序和堆排序展现出极高的效率。以下将详细解析各类型算法的核心逻辑与Java代码实现。
基础交换类排序：冒泡排序
冒泡排序通过重复遍历列表，比较相邻元素并交换位置，使较大的元素逐渐“沉底”。虽然其时间复杂度为 O(n²)，但因其逻辑简单，常作为入门算法。
原始冒泡排序
两层嵌套循环：外层控制扫描次数，内层控制比较范围。每轮扫描结束后，当前未排序部分的最大值会被移动到末尾。
public static void bubbleSort(int[] a) {
for(int i = 0; i < a.length; i++) {
for(int j = 0; j < a.length - i - 1; j++) {
if(a[j] > a[j+1]) {
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}带标志位优化的冒泡排序
增加一个 flag 记录本趟是否发生交换。若某趟未发生交换，说明数组已完全有序，提前终止循环，可节省一定时间。
public static void bubbleSortAdvanced(int[] a) {
int k = a.length - 1;
boolean flag = true;
while(flag) {
flag = false;
for(int i = 0; i < k; i++) {
if(a[i] > a[i+1]) {
int tmp = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
flag = true;
}
}
k--;
}
}记录最后交换位置的进阶版
进一步优化：记录最后一次发生交换的位置 flag。下一轮只需比较到该位置，因为之后的元素已经有序。
public static void bubbleSortAdvanced2(int[] a) {
int flag = a.length - 1;
int k;
while(flag > 0) {
k = flag;
flag = 0;
for(int i = 0; i < k; i++) {
if(a[i] > a[i+1]) {
int tmp = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
flag = i + 1;
}
}
}
}直接插入类排序
插入排序将数组分为“有序区”和“无序区”，不断从无序区取出元素插入到有序区的正确位置。
标准插入排序
对于无序区的每个元素，在有序区从后向前查找插入点。找到合适位置后，将该位置后的元素统一后移。
public static void insertSort(int[] a) {
for(int i = 1; i < a.length; i++) {
int j;
for(j = i - 1; j >= 0; j--) {
if(a[j] < a[i]) break;
}
if(j != (i - 1)) {
int tmp = a[i];
for(int k = i - 1; k > j; k--) {
a[k+1] = a[k];
}
a[k+1] = tmp;
}
}
}改进的插入排序（移动法）
首先判断 a[i] < a[i-1]，若成立则在有序区从后向前查找大于 a[i] 的元素并逐个后移，空出空间后填入。
public static void insertSortAdvanced(int[] a) {
for(int i = 1; i < a.length; i++) {
if(a[i] < a[i-1]) {
int tmp = a[i];
int j;
for(j = i - 1; j >= 0 && a[j] > tmp; j--) {
a[j+1] = a[j];
}
a[j+1] = tmp;
}
}
}采用冒泡交换思想的插入排序
不整体移动元素，而是让待插入元素像气泡一样，通过与前一个元素的不断交换，逐步向前移动到正确位置。
public static void insertSortAdvanced2(int[] a) {
for(int i = 1; i < a.length; i++) {
for(int j = i - 1; j >= 0 && a[j] > a[j+1]; j--) {
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}分治策略：快排、归并与二叉树
这三类算法均采用了递归或分治思想，通常在处理大规模数据时具有更好的性能表现。
快速排序 (QuickSort)
核心逻辑是选择一个基准值，将比它小的放左边，大的放右边，然后递归处理左右子数组。这里的关键在于指针 low0 和 high0 的移动以及 forward 方向的切换。
public static void quickSort(int[] a, int low, int high) {
if(low >= high) return;
int low0 = low;
int high0 = high;
boolean forward = false;
while(low0 != high0) {
if(a[low0] > a[high0]) {
int tmp = a[low0];
a[low0] = a[high0];
a[high0] = tmp;
forward = !forward;
}
if(forward) low0++;
else high0--;
}
low0--; high0++;
quickSort(a, low, low0);
quickSort(a, high0, high);
}
public static void quickSort(int[] a) {
quickSort(a, 0, a.length - 1);
}归并排序 (MergeSort)
将数组二分，直到子数组长度为1，再两两合并为有序数组。由于需要额外空间存储合并结果，此处设计返回新数组。
public static int[] merge(int[] a, int[] b) {
int result[] = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while(i < a.length && j < b.length) {
if(a[i] < b[j]) result[k++] = a[i++];
else result[k++] = b[j++];
}
while(i < a.length) result[k++] = a[i++];
while(j < b.length) result[k++] = b[j++];
return result;
}
public static int[] mergeSort(int[] a) {
if(a.length == 1) return a;
int mid = a.length / 2;
int[] leftPart = Arrays.copyOfRange(a, 0, mid);
int[] rightPart = Arrays.copyOfRange(a, mid, a.length);
return merge(mergeSort(leftPart), mergeSort(rightPart));
}二叉树排序 (BinaryTreeSort)
利用二叉搜索树的性质（左节点小于父节点，右节点大于父节点）。构建完成后进行中序遍历即可得到有序序列。
public static void binaryTreeSort(int[] a) {
class BinaryNode {
int value;
BinaryNode left;
BinaryNode right;
public BinaryNode(int value) { this.value = value; }
public void add(int val) {
if(val > this.value) {
if(this.right != null) this.right.add(val);
else this.right = new BinaryNode(val);
} else {
if(this.left != null) this.left.add(val);
else this.left = new BinaryNode(val);
}
}
public void iterate() {
if(left != null) left.iterate();
System.out.print(value + " "); // 实际使用中可收集至List
if(right != null) right.iterate();
}
}
BinaryNode root = new BinaryNode(a[0]);
for(int i = 1; i < a.length; i++) root.add(a[i]);
root.iterate();
}高效改进型：希尔排序
希尔排序是插入排序的高效变种，通过缩小增量 gap 进行分组插入排序，使得全局逐渐趋于有序。
基础希尔排序
分别对每一组子序列执行插入排序。步长依次减半，直到步长为1时进行最后一次全序列插入排序。
public static void shellSort(int[] a) {
for(int gap = a.length / 2; gap > 0; gap /= 2) {
for(int i = 0; i < gap; i++) {
for(int j = i + gap; j < a.length; j += gap) {
if(a[j] < a[j - gap]) {
int tmp = a[j], k = j - gap;
while(k >= 0 && a[k] > tmp) {
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = tmp;
}
}
}
}
}更简洁的希尔排序实现
不再按索引分组循环，而是将步长逻辑融入单循环，代码更为紧凑。
public static void shellSortAdvanced(int[] a) {
for(int gap = a.length / 2; gap > 0; gap /= 2) {
for(int j = gap; j < a.length; j++) {
if(a[j] < a[j - gap]) {
int tmp = a[j], k = j - gap;
while(k >= 0 && a[k] > tmp) {
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = tmp;
}
}
}
}基于堆结构的堆排序
利用完全二叉树结构（大顶堆），将数组先调整为最大堆，然后反复将堆顶最大值移至末尾，并重新调整剩余堆结构。
public static void heapSort(int[] a) {
// 构建初始大顶堆
for(int i = (a.length - 2) / 2; i >= 0; i--) {
maxHeapAdjust(a, i, a.length);
}
// 依次将堆顶元素与末尾元素交换
for(int i = a.length - 1; i > 0; i--) {
int tmp = a[i]; a[i] = a[0]; a[0] = tmp;
maxHeapAdjust(a, 0, i);
}
}
private static void maxHeapAdjust(int[] a, int i, int len) {
int tmp = a[i];
int j = 2 * i + 1; // 左孩子
while(j < len) {
if(j + 1 < len && a[j+1] > a[j]) j++; // 指向更大的孩子
if(a[j] < tmp) break;
a[i] = a[j];
i = j;
j = 2 * i + 1;
}
a[i] = tmp;
}以上就是Java常用排序算法及性能测试的详细内容，更多关于Java面试资料与算法实践的文章请关注本站其它相关文章！
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
