阅读量:0
Java中的八大排序算法是编程中常用的排序方法，每种排序算法都有其独特的特点和应用场景。以下是对Java八大排序算法的详细介绍：
1. 冒泡排序（Bubble Sort）
- 基本思想：通过对待排序序列从前向后（或从后向前），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部（或使值较小的元素逐渐从前移向后部），就像水底的气泡一样逐渐向上冒。
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定性：稳定
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-i-1; j++) { if (arr[j] > arr[j+1]) { // 交换 arr[j+1] 和 arr[j] int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } public static void main(String[] args) { int[] arr = {64, 34, 25, 12, 22, 11, 90}; bubbleSort(arr); System.out.println("Sorted array"); for (int i = 0; i < arr.length; i++) System.out.print(arr[i] + " "); System.out.println(); } }2. 选择排序（Selection Sort）
- 基本思想：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
public class SelectionSort { public static void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i < n-1; i++) { // 找到[i, n-1]区间里的最小值的索引 int minIndex = i; for (int j = i+1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } // 交换arr[i]和arr[minIndex] int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } public static void main(String[] args) { int[] arr = {64, 25, 12, 22, 11}; selectionSort(arr); System.out.println("Sorted array"); for (int i = 0; i < arr.length; i++) System.out.print(arr[i] + " "); System.out.println(); } }3. 插入排序（Insertion Sort）
- 基本思想：将一个记录插入到已经排好序的有序表中，使得被插入数的序列同样是有序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程。
- 时间复杂度：O(n^2)（平均和最坏情况），O(n)（最好情况，即数据已经有序）
- 空间复杂度：O(1)
- 稳定性：稳定
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; /* 将arr[i]插入到arr[0...i-1]中已排序的序列中 */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } public static void main(String[] args) { int[] arr = {12, 11, 13, 5, 6}; insertionSort(arr); System.out.println("Sorted array"); for (int i = 0; i < arr.length; i++) System.out.print(arr[i] + " "); System.out.println(); } }4. 希尔排序（Shell Sort）
- 基本思想：也称缩小增量排序，是插入排序的一种更高效的改进版本。希尔排序通过将原来要排序的数列分割成几个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
- 时间复杂度：取决于增量序列的选择，最好为O(nlogn)，最坏为O(n^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
public class ShellSort { // 希尔排序 public static void sort(int[] arr) { int n = arr.length; // 初始步长 for (int gap = n / 2; gap > 0; gap /= 2) { // 从第gap个元素开始，逐个对其所在组进行直接插入排序操作 for (int i = gap; i < n; i++) { int temp = arr[i]; int j; // 对每个组进行插入排序 for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { arr[j] = arr[j - gap]; } arr[j] = temp; } } } // 测试方法 public static void main(String[] args) { int[] arr = {9, 8, 3, 7, 5, 6, 4, 1}; sort(arr); System.out.println("Sorted array: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }5. 快速排序（Quick Sort）
- 基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
- 时间复杂度：O(nlogn)（平均情况），O(n^2)（最坏情况，如数组已经有序）
- 空间复杂度：O(logn)（递归栈空间）
- 稳定性：不稳定
public class QuickSort { // 快速排序的递归方法 public static void quickSort(int[] arr, int low, int high) { if (low < high) { // partitionIndex是分区后基准值的正确位置 int partitionIndex = partition(arr, low, high); // 递归地对基准值左边的子数组进行排序 quickSort(arr, low, partitionIndex - 1); // 递归地对基准值右边的子数组进行排序 quickSort(arr, partitionIndex + 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++; // 交换arr[i]和arr[j] 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; } // 测试方法 public static void main(String[] args) { int[] arr = {10, 7, 8, 9, 1, 5}; quickSort(arr, 0, arr.length - 1); System.out.println("Sorted array: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }6. 归并排序（Merge Sort）
- 基本思想：采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)（需要额外的数组来存储合并后的序列）
- 稳定性：稳定
public class MergeSort { // 归并排序的递归方法 public static void mergeSort(int[] arr, int left, int right) { if (left < right) { // 找到中间位置 int middle = left + (right - left) / 2; // 对左半部分进行归并排序 mergeSort(arr, left, middle); // 对右半部分进行归并排序 mergeSort(arr, middle + 1, right); // 合并两个有序数组 merge(arr, left, middle, right); } } // 合并两个有序数组的方法 private static void merge(int[] arr, int left, int middle, int right) { // 创建临时数组来存储合并后的结果 int[] temp = new int[right - left + 1]; // 初始化两个指针，分别指向左右两个子数组的起始位置 int i = left; int j = middle + 1; int k = 0; // 遍历两个子数组，将较小的元素先放入临时数组 while (i <= middle && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // 如果左子数组还有剩余元素，将它们复制到临时数组 while (i <= middle) { temp[k++] = arr[i++]; } // 如果右子数组还有剩余元素，将它们复制到临时数组 while (j <= right) { temp[k++] = arr[j++]; } // 将临时数组中的元素复制回原数组 for (i = left, k = 0; i <= right; i++, k++) { arr[i] = temp[k]; } } // 测试方法 public static void main(String[] args) { int[] arr = {12, 11, 13, 5, 6, 7}; mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }7. 堆排序（Heap Sort）
- 基本思想：是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)（原地排序）
- 稳定性：不稳定
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--) { // 移动当前根到末尾 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; // 左 = 2*i + 1 int right = 2 * i + 2; // 右 = 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); } } // 测试方法 public static void main(String[] args) { int[] arr = {12, 11, 13, 5, 6, 7}; sort(arr); System.out.println("Sorted array: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }8. 计数排序（Counting Sort）
- 基本思想：不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
- 时间复杂度：O(n+k)（k是整数的范围）
- 空间复杂度：O(k)
- 稳定性：稳定
public class CountingSort { // 计数排序 public static void countingSort(int[] arr) { if (arr == null || arr.length == 0) return; int max = arr[0]; int min = arr[0]; // 找出数组中的最大值和最小值 for (int i = 1; i < arr.length; i++) { if (arr[i] > max) max = arr[i]; if (arr[i] < min) min = arr[i]; } // 计数数组的长度为max-min+1，用于记录每个元素的出现次数 int[] count = new int[max - min + 1]; // 遍历待排序数组，统计每个元素的出现次数 for (int i = 0; i < arr.length; i++) { count[arr[i] - min]++; } // 更改count[i]，使其包含实际在arr[]中的位置信息 // 这一步是为了确保排序的稳定性 for (int i = 1; i < count.length; i++) { count[i] += count[i - 1]; } // 构建输出数组 int[] output = new int[arr.length]; // 反向填充目标数组，以保持稳定性 for (int i = arr.length - 1; i >= 0; i--) { output[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } // 将排序后的数组复制到原数组 for (int i = 0; i < arr.length; i++) { arr[i] = output[i]; } } // 测试方法 public static void main(String[] args) { int[] arr = {4, 2, 2, 8, 3, 3, 1}; countingSort(arr); System.out.println("Sorted array: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }这些排序算法在Java中都有广泛的应用，根据具体的数据情况和性能要求选择合适的排序算法是非常重要的。
