JAVA排序算法整理：冒泡、选择、插入排序

"JAVA经典算法收集整理" 这篇文章主要介绍了三种经典的Java排序算法：冒泡排序、选择排序和插入排序。这些算法是计算机科学基础中的重要组成部分，尤其在数据结构和算法的学习中占据着核心地位。 1. **冒泡排序（Bubble Sort）** 冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经过交换慢慢“浮”到数列的顶端，就像水中的气泡最终会上浮到水面一样。 ```java void bubbleSort(int[] numlist) { int temp; for (int j = 1; j < numlist.length; j++) { for (int i = 0; i < numlist.length - j; i++) { if (numlist[i] > numlist[i + 1]) { temp = numlist[i + 1]; numlist[i + 1] = numlist[i]; numlist[i] = temp; } } } } ``` 2. **选择排序（Selection Sort）** 选择排序的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。 ```java void selectionSort(int[] numlist) { int temp; for (int i = 0; i < numlist.length - 1; i++) { for (int j = i + 1; j < numlist.length; j++) { if (numlist[i] > numlist[j]) { temp = numlist[j]; numlist[j] = numlist[i]; numlist[i] = temp; } } } } ``` 3. **插入排序（Insertion Sort）** 插入排序的工作方式是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 ```java void insertSort(int[] numlist) { int temp, in, out; for (int i = 1; i < numlist.length; i++) { temp = numlist[i]; in = i; while (in > 0 && numlist[in - 1] > temp) { numlist[in] = numlist[in - 1]; in--; } numlist[in] = temp; } } ``` 这三种排序算法各有优缺点。冒泡排序的时间复杂度为O(n²)，适用于小规模或基本有序的数组；选择排序的时间复杂度同样为O(n²)，但其交换次数较少，适合对稳定性要求不高的场景；插入排序在最好的情况下（已排序数组）时间复杂度为O(n)，但在最坏的情况下（逆序数组）也是O(n²)，所以它的性能介于冒泡排序和选择排序之间。了解和掌握这些基础排序算法有助于理解更高级的排序算法，如快速排序、归并排序等，并能为解决实际问题提供基础。