折半插入排序其实就是直接插入排序的一种改进,引入了二分查找算法,这样关键字的比较次数就会减少,
数量级为O(nlog^2n),但是元素移动次数还是O(n^2),所以折半插入排序的时间复杂度是O(n^2)。
另外,折半插入排序是稳定的排序算法;
下面是用JAVA写的算法的两种实现方式。不过原理都是一样的
第一种:
package sort;
import java.util.Arrays;
public class BinarySearch1 {
public static void main(String args[])
{
int array[]={49,38,65,97,76,13,27};
binarySort(array,array.length);
System.out.println("---------排序后的结果----------");
System.out.println(Arrays.toString(array));
}
//二分查找
public static int binarySearch(int array[],int low,int high,int temp)
{
int mid=0;
while(low<=high)
{
mid=(low+high)/2;
if(array[mid]<temp&&temp<=array[mid+1])
return (mid+1);
else if(array[mid]<temp)
low = mid + 1;
else
high = mid -1;
}
return high;
}
//二分排序
public static void binarySort(int array[],int size)
{
int i,j,k,temp;
for(i=1;i<size;i++)
{
temp=array[i];
if(array[i]<array[0])
k=0;
else
k = binarySearch(array,0,i,temp);
for(j=i;j>k;j--)
{
array[j]=array[j-1];
}
array[k]=temp;
System.out.println(Arrays.toString(array));
}
}
}
运行结果如下:
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 76, 97, 13, 27]
[13, 38, 49, 65, 76, 97, 27]
[13, 27, 38, 49, 65, 76, 97]
---------排序后的结果----------
[13, 27, 38, 49, 65, 76, 97]
第二种:
package sort;
import java.util.Arrays;
public class BinarySearch2 {
public static void main(String args[])
{
int array[]={49,38,65,97,76,13,27};
binaryInsertSort(array,array.length);
System.out.println("------------排序后的结果-------------");
System.out.println(Arrays.toString(array));
}
/**
*
* @param array 要排序的数组
* @param size 数组的大小
*/
public static void binaryInsertSort(int []array,int size)
{
int i,j,temp;
int low,high,mid;
for(i=1;i<size;i++)
{
//将待插入的元素赋给temp,这个元素前面是有序数组,用于插入到有序数组中
temp=array[i];
low=0;
high=i-1;
while(low<=high)
{
//有序数组的中间坐标,此时用于二分查找,减少查找次数
mid = (low+high)/2;
//如果有序序列中的中间元素大于待排序的元素,则有序序列的中间坐标向前搜索,否则向后搜索
if(array[mid]>array[i])
high=mid-1;
else
low = mid + 1;
}
/**
* j首先赋值为要插入值的前一个元素的最后的坐标,也就是有序数组中最后一个元素的坐标
* 然后依次向前扫描有序数组,然后如果满足条件则向后移动数据
*/
for(j=i-1;j>=low;j--)
{
array[j+1]=array[j];
}
//将待排序的元素插入到array数组中
array[low]=temp;
System.out.println(Arrays.toString(array));
}
}
}
运行结果:
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 97, 76, 13, 27]
[38, 49, 65, 76, 97, 13, 27]
[13, 38, 49, 65, 76, 97, 27]
[13, 27, 38, 49, 65, 76, 97]
------------排序后的结果-------------
[13, 27, 38, 49, 65, 76, 97]
分享到:
相关推荐
根据给定文件中的标题、描述、标签以及部分内容,我们可以总结出关于希尔排序(Shell Sort)、直接插入排序(Direct Insertion Sort)以及折半...而折半插入排序则结合了二分查找的优势来减少比较次数,提高排序速度。
- 折半插入排序是插入排序的一个变体,它在插入元素时使用二分查找来确定插入位置,从而减少比较次数。 - 在查找插入位置时,将数组分成已排序部分和未排序部分,用二分查找找到已排序部分中合适的位置,然后将...
传统的插入排序通过顺序查找的方式确定元素应该插入的位置,而折半插入排序则利用二分查找技术来减少这一过程中的比较次数。 #### 折半插入排序算法原理 折半插入排序的核心思想是在插入排序的基础上,利用二分查找...
折半插入排序(Binary Insertion Sort)是一种改进的插入排序方法,它利用二分查找技术来减少比较次数,从而提高排序效率。现在我们来深入探讨这个主题。 首先,我们要了解插入排序的基本原理。插入排序是一种简单...
2. **折半排序**:这里的“折半”可能是指二分查找排序(Binary Insertion Sort),它是在插入排序的基础上改进的,当在有序序列中插入一个元素时,采用二分查找的方法找到插入位置,以减少比较次数。这种排序方法在...
3. **折半插入排序**:相比于直接插入排序,它改进了插入过程,通过二分查找找到插入位置,降低了比较次数,提高了效率,尤其是对大数据集而言。 4. **希尔排序**:希尔排序是插入排序的一种更高效的版本,通过将...
在这个主题中,我们主要关注查找和排序算法,特别是二分查找(折半查找)算法。这些算法在实际编程中具有广泛应用,包括数据库索引、搜索引擎优化和各种计算问题的解决。 首先,我们来看查找算法。查找是数据结构中...
折半插入排序是一种基于比较的排序算法,其核心思想是通过二分查找来确定待插入元素在已排序部分的合适位置,从而减少比较次数。相比于传统的插入排序,它的效率有所提高,尤其是在处理近似有序的数据时。 **一、...
相比于传统的插入排序,折半插入排序在处理大量数据时效率更高,因为它利用了二分查找算法来减小比较次数。然而,当输入数据已经是部分有序或完全有序时,插入排序(无论是折半还是普通)的性能会非常优秀,接近线性...
折半插入排序是一种改进的插入排序算法,它在进行元素比较时采用二分查找(又称折半查找)的方法来减少比较次数,从而提高排序效率。折半插入排序的核心在于如何通过二分查找找到待插入元素的正确位置。 #### 二、...
**折半查找**,也称为二分查找,适用于有序数组。它通过不断将查找区间减半来缩小搜索范围,平均时间复杂度为O(log n)。折半查找的优势在于效率高,但前提是数据必须事先排序,且不支持动态插入和删除操作。 **二叉...
二分查找排序算法是一种高效的排序方法,它是基于二分查找思想和插入排序的结合体。在计算机科学中,排序算法是处理数据集合的一种基础方法,它使得数据按照特定的顺序排列,例如升序或降序。二分查找排序算法特别...
- `binary_inst` 文件则可能提供折半插入排序的实现,展示如何结合二分查找来提高插入效率。 通过学习这三个文件,你可以更深入地理解插入类排序算法,并且能够实现和优化这些排序算法。在实际编程中,选择适合的...
- 折半查找(又称二分查找)是一种在有序数组中查找特定元素的高效算法。 - 工作原理是从数组中间元素开始比较,如果目标值大于中间值,则在右半部分继续查找;如果目标值小于中间值,则在左半部分继续查找。 - ...
折半插入排序是在插入排序的基础上,利用二分查找来定位新元素的正确位置,从而减少比较次数。它首先将数组分为已排序和未排序两部分,然后将未排序的元素通过二分查找找到合适的位置插入,逐步将未排序部分缩小。 ...
折半插入排序是在插入排序的基础上优化的,它利用二分查找的方法降低插入元素时的比较次数。当需要将一个元素插入已排序的部分时,通过二分查找确定插入位置,减少了比较次数,提高了效率。其平均时间复杂度仍为O(n...
折半查找,也称为二分查找,适用于有序数组。首先确定中间元素,然后与目标值比较。如果目标值小于中间元素,就在数组的左半部分继续查找;如果目标值大于中间元素,就在右半部分查找;如果相等,则查找成功。这个...
折半查找,也被称为二分查找,是一种在有序数组中搜索特定元素的高效算法。它的基本思想是将数组分成两半,然后比较中间元素与目标值,根据比较结果决定是在左半部分还是右半部分继续查找。这个过程一直持续到找到...