Java 排序算法详解

排序是计算机科学中的基本操作，Java 提供了多种排序算法来满足不同的需求。常见的排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序。本文将逐一介绍这些排序算法及其 Java 实现。

1. 冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法，其基本思想是通过重复遍历待排序的元素，比较相邻元素并交换位置，直到所有元素有序。时间复杂度为 O(n^2)，适合小规模数据的排序。

1.1 算法步骤

1. 从头到尾遍历数组。
2. 比较相邻的元素，如果前一个元素大于后一个元素，则交换它们。
3. 重复步骤 1 和 2，直到没有元素需要交换为止。

1.2 Java 实现

java

复制代码

public class BubbleSort { public static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { 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; } } } } }

2. 选择排序 (Selection Sort)

选择排序是一种简单的排序算法，其基本思想是每次从未排序的部分中选择最小（或最大）的元素，并将其放到已排序部分的末尾。时间复杂度为 O(n^2)，适用于小规模数据。

2.1 算法步骤

1. 从未排序的部分选择最小元素。
2. 将选出的最小元素与未排序部分的第一个元素交换。
3. 将已排序部分的范围扩展，重复步骤 1 和 2。

2.2 Java 实现

java

复制代码

public class SelectionSort { public static 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[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } } }

3. 插入排序 (Insertion Sort)

插入排序是一种简单直观的排序算法，其基本思想是将待排序的数据分为已排序和未排序两部分，每次从未排序部分取出一个元素，将其插入到已排序部分的正确位置。时间复杂度为 O(n^2)，适用于小规模数据或部分已排序的数据。

3.1 算法步骤

1. 从第二个元素开始，向前与已排序部分比较。
2. 如果当前元素小于已排序部分的元素，则将已排序部分的元素右移，直到找到合适的位置。
3. 插入当前元素，扩展已排序部分的范围。

3.2 Java 实现

java

复制代码

public class InsertionSort { public static 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--; } arr[j + 1] = key; } } }

4. 归并排序 (Merge Sort)

归并排序是一种有效的排序算法，基于分治法，其基本思想是将数组分成两个子数组，分别排序，然后将排序好的子数组合并。时间复杂度为 O(n log n)，适用于大规模数据的排序。

4.1 算法步骤

1. 将数组递归地分成两半，直到每个子数组只有一个元素。
2. 合并已排序的子数组，形成排序好的更大子数组。
3. 重复步骤 2，直到所有子数组合并成一个排序好的数组。

4.2 Java 实现

java

复制代码

public class MergeSort { public static void mergeSort(int[] arr) { if (arr.length < 2) return; int mid = arr.length / 2; int[] left = new int[mid]; int[] right = new int[arr.length - mid]; System.arraycopy(arr, 0, left, 0, mid); System.arraycopy(arr, mid, right, 0, arr.length - mid); mergeSort(left); mergeSort(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++]; } }

5. 快速排序 (Quick Sort)

快速排序是一种高效的排序算法，基于分治法，其基本思想是通过一个“基准”元素将数组分为两部分，一部分比基准小，另一部分比基准大，然后递归地排序这两部分。时间复杂度为 O(n log n)，但在最坏情况下为 O(n^2)，适用于大规模数据。

5.1 算法步骤

1. 选择一个基准元素。
2. 将数组分成两部分，一部分小于基准，一部分大于基准。
3. 递归地对这两部分进行快速排序。

5.2 Java 实现

java

复制代码

public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 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++; 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; } }

6. 堆排序 (Heap Sort)

堆排序是一种基于堆数据结构的排序算法，时间复杂度为 O(n log n)。它的基本思想是将数组视为一个堆，通过调整堆的结构，使得每次都可以将最大元素（或最小元素）取出，重复此操作直到排序完成。

6.1 算法步骤

1. 建立一个最大堆（或最小堆）。
2. 取出堆顶元素，将其与堆的最后一个元素交换，然后调整堆。
3. 重复步骤 2，直到堆为空。

6.2 Java 实现

java

复制代码

public class HeapSort { public static void heapSort(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--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; 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) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } }

总结

本文介绍了常见的 Java 排序算法，包括冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序。每种排序算法都有其特定的应用场景和优缺点，了解这些算法的基本原理和实现方法可以帮助你在实际编程中选择最合适的排序方法。希望本文的讲解能帮助你更好地掌握和应用这些排序算法。如果你有任何问题或需要进一步的详细说明，欢迎留言讨论！