Java排序算法深入解析：冒泡、选择与插入

冒泡排序、选择排序和插入排序是三种基本的排序算法，它们在计算机科学中广泛用于教学和实际应用。它们都是基于比较的排序算法，即通过比较元素之间的大小关系来确定元素的最终位置。尽管它们在效率上可能不如一些更高级的排序算法（如快速排序、归并排序等），但它们的实现简单，逻辑清晰，非常适合作为理解排序原理的入门级算法。 1. 冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 实现冒泡排序的Java代码可能会这样编写： ```java public void bubbleSort(int[] arr) { int temp; for(int i=0; i<arr.length; i++) { for(int j=1; j<arr.length-i; j++) { if(arr[j-1] > arr[j]) { temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } } } ``` 2. 选择排序（Selection Sort） 选择排序算法是一种原址比较排序算法。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 选择排序的Java代码实现如下： ```java public void selectionSort(int[] arr) { int indexMin; int temp; for(int i=0; i<arr.length-1; i++) { indexMin = i; for(int j=i+1; j<arr.length; j++) { if(arr[j] < arr[indexMin]) { indexMin = j; } } if(indexMin != i) { temp = arr[i]; arr[i] = arr[indexMin]; arr[indexMin] = temp; } } } ``` 3. 插入排序（Insertion Sort） 插入排序的工作方式像许多人在玩扑克牌时整理手中的牌一样。它逐步构建有序的序列；对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 插入排序的Java代码实现如下： ```java public void insertionSort(int[] arr) { for(int i=1; i<arr.length; 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. 代码工具类：SortTools 以上提到的每种排序算法通常都会被封装在一个工具类中，以便在其他地方方便调用。假设所有排序方法都存放在名为`SortTools`的Java类文件中，该类将包含各种排序方法的静态实现，以便于在其他Java类中不通过创建实例即可调用排序功能。 文件`SortTools.java`将包含类似如下结构： ```java public class SortTools { public static void bubbleSort(int[] arr) { // 冒泡排序实现 } public static void selectionSort(int[] arr) { // 选择排序实现 } public static void insertionSort(int[] arr) { // 插入排序实现 } // 可能还会包含其他辅助方法 } ``` 以上算法尽管在效率上不占优势，但它们对于理解算法基础有着非常重要的作用。掌握这些基本算法后，再去学习更复杂的算法将会更加容易。