学习Java中的排序算法不仅有助于理解数据结构与算法的基本原理，还能提升解决实际问题的能力。排序算法是计算机科学中的重要组成部分，它们在数据处理、数据库管理、机器学习等多个领域都有着广泛的应用。通过学习不同的排序算法，可以加深对算法复杂度、稳定性等概念的理解，并能够根据具体问题选择或设计最合适的排序方法。
下面介绍几种JAVA中简单的算法排序
1.冒泡排序
冒泡排序思路易于理解，是学习排序算法时的一个很好的入门点。这种排序算法的基本思想是每次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。这样一轮比较下来，最大的元素就会被交换到数组的末尾。然后再进行下一轮比较，直到整个数组有序。
public class Main { public static void main(String[] args) { int [] arr={-3,3,55,12,32,65,78}; //冒泡排序 bubbleSort(arr); for (int nNum:arr){ System.out.println(nNum); } } public static void bubbleSort(int []arr){ //临时变量，用于交换元素 int temp; //标志位，用来判断有没有交换 boolean flag; //外层循环，限制循环次数 for (int i = 0;i < arr.length - 1;i++){ flag = false; //内层控制元素相邻变换 for(int j = 0;j< arr.length -1 -i;j++){ if(arr[j] > arr[j + 1]){ temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; flag = true; } } if (!flag){ break; } } } }
上述代码中，调用bubbleSort方法，首先定义了一个临时变量temp和一个标志位flag。外层循环控制排序的轮数，每轮比较相邻的元素，如果前一个元素大于后一个元素，则交换它们的位置。一轮比较下来，最大的元素就会被交换到数组的末尾。内层循环控制每轮比较的次数，每次比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。如果一轮比较中没有发生任何交换，说明数组已经有序，此时可以提前结束排序。
2.选择排序
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O (n²) 的时间复杂度。 所以用到它的时候，数据规模越小越好。 唯一的好处可能就是不占用额外的内存空间了吧。
选择排序的基本思想是：首先在未排序序列中找到最小（或最大）元素，将其放到排序序列的起始位置，然后再从剩余的未排序元素中继续寻找最小（或最大）元素，并将其放到已排序序列的末尾。这一过程重复进行，直到所有元素均排序完毕。
public class Main { public static void main(String[] args) { int [] arr={50,89,0,-22,67}; //选择排序 selectionSort(arr); for (int nNum:arr){ System.out.println(nNum); } } public static void selectionSort(int []arr){ for (int i = 0;i< arr.length -1;i++) { int minIndex = i; for (int j = i + 1;j < arr.length;j++){ if (arr[j] < arr[minIndex]){ minIndex = j; } } if (minIndex != i){ int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } } } }
上述代码中调用selectionSort方法，定义了变量minIndex，用于记录最小元素的下标。外层循环控制排序的轮数，每轮比较相邻的元素，找到最小元素的下标minIndex。
内层循环从i+1开始遍历未排序序列，找到最小元素的下标minIndex。如果minIndex不等于i，说明找到了更小的元素，需要交换位置。
3.快速排序
快速排序是一种高效的排序算法，其基本思想是采用分治法的思想，将待排序的序列分为两个子序列，其中一个子序列的所有元素都比另一个子序列的元素小，然后对这两个子序列分别进行排序，最终得到有序序列。
public class Main { public static void main(String[] args) { int [] arr={22,11,-12,100,89}; //快速排序 quickSort(arr,0,arr.length-1); for (int nNum:arr){ System.out.println(nNum); } } public static void quickSort(int [] arr,int low,int high){ if (low < high){ int prvot =partition(arr,low,high); quickSort(arr,low,prvot - 1); quickSort(arr,prvot + 1,high); } } public static int partition(int [] arr,int low,int high){ int prvot = arr[low]; while (low < high){ while (low < high && arr[high] >= prvot){ high--; } arr[low] = arr[high]; while (low < high && arr[high] <= prvot){ low++; } arr[high] = arr[low]; arr[low] = prvot; } return low; } }
上述代码调用两个方法，在partition方法中，首先选取一个基准元素pivot，通常选择第一个元素或者最后一个元素。然后从左到右遍历序列，将小于pivot的元素放到左边，大于pivot的元素放到右边。最后返回基准元素的下标。在quickSort方法中，首先判断low是否小于high，如果是，则调用partition方法获取基准元素的下标prvot。然后对左右两个子序列分别递归调用quickSort方法。
4.插入排序
插入排序是一种简单直观的排序算法，其基本思想是将一个无序序列分为已排序和未排序两部分，每次从未排序部分取出一个元素，将其插入到已排序部分的正确位置上。
public class Main { public static void main(String[] args) { int [] arr={-6,12,89,22,-8}; //插入排序 insertionSort(arr); for (int nNum:arr){ System.out.println(nNum); } } public static 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; } } }
5.希尔排序
希尔排序是一种改进的插入排序算法，它的基本思想是将待排序的数组按照一定的间隔进行分组，对每组使用插入排序算法进行排序，然后缩小间隔，再对分组进行排序，直到间隔为1为止。
逐渐减小间隔大小的方法有助于提高排序过程的效率，可以减少比较和交换的次数。这是希尔排序算法的一个关键特点。
import java.util.Arrays; public static void Main(String[] args) { int[] arr = {5, 2, 8, 3, 1, 6}; int[] expectedArr = {1, 2, 3, 5, 6, 8}; shellSort(arr); System.out.println("arr = " + Arrays.toString(arr)); Assertions.assertArrayEquals(expectedArr, arr); } public static void shellSort(int[] arr) { int n = arr.length; // 初始化间隔（gap）的值，它决定了每次迭代中子数组的大小 // 从数组长度的一半开始作为初始间隔值，gap就是分割的子数组数量 for (int gap = n / 2; gap > 0; gap /= 2) { // 循环从间隔值开始，遍历数组直到数组的末尾；代表循环所有的子数组 for (int i = gap; i < n; i++) { int temp = arr[i]; int j = i; // 将当前元素 arr[j] 的值替换为前一个元素 arr[j - gap] 的值。 // 通过这个操作，将较大的元素向后移动，为当前元素腾出位置 while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } }
代码中的shellSort方法接收一个整数数组作为参数，对其进行希尔排序。在main方法中，定义了一个待排序的数组arr和一个预期排序后的数组expectedArr，然后调用shellSort方法对arr进行排序，并使用Assertions.assertArrayEquals方法检查排序后的结果是否与预期相符。
6.计数排序
计数排序是一种非基于比较的排序算法，它适用于当待排序的元素是确定的、可数的，并且元素的范围事先已知的情况下。计数排序的基本思想是对每一个输入元素确定小于它的元素个数，这样就可以直接把输入元素放到它在输出数组中的位置上。
计数排序是一种简单而有效的排序算法，特别适用于整数序列，其性能优于比较排序算法，但在应用上有一定的局限性。
import java.util.Arrays; public static void Main(String[] args) { int[] arr = {5, 2, 6, 8, 3, 1, 6, 5, 12}; int[] expectedArr = {1, 2, 3, 5, 5, 6, 6, 8, 12}; countingSort(arr); System.out.println("arr = " + Arrays.toString(arr)); Assertions.assertArrayEquals(expectedArr, arr); } public static void countingSort(int[] arr) { int n = arr.length; // 取出数组中最大值 int max = getMax(arr); int[] count = new int[max + 1]; // 统计每个元素出现的次数 for (int i = 0; i < n; i++) { count[arr[i]]++; } // 计算每个元素在有序序列中的位置 for (int i = 1; i <= max; i++) { // 因为count包含了每个数据出现的次数，所以从小到大， // 逐个往前加得到就是原数组中每个元素在有序序列中应有的位置 count[i] += count[i - 1]; } // 输出有序序列 int[] sortedArr = new int[n]; for (int i = n - 1; i >= 0; i--) { int item = arr[i];//元素 int itemPos = count[item];// 元素在有序数组中的位置 sortedArr[itemPos - 1] = item; // 将元素填入有序数组 count[item]--; } // 将有序序列复制回原数组 System.arraycopy(sortedArr, 0, arr, 0, n); } private static int getMax(int[] arr) { int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } return max; }
上述代码中的countingSort方法接受一个整数数组作为参数，并对其进行排序。首先，它找到数组中的最大值，然后创建一个长度为最大值加1的计数数组。接下来，它遍历输入数组，统计每个元素出现的次数，并将结果存储在计数数组中。然后，它计算每个元素在有序序列中的位置，并将结果存储回计数数组。最后，它使用计数数组中的位置信息将元素填入一个新的有序数组，并将有序数组复制回原数组。
getMax方法用于获取数组中的最大值。它遍历数组，找到最大的元素并返回。
