資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Java實現二分插入排序
二分插入排序使用二分查詢來查詢在每次迭代中插入元素的正確位置。首先，找到需要插入元素的位置。然後，將元素向右移動。現在，將特定元素放置在該位置。
問題陳述
給定一個整數陣列，使用Java實現二分插入排序對其進行排序。該演算法應使用二分查詢來確定每個元素的正確位置，並透過相應地移動元素來保持排序順序。
二分插入排序步驟
以下是二分插入排序的步驟：
- 步驟1：初始化，實現二分查詢。
- 步驟2：為了為當前元素騰出空間，我們將元素向右移動。
- 步驟3：將當前元素插入到確定的位置。
- 步驟4：列印排序前後的陣列。
二分查詢演算法
二分查詢演算法是一種區間搜尋方法，它只在區間內執行搜尋。
- 步驟1：要搜尋關鍵字，我們將選擇陣列中的中間值並將其與關鍵字進行比較，如果匹配，則返回其位置。
- 步驟2：如果關鍵字與中間值不匹配，則檢查關鍵字是大於還是小於中間值。
- 步驟3：如果關鍵字更大，則在右子陣列中執行搜尋；但如果關鍵字小於中間值，則在左子陣列中執行搜尋。
- 步驟4：迭代地重複步驟1、2和3，直到子陣列的大小變為1。
- 步驟5：如果在陣列中找不到關鍵字，則返回一個值來指示搜尋不成功。
Java實現二分插入排序
以下是二分插入排序的Java程式碼：
public class Demo {
void Cocktail_Sort(int my_arr[]) {
boolean swapped = true;
int start = 0;
int end = my_arr.length;
while (swapped == true) {
swapped = false;
for (int i = start; i < end - 1; ++i) {
if (my_arr[i] > my_arr[i + 1]) {
int temp = my_arr[i];
my_arr[i] = my_arr[i + 1];
my_arr[i + 1] = temp;
swapped = true;
}
}
if (swapped == false)
break;
swapped = false;
end = end - 1;
for (int i = end - 1; i >= start; i--) {
if (my_arr[i] > my_arr[i + 1]) {
int temp = my_arr[i];
my_arr[i] = my_arr[i + 1];
my_arr[i + 1] = temp;
swapped = true;
}
}
start = start + 1;
}
}
void print_values(int my_arr[]) {
for (int i = 0; i < my_arr.length; i++)
System.out.print(my_arr[i] + " ");
System.out.println();
}
public static void main(String[] args) {
Demo my_object = new Demo();
int my_arr[] = { 6, 8, 34, 21, 0, 1, 98, 64, 6};
System.out.println("The array contains ");
for (int i = 0; i < my_arr.length; i++)
System.out.print(my_arr[i] + " ");
System.out.println();
my_object.Cocktail_Sort(my_arr);
System.out.println("The array after implementing cocktail sort is : ");
my_object.print_values(my_arr);
}
}
輸出
The array contains 6 8 34 21 0 1 98 64 6 The array after implementing cocktail sort is : 0 1 6 6 8 21 34 64 98
程式碼解釋
該類Demo執行雞尾酒排序並列印陣列的值。main方法初始化Demo類和一個帶有值的整數陣列my_arr。它列印原始陣列，呼叫Cocktail_Sort方法對陣列進行排序，然後列印排序後的陣列。
該方法Cocktail_Sort首先將布林變數swapped初始化為true，並將start設定為0，end設定為陣列的長度。
只要swapped為true，while迴圈就會繼續。最初，在每次迭代開始時，swapped被設定為false。
一個for迴圈從start索引迭代到end - 1。在每次迭代中，都會比較相鄰的元素。如果一個元素大於下一個元素，則交換它們，並將swapped設定為true。
如果在正向傳遞中沒有交換元素，則陣列已排序，迴圈中斷。
如果交換了元素，則swapped再次設定為false，並且end遞減1。另一個for迴圈從end - 1執行到start。如果一個元素大於下一個元素，則交換它們，並將swapped設定為true。
反向傳遞之後，start遞增1。然後迴圈重複，直到在正向和反向傳遞中都沒有交換元素。
print_values方法接受一個數組並列印其元素在一行中。
更新於：2024年7月2日
3K+ 次瀏覽
廣告