Java实现排序算法：选择排序、插入排序与希尔排序

"这篇资料主要介绍了使用Java实现的几种排序算法，包括冒泡排序、选择排序、插入排序和快速排序。这些算法都是针对整数数组进行的，有助于理解排序的基本原理和实现方式。同时，还提到了Java中可能出现的NullPointerException异常情况。" 排序算法是计算机科学中的基础内容，对于任何编程语言来说都至关重要。Java作为一种广泛使用的编程语言，提供了丰富的工具和数据结构来实现各种算法。在Java中，我们可以通过自定义函数或内置的Arrays类方法来实现排序。 1. 冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法，通过不断交换相邻两个元素的位置来达到排序的目的。在Java中，我们可以通过两个嵌套的for循环来实现。代码中的if条件语句用于检查当前元素是否大于下一个元素，如果是，则交换它们的位置。冒泡排序的时间复杂度为O(n^2)，效率相对较低，但对于小规模数据排序仍然适用。 ```java int[] a = new int[]{5, 8, 3, 2, 1}; for (int i = 0; i < a.length - 1; i++) { for (int j = 0; j < a.length - 1 - i; j++) { if (a[j] > a[j + 1]) { int b = a[j]; a[j] = a[j + 1]; a[j + 1] = b; } } } ``` 2. 选择排序（Selection Sort） 选择排序的工作原理是每次从未排序的元素中找到最小（或最大）的元素，放到已排序序列的末尾。这里采用了一个min变量来记录当前未排序部分的最小值索引，然后在合适的时候交换位置。选择排序的时间复杂度同样为O(n^2)。 ```java for (int i = 0; i < a.length - 1; i++) { int min = i; for (int j = i + 1; j < a.length; j++) { if (a[min] > a[j]) { min = j; } } if (min != i) { int temp = a[i]; a[i] = a[min]; a[min] = temp; } } ``` 3. 插入排序（Insertion Sort） 插入排序是将每个元素插入到已排序的序列中正确的位置，以保持顺序。这里通过外层循环控制待排序的元素，内层循环则用于找到元素的正确插入位置，并将前面的元素后移。插入排序在处理近乎有序的数据时效率较高，时间复杂度为O(n^2)。 ```java for (int i = 1; i < a.length; i++) { for (int j = i; j > 0 && a[j] < a[j - 1]; j--) { int temp = a[j]; a[j] = a[j - 1]; a[j - 1] = temp; } } ``` 4. 快速排序（Quick Sort） 快速排序是一种高效的分治算法，它选取一个基准元素，将数组分为两部分，一部分的所有元素都比基准小，另一部分的元素都比基准大。然后对这两部分递归地进行快速排序。这里的快速排序采用了希尔排序的思路，每次缩小排序的范围。由于代码没有完整展示，因此无法提供具体实现。快速排序的平均时间复杂度为O(n log n)。 此外，文件中还提到了`NullPointerException`，这是Java中常见的运行时异常，表示尝试访问或操作一个null对象引用时抛出。为了避免这类异常，我们需要确保在使用对象之前已经正确初始化了它。 ```java public static int[] dongTaiArray(int[] a, int b) { if (a == null) { // 检查数组是否为null throw new NullPointerException("数组不能为null"); } // 其他操作... } ``` 这份资料涵盖了基础的排序算法实现，适合初学者学习和理解排序过程。在实际开发中，Java的`Arrays.sort()`方法通常会更方便、高效地完成排序任务，但理解这些基本算法有助于提升编程思维和问题解决能力。