`
leihongtai2010
  • 浏览: 14948 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

二分插入排序的分析与实现

阅读更多
1、基本思想:
  二分插入法与直接排序类似,只是在确定插入位置的方法是用二分法,即从第0个数据开始依次折半与待插入的数据进行比较直到找到合适的位置。

2、图示:
 


3、Java具体代码实现:
  package com.leiht.sort;

public class SortBinary {
	public static void main(String[] args) {
		int[] numbers = { 56, 45, 78, 67, 99, 13, 34, 49, 55, 34, 12, 77, 1 };
		
		System.out.println("排序之前:");
		for (int i = 0; i < numbers.length; i++) {
			System.out.print(numbers[i] + " ");
		}
		
		new SortBinary().sortBinary(numbers);
		
		System.out.println();
		System.out.println("排序之后:");
		for (int i = 0; i < numbers.length; i++) {
			System.out.print(numbers[i] + " ");
		}
	}
	
	private void sortBinary(int[] numbers) {
		for(int i = 0; i < numbers.length; i++) {
			int temp = numbers[i];
			
			int left = 0;
			int right = i -1;
			int middle = 0;
			
			while(left <= right) {
				middle = (left + right)/2;
				if(numbers[i] > numbers[middle]) {
					left = middle+1;
				}else {
					right = middle-1;
				}
			} 
			for(int j = i-1; j >= left; j--) {
				numbers[j+1] = numbers[j];
			}
			numbers[left] = temp;
			System.out.println("left=" + left + ",right=" + right + ",middle=" + middle);
		}
	} 
	
}


4、分析
  显然,二分排序是一种稳定的排序方法
 
  • 大小: 46.8 KB
分享到:
评论

相关推荐

    MATLAB实现插入排序、二分归并排序、归并排序.rar

    在本资源中,我们主要关注的是使用MATLAB编程语言实现三种经典的排序算法:插入排序、二分归并排序以及归并排序。这些算法是计算机科学基础中的重要组成部分,特别是在算法设计与分析领域。MATLAB是一种强大的数值...

    易语言源码二分插入排序.rar

    在这个“易语言源码二分插入排序.rar”压缩包中,我们可以找到一个用易语言实现的二分插入排序的代码示例。 易语言是一种中国本土开发的、面向对象的编程语言,其设计目标是让编程变得简单、直观。它的语法结构简洁...

    二分插入排序算法

    使用二分方法实现插入排序

    易语言二分插入排序

    这个过程可以应用于各种场景,如数据分析、数据处理等,只要涉及到对大量数据的有序排列,二分插入排序都是一个实用的选择。 总的来说,易语言二分插入排序是利用易语言的特点,结合二分查找优化的排序算法,它在...

    内部排序之二分插入排序

    ### 内部排序之二分插入排序:深入解析与实现 #### 一、知识点概览 在计算机科学中,排序算法是数据结构与算法领域的重要组成部分,广泛应用于各种场景,如数据库管理、搜索引擎优化等。其中,二分插入排序是一种...

    JS实现二分插入排序,前端必会

    以下是关于JS实现二分插入排序的详细解释。 首先,我们需要了解基本的插入排序。插入排序的基本思想是将未排序的元素逐个插入到已排序的部分,从而逐步构建出一个有序序列。在JS中,这个过程通常通过遍历数组并比较...

    插入排序的设计实现分析比较.rar_C# 插入_插入排序

    在二分插入排序中,我们在寻找插入位置时使用二分查找,这可以显著减少比较次数,提高效率。但是,由于插入操作仍然需要移动元素,时间复杂度仍为O(n²),但常数因子有所减少。 在《插入排序的设计实现分析比较.doc...

    二分插入排序-易语言.zip

    5. **递归与迭代**:虽然二分插入排序通常不采用递归实现,但在易语言中,理解递归和迭代的概念有助于扩展其他算法的理解。 6. **性能分析**:二分插入排序的平均时间复杂度为O(nlogn),最好情况(已排序)为O(n),...

    易语言二分插入排序.rar

    3. **循环与递归**:二分插入排序通常使用循环结构来实现,遍历未排序部分的每一个元素,重复执行上述步骤。在易语言中,可以使用`循环`或`计次循环`指令来实现。 4. **易语言语法**:易语言的语法简洁明了,如定义...

    java实现插入排序

    -二分查找插入:在插入元素时,可以使用二分查找找到合适的位置,减少比较次数,但增加了一些额外的计算。 - 当前元素与其相邻元素交换:在比较过程中,可以直接与相邻元素交换位置,避免不必要的移动。 总结来说...

    C++实现插入排序

    - **二分查找插入排序**:在插入排序的过程中,使用二分查找来寻找插入位置,减少比较次数。 - **改进的插入排序**:在发现元素已经有序时,可以提前结束排序过程。 综上所述,插入排序是一种基础且实用的排序算法...

    常用算法 2分法插入排序

    2分法插入排序的时间复杂度在最坏情况下为O(n²),与传统插入排序相同,但在平均情况下,由于二分查找的引入,时间复杂度可以降低到O(n log n)。空间复杂度为O(1),因为该算法是原地排序,不需要额外的存储空间。 ...

    插入排序,C语言实现

    /* * --插入排序-- * 假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大, * 则将这个数的位置往后挪,直到当前外层元素的... * 该算法可以认为是插入排序的一个变种,称为二分查找排序。 */

    模拟实验-C#版基于二分查找的稳定“插入排序”算法

    这有助于我们了解在实际应用中,二分查找插入排序与冒泡排序在处理相同数据集时的速度差异。 总的来说,这个实验提供了一个深入理解和实践排序算法的平台,特别是如何利用二分查找优化插入排序的过程。通过对C#代码...

    易语言源码二分插入排序.7z

    在这个“易语言源码二分插入排序.7z”压缩包中,包含了一个使用易语言实现的二分插入排序算法的源代码文件。 二分插入排序的工作原理是这样的:首先,将待排序的数组分为已排序和未排序两部分,初始状态已排序部分...

    插入排序C语言实现

    此外,插入排序还可以通过一些优化策略来提高性能,例如二分查找法。在寻找插入位置时,如果使用二分查找,可以将内层循环的时间复杂度从O(n)降低到O(logn),但总的时间复杂度仍为O(n^2),因为外层循环不变。 总的...

    数据结构 折半插入排序

    5. **折半插入排序与普通插入排序的区别** 6. **折半插入排序的应用场景** 7. **C语言实现** #### 折半插入排序的基本概念 折半插入排序是插入排序的一种变种,它在插入排序的基础上采用了二分查找的方法来减少比较...

    Java实现插入排序

    在Java中实现插入排序,我们可以按照以下步骤进行: 1. **基本思想**:将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。可以想象成每次从无序序列中取出一个元素,找到它在有序序列中...

Global site tag (gtag.js) - Google Analytics