希尔排序 用java实现
时间: 2023-06-02 20:05:02 浏览: 46
希尔排序是一种插入排序算法,它的主要思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组被称为 h 有序数组。希尔排序会不断减小 h 的值,直到最后 h=1 时,所有元素就都是有序的了。
下面是用 Java 实现的希尔排序代码:
```
public void shellSort(int[] arr) {
int n = arr.length;
// 构造增量序列
int h = 1;
while (h < n / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
// 将数组变为 h 有序
for (int i = h; i < n; i++) {
// 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
int e = arr[i];
int j = i;
for (; j >= h && e < arr[j - h]; j -= h) {
arr[j] = arr[j - h];
}
arr[j] = e;
}
// 减小 h
h /= 3;
}
}
```
相关问题
用java实现希尔排序
以下是 Java 实现希尔排序的代码:
```java
public class ShellSort {
public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = { 12, 34, 54, 2, 3, 1, 5, 7, 23, 4 };
System.out.println("排序前:");
System.out.println(Arrays.toString(arr));
shellSort(arr);
System.out.println("排序后:");
System.out.println(Arrays.toString(arr));
}
}
```
希尔排序的基本思想是把待排序的元素分成若干个子序列,每个子序列是一个小的插入排序,通过逐步缩小子序列的间隔,最终实现整个序列的有序。
写一个希尔排序java实现
希尔排序是一种改进的插入排序算法,它通过将数组分成多个子序列来提高插入排序的效率。以下是一个希尔排序的Java实现示例:
```java
public class ShellSort {
public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {9, 5, 1, 4, 3, 2, 8, 7, 6};
shellSort(arr);
System.out.println("排序结果:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```