Java各种排序算法代码

在编程领域，排序算法是计算机科学的基础之一，尤其是在Java这样的高级编程语言中。排序算法用于组织数据，使得数据按照特定顺序排列，这对于数据分析、数据库管理、搜索效率优化等多个方面都至关重要。下面，我们将深入探讨Java中的一些经典排序算法及其代码实现。 1. 冒泡排序（Bubble Sort）： 冒泡排序是最基础的排序算法之一，它通过重复遍历数组，每次比较相邻元素并交换位置来完成排序。虽然效率较低，但易于理解。在Java中，冒泡排序的实现如下： ```java void bubbleSort(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; } } } } ``` 2. 插入排序（Insertion Sort）： 插入排序将未排序的元素逐个插入到已排序部分的正确位置。Java中的插入排序实现如下： ```java void insertionSort(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 = j - 1; } arr[j + 1] = key; } } ``` 3. 选择排序（Selection Sort）： 选择排序每次从未排序部分找到最小（或最大）元素，放到已排序部分的末尾。Java实现如下： ```java 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; } } // 将找到的最小元素与第一个未排序元素交换 int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } ``` 4. 快速排序（Quick Sort）： 快速排序是一种分治算法，通过选取一个“基准”元素，将数组分为两部分，左边小于基准，右边大于基准，然后递归地对这两部分进行快速排序。Java实现如下： ```java void quickSort(int[] arr, int low, int high) { if (low < high) { int pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } 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++; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; } } ``` 5. 归并排序（Merge Sort）： 归并排序也是分治策略的一种，它将数组分成两半，分别排序，然后合并两个有序部分。Java实现如下： ```java void mergeSort(int[] arr, int l, int r) { if (l < r) { int m = (l + r) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } void merge(int[] arr, int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; int[] L = new int[n1]; int[] R = new int[n2]; System.arraycopy(arr, l, L, 0, n1); System.arraycopy(arr, m + 1, R, 0, n2); int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } } ``` 6. 堆排序（Heap Sort）： 堆排序利用了二叉堆的数据结构。在Java中，可以使用内置的`PriorityQueue`类实现堆排序： ```java void heapSort(int[] arr) { PriorityQueue<Integer> pq = new PriorityQueue<>(); for (int val : arr) { pq.offer(val); } int n = arr.length; for (int i = n - 1; i >= 0; i--) { arr[i] = pq.poll(); } } ``` 以上就是Java中常见的几种排序算法，每种算法都有其适用场景和优缺点。例如，冒泡排序和插入排序适合小规模数据，快速排序和归并排序适用于大规模数据，而堆排序则在处理动态数据时表现出色。理解并掌握这些排序算法，对于提升编程技能和优化程序性能有着重要意义。在实际应用中，可以根据数据特性和需求选择合适的排序算法。