数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究Java ShellSort 程序
在本文中，我们将学习如何使用Java编写Shell Sort程序。在程序中，我们将应用此技术对数组进行排序，并观察算法如何通过减少元素之间的间隔来优化排序过程。
希尔排序
希尔排序是一种排序技术，类似于插入排序，其中对数组两端（任一端）的元素进行排序。这样，下一个元素和倒数第二个元素之间的间隔大小就会减小。这会发生在数组中的所有元素上，直到间隔距离减小到 0。
问题陈述
编写一个 Java 程序，实现希尔排序以对整数数组进行排序。该程序应遵循希尔排序算法，重复排序元素，并逐渐减小间隔，直到整个数组排序完成。
输入
my_arr = 12, 34, 54, 2, 3
输出
The array, after performing shell sort is :
2 3 12 34 54
希尔排序算法
以下是希尔排序算法：
- 将初始间隔确定为数组长度的一半。
- 对于每个间隔，遍历数组，选择每个元素，并将其插入到间隔排序数组中的正确位置。
- 重复此过程，每次将间隔减半，直到间隔变为零。
- 返回排序后的数组。
Java ShellSort 程序
以下是 Java 中希尔排序的示例：
public class Demo {
int shell_sort(int my_arr[]) {
int arr_len = my_arr.length;
for (int gap = arr_len / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr_len; i += 1) {
int temp = my_arr[i];
int j;
for (j = i; j >= gap && my_arr[j - gap] > temp; j -= gap)
my_arr[j] = my_arr[j - gap];
my_arr[j] = temp;
}
}
return 0;
}
public static void main(String args[]) {
int my_arr[] = { 12, 34, 54, 2, 3 };
Demo my_instance = new Demo();
my_instance.shell_sort(my_arr);
System.out.println("The array, after performing shell sort is : ");
int arr_len = my_arr.length;
for (int i = 0; i < arr_len; ++i)
System.out.print(my_arr[i] + " ");
System.out.println();
}
}
输出
The array, after performing shell sort is : 2 3 12 34 54
时间复杂度：它在 O(N) 和 O(N^2) 之间变化。
空间复杂度：最坏情况下的空间复杂度为 O(N)，辅助空间为 O(1)。
代码解释
此算法对彼此相距较远的元素进行排序，从而减少这两个元素之间的间隔。可以理解为插入排序的广义版本。首先对数组中特定间隔的元素进行排序，然后它们的间隔距离减小，从而在此过程中对所有元素进行排序。
当第一次循环迭代时，获取数组的大小，并比较 size/2 之间的元素，如果它们未排序则交换。对所有其他元素重复相同操作。通过定义一个临时变量并交换元素来对元素进行排序。
在第二次循环迭代中，比较并排序 size/4 个元素。对其余元素执行相同的过程，从而对它们进行排序。在主函数中，定义数组，并通过将此数组作为参数来调用“shell_sort”函数。
更新于： 2024年11月15日
604 次查看
广告