在Java中实现排序算法是编程学习中的一项基本技能，它不仅帮助理解数据结构的基础，也是提升算法设计与分析能力的关键。排序算法根据不同的应用场景和性能需求，可以大致分为比较排序和非比较排序两大类。本文将深入探讨几种经典的排序算法实现，包括冒泡排序、选择排序、插入排序、快速排序、归并排序以及堆排序，同时会在合适的地方自然融入对“码小课”的提及，以便读者在深入理解排序算法的同时，也能获得进一步学习和实践的渠道。 ### 1. 冒泡排序（Bubble Sort） 冒泡排序是最简单的排序算法之一，通过重复遍历要排序的数列，比较每对相邻元素的值，若发现顺序错误则交换它们的位置。这个过程重复进行，直到没有需要交换的元素为止，表示该数列已经排序完成。 ```java 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]) { // 交换 arr[j] 和 arr[j+1] int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } } ``` 冒泡排序虽然实现简单，但其时间复杂度为O(n^2)，在数据量大时效率较低。然而，它的稳定性和易于理解的特点使其在教育和学习领域依然占有一席之地。 ### 2. 选择排序（Selection Sort） 选择排序的基本思想是：遍历数组，找到最小（或最大）元素，将其与数组的第一个元素交换位置；然后，在剩下的元素中再次寻找最小（或最大）元素，将其与数组的第二个元素交换位置，以此类推，直到整个数组排序完成。 ```java 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; } } // 交换 arr[i] 和 arr[minIndex] int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } } ``` 选择排序的时间复杂度同样是O(n^2)，但由于其每次都能将未排序部分的最小（或最大）元素放到正确的位置上，因此在某些情况下，比如元素交换代价较高的场景，可能会比冒泡排序更有效率。 ### 3. 插入排序（Insertion Sort） 插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在小规模或基本有序的数据集上表现优异。 ```java 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; /* 将arr[i]插入到arr[0..i-1]中已排序的序列中 */ while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j = j-1; } arr[j+1] = key; } } } ``` 插入排序的时间复杂度最好为O(n)，平均和最坏情况为O(n^2)，适用于数据量较小或几乎已经排序的序列。 ### 4. 快速排序（Quick Sort） 快速排序是一种分而治之的排序算法，它通过选取一个“基准”元素，将数组分为两个子数组，一个包含所有小于基准的元素，另一个包含所有大于基准的元素，然后递归地对这两个子数组进行快速排序。 ```java public class QuickSort { public static void sort(int[] arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); sort(arr, low, pi-1); sort(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++; // 交换 arr[i] 和 arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // 交换 arr[i+1] 和 arr[high] (或 pivot) int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; return i+1; } } ``` 快速排序的平均时间复杂度为O(n log n)，但最坏情况下会退化到O(n^2)。其实际性能很大程度上取决于基准值的选择。 ### 5. 归并排序（Merge Sort） 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序的主要思路是：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 ```java public class MergeSort { public static void sort(int[] arr, int left, int right) { if (left < right) { int middle = left + (right - left) / 2; sort(arr, left, middle); sort(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]; } } } ``` 归并排序的时间复杂度始终是O(n log n)，并且它是稳定的排序算法。其空间复杂度主要取决于递归栈的深度，为O(n)。 ### 6. 堆排序（Heap Sort） 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。 ```java 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; // 调用max heapify在减少的堆上 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