Java实现数组排序：冒泡、选择、插入与希尔排序

"该代码示例展示了如何在Java中实现四种基本排序算法：冒泡排序、选择排序、插入排序和希尔排序。这些算法可用于对一维或二维数组进行排序。作者为YangL，时间戳为2008.11.09。" **冒泡排序** 冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 ```java public static void maoPao(int[] x) { for (int i = 0; i < x.length; i++) { for (int j = i + 1; j < x.length; j++) { if (x[i] > x[j]) { int temp = x[i]; x[i] = x[j]; x[j] = temp; } } } // 输出排序后的数组 for (int i : x) { System.out.print(i + ""); } } ``` **选择排序** 选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。 ```java public static void xuanZe(int[] x) { for (int i = 0; i < x.length; i++) { int lowerIndex = i; // 找出最小的一个索引 for (int j = i + 1; j < x.length; j++) { if (x[j] < x[lowerIndex]) { lowerIndex = j; } } // 交换 int temp = x[i]; x[i] = x[lowerIndex]; x[lowerIndex] = temp; } // 输出排序后的数组 for (int i : x) { System.out.print(i + ""); } } ``` **插入排序** 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需要用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。 ```java public static void chaRu(int[] x) { for (int i = 1; i < x.length; i++) { // int key = x[i]; int j = i - 1; // 将比key大的元素依次向后移动 while (j >= 0 && x[j] > key) { x[j + 1] = x[j]; j--; } x[j + 1] = key; } // 输出排序后的数组 for (int i : x) { System.out.print(i + ""); } } ``` **希尔排序** 希尔排序是插入排序的一种更高效的改进版本。它通过将原始数组分割成若干个子序列（增量序列），然后对每个子序列使用插入排序。增量序列的选择对算法性能有很大影响，通常选择一个逐渐减小的序列。 ```java public static void shell(int[] x) { int gap = x.length / 2; while (gap > 0) { for (int i = gap; i < x.length; i++) { int j = i; int temp = x[i]; // 对每个子序列进行插入排序 while (j >= gap && x[j - gap] > temp) { x[j] = x[j - gap]; j -= gap; } x[j] = temp; } // 缩小增量 gap /= 2; } // 输出排序后的数组 for (int i : x) { System.out.print(i + ""); } } ``` 这四个排序算法各有特点，冒泡排序最简单但效率较低，适合小规模数据；选择排序和插入排序同样适用于小规模数据，而插入排序在接近有序的数组中表现优秀；希尔排序则在大规模数据中表现优于前三种，但具体的效率依赖于增量序列的选择。在实际应用中，Java标准库提供了`Arrays.sort()`方法，它采用了更高效的TimSort算法，能更好地适应各种输入数据。