最近在研究Java数据结构和算法
练习写了一个用插入排序的算法
查找部分使用二分查找实现的
和大家分享一下 呵呵
还请各位大牛多指教啊
呵呵
import java.util.Random;
public class InsertSort {
/**
* 插入排序算法实现
* @author Jason
* @param arr
* @return
*/
public static int[] insertSort(int[] arr) {
int searchCount = 0;
for (int out = 1; out < arr.length; out++) {
outPrint(arr);
if (arr[out]>arr[out-1]) {
continue;
}
//普通查找算法
/*for (int inn = 0; inn < out; inn++) {
searchCount++;
if (arr[out]<arr[inn]) {
move(arr,out,inn);
break;
}else {
continue;
}
}*/
//使用二分查找算法找到要插入的位置
int start = 0;
int end = out - 1;
while (start <= end) {
searchCount++;
int searchIndex = (start + end) / 2;
if (arr[out] > arr[searchIndex]) {
start = searchIndex + 1;
} else if (arr[out] < arr[searchIndex]) {
if (searchIndex == 0
|| (searchIndex != 0 && arr[out] > arr[searchIndex - 1])) {
move(arr, out, searchIndex);
break;
} else {
end = searchIndex - 1;
continue;
}
} else {
move(arr, out, searchIndex);
break;
}
}
}
check(arr);
System.out.println("Search Count:" + searchCount);
return arr;
}
/**
* 移动数据
*/
private static void move(int[] arr, int out, int inn) {
int changeTemp = arr[out];
for (int i = out; i > inn; i--) {
arr[i] = arr[i - 1];
}
arr[inn] = changeTemp;
}
/**
* 输出
*/
private static void outPrint(int[] arr) {
System.out.println();
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + "|");
}
}
/**
* 结果检查
*/
private static boolean check(int[] arr) {
System.out.println();
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) {
System.out.println("Sort Error!");
return false;
}
}
System.out.println("Sort Success!");
return true;
}
/**
* 测试方法
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Random ran = new Random();
int[] arr = new int[60];
for (int i = 0; i < arr.length; i++) {
arr[i]=ran.nextInt(300000);
}
System.out.println("Befor sort:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+"|");
}
arr = InsertSort.insertSort(arr);
System.out.println("After sort:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+"|");
}
}
}
分享到:
相关推荐
在本资源中,我们主要关注的是使用MATLAB编程语言实现三种经典的排序算法:插入排序、二分归并排序以及归并排序。这些算法是计算机科学基础中的重要组成部分,特别是在算法设计与分析领域。MATLAB是一种强大的数值...
在这个“易语言源码二分插入排序.rar”压缩包中,我们可以找到一个用易语言实现的二分插入排序的代码示例。 易语言是一种中国本土开发的、面向对象的编程语言,其设计目标是让编程变得简单、直观。它的语法结构简洁...
使用二分方法实现插入排序
- **二分查找插入排序**:在插入排序的过程中,使用二分查找来寻找插入位置,减少比较次数。 - **改进的插入排序**:在发现元素已经有序时,可以提前结束排序过程。 综上所述,插入排序是一种基础且实用的排序算法...
-二分查找插入:在插入元素时,可以使用二分查找找到合适的位置,减少比较次数,但增加了一些额外的计算。 - 当前元素与其相邻元素交换:在比较过程中,可以直接与相邻元素交换位置,避免不必要的移动。 总结来说...
在此,我们将深入探讨二分插入排序的基本原理、实现方法以及在易语言中的应用。 首先,我们来理解二分插入排序的基本概念。这种排序算法基于插入排序,但通过引入二分查找来提高效率。在插入排序中,我们将未排序的...
2分法插入排序(Binary Insertion Sort)是一种基于插入排序的算法,它结合了二分查找的策略来优化传统插入排序的过程。在传统插入排序中,我们需要将一个新元素与已排序的序列逐个比较,找到合适的位置插入。而2分...
以下是关于JS实现二分插入排序的详细解释。 首先,我们需要了解基本的插入排序。插入排序的基本思想是将未排序的元素逐个插入到已排序的部分,从而逐步构建出一个有序序列。在JS中,这个过程通常通过遍历数组并比较...
- 可以考虑使用二分查找法来定位待插入元素的位置,以减少比较次数,但这会增加算法的复杂性,使其不再是线性时间复杂度。 - 对于接近有序的数组,插入排序的性能非常优秀,因此在某些排序算法中,例如希尔排序,...
学习易语言的二分直接插入排序源码可以帮助初学者更好地理解这种排序算法的内部工作原理,以及如何在易语言环境下实现高级算法。 在"content.txt"文件中,可能会包含具体的易语言源代码实现,通过阅读和分析这些...
### 内部排序之二分插入排序:深入解析与实现 #### 一、知识点概览 在计算机科学中,排序算法是数据结构与算法领域的重要组成部分,广泛应用于各种场景,如数据库管理、搜索引擎优化等。其中,二分插入排序是一种...
在本模拟实验中,我们关注的是使用C#编程语言实现基于二分查找的稳定“插入排序”算法。插入排序是一种简单直观的排序算法,它的工作原理是通过构造一个有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到...
折半插入排序是插入排序的一种变种,它在插入排序的基础上采用了二分查找的方法来减少比较次数,从而提高排序效率。传统的插入排序通过顺序查找的方式确定元素应该插入的位置,而折半插入排序则利用二分查找技术来...
接下来,我们来看C语言中的插入排序实现。以下是一个简单的C语言代码示例: ```c #include void insertion_sort(int arr[], int n) { int i, key, j; for (i = 1; i ; i++) { key = arr[i]; j = i - 1; /* ...
在这个"二分插入排序-易语言.zip"压缩包中,我们可以预期包含的是关于如何使用易语言实现二分插入排序的详细教程或源代码。 易语言是一款中国本土开发的编程语言,以简洁明了的中文语句设计,使得编程对初学者更为...
3. **循环与递归**:二分插入排序通常使用循环结构来实现,遍历未排序部分的每一个元素,重复执行上述步骤。在易语言中,可以使用`循环`或`计次循环`指令来实现。 4. **易语言语法**:易语言的语法简洁明了,如定义...
- **二分查找**:在将元素插入已排序部分时,使用二分查找找到合适的位置,可以降低比较次数。 - **插入排序优化**:对于近乎有序的数组,插入排序表现优秀,因此可以先进行简单的预处理,检查数组是否接近有序。 ...