資料結構
網路
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 次檢視
廣告