数据结构
网络
关系数据库管理系统 (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+ 次浏览
广告