java排序算法有哪些：Java排序算法有哪些？全面解析与实现指南
排序算法的分类
排序算法可以根据不同的标准进行分类,
- 内部排序：数据量较小，完全在内存中完成排序。
- 外部排序：数据量巨大，需要借助外部存储（如磁盘）进行排序。
- 稳定性：如果两个元素相等，排序后它们的相对顺序是否保持不变。
- 时间复杂度：算法执行效率的度量标准。
Java中常见的排序算法
冒泡排序（Bubble Sort）
原理：重复地遍历数组，比较相邻元素，如果顺序错误则交换它们，每一轮遍历后，最大的元素会被“冒泡”到数组的末尾。
代码示例：
public class BubbleSort {
public static void sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
} 时间复杂度：O(n²)，适用于小规模数据。
选择排序（Selection Sort）
原理：每一轮从未排序的部分中选出最小（或最大）的元素，放到已排序部分的起始位置。
代码示例：
public class SelectionSort {
public static void sort(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;
}
}
// 交换最小元素
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
} 时间复杂度：O(n²)，适用于小规模数据。
插入排序（Insertion Sort）
原理：每一轮将未排序的元素插入到已排序序列的适当位置，类似于整理扑克牌。
代码示例：
public class InsertionSort {
public static void sort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
} 时间复杂度：O(n²)，但在部分有序的情况下表现较好。
快速排序（Quick Sort）
原理：采用分治策略，选择一个基准元素，将数组分为两部分，一部分小于基准，一部分大于基准，然后递归排序。
代码示例：
public class QuickSort {
public static void sort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
sort(arr, low, pivot - 1);
sort(arr, pivot + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} 时间复杂度：平均O(n log n)，最坏O(n²)，适用于大规模数据。
归并排序（Merge Sort）
原理：将数组分成两半，分别排序后再合并，采用分治策略，时间复杂度稳定。
代码示例：
public class MergeSort {
public static void sort(int[] arr) {
if (arr.length > 1) {
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
sort(left);
sort(right);
merge(arr, left, right);
}
}
private static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) {
arr[k++] = left[i++];
}
while (j < right.length) {
arr[k++] = right[j++];
}
}
} 时间复杂度：O(n log n)，空间复杂度O(n)，适用于大规模数据。
堆排序（Heap Sort）
原理：将数组构建成堆结构，然后反复提取堆顶元素并重建堆。
代码示例：
public class HeapSort {
public static void sort(int[] arr) {
int n = arr.length;
// 构建堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 依次提取元素
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
} 时间复杂度：O(n log n)，空间复杂度O(1)，适用于大规模数据。
Java内置排序算法
Java的Arrays和Collections类提供了高效的排序方法，通常基于归并排序或快速排序的优化版本。
代码示例：
import java.util.Arrays;
import java.util.Collections;
public class BuiltInSort {
public static void main(String[] args) {
Integer[] array = {5, 2, 9, 1, 5};
Collections.sort(array);
System.out.println(Arrays.toString(array));
Integer[] array2 = {5, 2, 9, 1, 5};
Arrays.sort(array2);
System.out.println(Arrays.toString(array2));
}
} Java提供了多种排序算法,从简单的冒泡排序、选择排序到高效的快速排序、归并排序，开发者可以根据实际需求选择合适的算法，对于大多数场景，Java内置的Arrays.sort()和Collections.sort()已经足够高效和稳定。
希望本文能帮助你更好地理解和应用Java中的排序算法！你对哪种算法最感兴趣呢？欢迎在评论区留言讨论！
相关文章：
文章已关闭评论！
