ShellSort 的 Java 程序
java 8server side programmingprogramming
Shell 排序是一种类似于插入排序的排序技术，其中对位于数组远端(两端)的元素进行排序。这样，下一个元素与倒数第二个元素之间的间隔大小就会减小。数组中的所有元素都会发生这种情况，直到间隔距离减小到 0。
示例
以下是 Java 中 ShellSort 的一个示例 −
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
解释
该算法对彼此相距较远的元素进行排序，从而缩小这两个元素之间的间隔。它可以理解为插入排序的广义版本。首先对数组中位于特定间隔的元素进行排序，然后缩小它们的间隔距离，从而在此过程中对所有元素进行排序。
第一次循环迭代时，获取数组的大小，并比较size/2之间的元素，如果未排序，则交换它们。对所有其他元素重复相同的操作。通过定义一个临时变量并交换元素来对元素进行排序。
在第二次循环迭代中，比较size/4之间的元素并进行排序。对剩余元素重复相同的过程，从而对它们进行排序。在主函数中，定义数组，并通过将该数组作为参数传递来调用‘shell_sort’函数。
