现在我来简单叙述一下二分法排序的思想,
1,从第0个元素开始用二分排序法递归产生有序序列
2,假设现在插入第i个元素,前面的0~i-1已经是有序的
3,设定left=0,i-1=right,
4,折半,用i元素跟[0~i-1]中间元素比,如果小,则进行前折半,否则进行后折半,直到left>right
5,把最终left与i-1之间的所有元素后移,再把第i个元素放在left位置上。
6,循环插入下一个元素,直到整个序列有序
/**
* 二分法排序<br>
* 根据排序原则,每次我们都是在一个有序序列中插入一个新的数字<br>
* 那么我们可以将这个有序序列进行二分。<br>
* 左游标left为0,右游标right为i-1(i是这个数字在原数组中的位置)<br>
* middle初始为。<br>
* 当left<=right时<br>
* middle是left和right的中值。<br>
* 我们作如下操作。如果array[i]的值比array[middle]值大。<br>
* 那么我们就移动左游标令值为middle+1<br>
* 负责就移动右游标为middle-1<br>
* 移动完成后,我们需要将i-1到left之间的值进行依次向后移动给array[i]空出一个位置然后将array[i]插入
* <p style="color:red">时间复杂度n</p>
*/
public int[] binaryInsertSort(int[] array){
for(int i = 0;i<array.length;i++){
int temp = array[i];//待插入到前面有序序列的值
int left = 0;//有序序列的左侧
int right = i-1;//有序序列的右侧
int middle = 0;//有序序列的中间
while(left <= right){
middle = (left + right)/2;//赋值
if(temp<array[middle]){
right = middle-1;
}else{
left = middle + 1;
}
}
for(int j = i-1;j>=left;j--){
//从i-1到left依次向后移动一位,等待temp值插入
array[j+1] = array[j];
}
if(left != i ){
array[left] = temp;
}
}
return array;
}
插入排序
对于未排序数据(右手抓到的牌),在已排序序列(左手已经排好序的手牌)中从后向前扫描,找到相应位置并插入。
插入排序与二分排序的区别
插入排序需要额外的空间存放有序序列,二分排序在原有的序列上排序
插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,比如量级小于千,那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用,在STL的sort算法和stdlib的qsort算法中,都将插入排序作为快速排序的补充,用于少量元素的排序(通常为8个或以下)。
二分插入排序
如果比较操作的代价比交换操作大的话,结合插入排序和二分排序,采用二分查找法来减少比较操作的次数,我们称为二分插入排序
分享到:
相关推荐
本文将基于二分排序法时间复杂度的求解过程进行深入探讨,分析该算法在不同场景下的性能表现,并通过实际代码展示其具体实现。 在进行算法分析时,时间复杂度是一个不可或缺的概念。它反映了算法执行时间与输入数据...
二分查找排序算法是一种高效的排序方法,它是基于二分查找思想和插入排序的结合体。在计算机科学中,排序算法是处理数据集合的一种基础方法,它使得数据按照特定的顺序排列,例如升序或降序。二分查找排序算法特别...
在本资源中,我们主要关注的是使用MATLAB编程语言实现三种经典的排序算法:插入排序、二分归并排序以及归并排序。这些算法是计算机科学基础中的重要组成部分,特别是在算法设计与分析领域。MATLAB是一种强大的数值...
冒泡排序和二分排序是两种常见的排序算法,在计算机科学中有着广泛的应用。它们各自具有不同的特点和适用场景,下面将详细介绍这两种排序方法。 首先,我们来看冒泡排序(Bubble Sort)。冒泡排序是一种简单的排序...
使用二分方法实现插入排序
常见的经典排序算法有希尔排序、二分插入法、直接插入法、带哨兵的直接排序法、冒泡排序、选择排序、快速排序、堆排序等。 一、希尔排序(Shell 排序法) 希尔排序法,又称宿小增量排序,是 1959 年由 D.L.Shell ...
二分查找算法与冒泡排序算法是计算机科学中两种基础且重要的算法,它们在数据处理和数组操作中扮演着至关重要的角色。 首先,我们来详细探讨递归二分查找算法。二分查找,也称为折半查找,是一种在有序数组中查找...
二分插入排序是一种基于二分查找的改进排序算法,它在插入新元素时使用二分查找来确定元素应插入的位置,从而减少比较次数。具体步骤如下: 1. 对于数组中的每个元素,假设为待插入元素。 2. 使用二分查找找到待...
易语言是一种基于中文编程的计算机...通过理解和实践这些代码,不仅能掌握二分排序的原理,还能进一步提升在易语言环境下的编程能力。对于初学者来说,这是一个很好的学习资源,有助于提高编程技能和解决问题的能力。
在提供的压缩包文件中,“易语言二分排序源码.e”显然是易语言编写的源代码文件,而“简单说明.txt”可能包含了对这个排序算法的简要介绍或使用指南。 二分排序,也称为二分插入排序,是基于二分查找的一种排序算法...
本资源“C#经典排序算法大全和二分查找算法”提供了多种经典的排序算法实现,以及C#中的二分查找算法。让我们深入探讨这些算法的原理、实现方式以及它们在实际开发中的应用。 首先,我们来看一下排序算法。排序是将...
合并排序算法和二分搜索技术算法的实现实验报告.doc
二分归并排序是一种高效的排序算法,它结合了分治策略和归并操作。在MATLAB环境中实现二分归并排序,可以让我们更好地理解和运用这种算法。以下将详细阐述二分归并排序的工作原理、MATLAB实现过程以及相关知识点。 ...
二分插入排序是一种高效且常用于优化的排序算法,尤其在处理近似有序的数据时表现优秀。它结合了二分查找的效率与插入排序的稳定性。在这个“易语言源码二分插入排序.rar”压缩包中,我们可以找到一个用易语言实现的...
2分法插入排序(Binary Insertion Sort)是一种基于插入排序的算法,它结合了二分查找的策略来优化传统插入排序的过程。在传统插入排序中,我们需要将一个新元素与已排序的序列逐个比较,找到合适的位置插入。而2分...
二分插入排序是一种改进的插入排序算法,它利用了二分查找的思想来减少在序列中找到合适插入位置的时间复杂度。在直接插入排序中,为了找到一个元素的正确位置,我们需要从当前元素开始向后逐个比较,直到找到合适的...
二分排序作为插入排序的一种变体,尽管在某些特定场景下并不比其他高级排序算法更快,但它的思想和实现过程对于理解分治法和优化基础排序算法有着重要的意义。在编程实践中,我们应该根据实际需求,结合算法的性能...
总的来说,这个实验提供了一个深入理解和实践排序算法的平台,特别是如何利用二分查找优化插入排序的过程。通过对C#代码的学习和分析,开发者可以提升对数据结构和算法的理解,并能更好地运用这些知识去解决实际问题...
这篇描述涉及到了几个高级的排序算法,其中包括快速排序、桶排序和二分插入排序,这些都是高效且广泛应用的排序方法。让我们详细了解一下这些算法以及如何在C++中实现它们。 **快速排序** 是由C.A.R. Hoare在1960年...