精华内容
下载资源
问答
  • 之前的文章介绍了简单插入排序法。我们知道插入排序的核心操作是在子序列中找到要插入的位置并插入。其实子序列本身是有序的,所以在有序的子序列中,我们完全可以使用折半查找,而不是粗暴的遍历,进而达到降低时间...

    之前的文章介绍了简单插入排序法。我们知道插入排序的核心操作是在子序列中找到要插入的位置并插入。其实子序列本身是有序的,所以在有序的子序列中,我们完全可以使用折半查找,而不是粗暴的遍历,进而达到降低时间复杂度的目的。
    在这里插入图片描述
    首先简单介绍下折半查找。折半查找的用途非常广泛,可以高效的解决很多实际问题。而且时间复杂度仅有 O ( log ⁡ 2 n ) O(\log_2n) O(log2n)
    在这里插入图片描述
    既然已经明白了原理,下面我就直接贴代码了,使用JS来实现,过程可以参考代码中的注释

    function binIntertSort(seq) {
    	let low, mid, high, i, j, temp;
    	// 从第二个元素开始,第一个本身就是有序的。
    	for(i=1;i<seq.length;i++) {
    		temp = seq[i]; // 待插入的元素
    		low = 0; // low 在每一趟查找中都是0
    		high = i - 1; // high 就是当前需要插入的元素的前一个位置
    		while(low <= high) { // 若low不再小于high了,那么就找到了待插入的位置
    			mid = Math.floor((low + high) / 2) // 中间位置
    			if(temp < seq[mid]) {
    				high -= 1; // 下一趟再找前半序列
    			} else {
    				low += 1; // 否则找后半序列
    			}
    		}
    		// 在即将插入的位置后边的所有元素依次前移一个位置,最终会空出要插入的位置。
    		for (j=i;j>low;j--) {
    			seq[j] = seq[j-1];
    		}
    		// 插入!
    		seq[j] = temp;
    	}
    }
    binIntertSort(seq)
    console.log(seq)
    // [1, 2, 3, 4, 5, 6, 6, 7, 9 ]
    

    相较于前文的简单插入排序法,折半查找插入排序,时间复杂度由原来的 O ( n 2 ) O(n^{2}) O(n2) 降低到了 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2n),当然这是最好的情况下。在实践中,如果需要稳定的低时间复杂度的算法。可以考虑后边介绍的堆积排序。

    展开全文
  • 排序算法:折半插入排序算法折半插入排序算法的定义:折半插入排序算法的原理折半插入排序算法的代码实现:折半插入排序算法的性能: 折半插入排序算法的定义: 插入排序时查找要插入位置用折半查找 折半插入...

    思维导图:

    在这里插入图片描述

    折半插入排序算法的定义:

    插入排序时查找要插入位置用折半查找法

    折半插入排序算法的原理:

    见直接插入排序

    折半插入排序算法的代码实现:

    void BInsertSort(int a[],int n){
    	int low,high,mid;
    	int i,j; 
    	for(i=2;i<n;i++){
    		a[0] = a[i];
    		low = 1;high = i-1;
    		//折半查找
    		while(low <= high){
    			mid = (low+high)/2;
    			if(a[mid] > a[0])
    				high = mid-1;
    			else
    				low = mid+1;
    		}
    		//移动
    		for(j = i-1;j>=high+1;j--)
    			a[j+1] = a[j];
    		a[high+1] = a[0];
    	}
    }
    

    折半插入排序算法的性能:

    时间复杂度:O(n^2)

    与“直接插入排序”相比,比较关键字的次数减少了,但是移动元素的次序没变,整体来看时间复杂度依然是O(n^2)

    空间复杂度:O(1)
    稳定
    只适用与顺序存储

    展开全文
  • 二分法(折半法)查找 当我们需要查找某个已经排序了的数组中某个元素的下标时,选择线性查找时需要遍历数组,如果数组长度很大,查找的效率比较低,因此可以采用二分法查找,原理见以下代码: /** * 二分法(折半法...

    二分法(折半法)查找

    当我们需要查找某个已经排序了的数组中某个元素的下标时,选择线性查找时需要遍历数组,如果数组长度很大,查找的效率比较低,因此可以采用二分法查找,原理见以下代码:

    
    /**
     * 二分法(折半法)查找算法:
     * 二分法查找或折半查找:前提是数组已经进行排序,原理:
     * 每次查找中间下标对应的元素和目标元素进行比较,
     * 小于目标元素则中间下标+1并作为下次折半的起始下标,大于目标元素则中间下标-1并作为下次折半的末尾下标;
     * 例如:arr数组排序后: 2(下标0),3,4,5,6,8,9,15(下标7)
     * 目标:找出 6 对应的下标
     * 中间下标:(0+7)/2=3
     * arr[3]=5, 5 < 6 说明查找的目标元素在下标 3 的右边,则起始下标为3+1=4
     * 中间下标:(4+7)/2=5
     * arr[5]=8, 8 > 6 说明查找的目标元素在下标 5 的左边,则末尾下标为5-1=4
     * 中间下标:(4+4)/2=4
     * arr[4]=6, 6 = 6 说明查找的目标元素在下标 4 。
     */
    public class Search {
        public static void main(String[] args) {
            int[] arr = {2, 3, 4, 5, 6, 8, 9, 15};
            
            System.out.println(binarySearch(arr, 6));//4
        }
    
        /**
         * 二分法查找(折半法查找)
         *
         * @param arr  被查找的数组
         * @param dest 目标元素
         * @return 大于等于 0 的元素表示目标元素的下标,等于 -1 表示没找到对应的下标
         */
        public static int binarySearch(int[] arr, int dest) {
            int begin = 0;//起始下标
            int end = arr.length - 1;//末尾下标
            
            while (begin <= end) {
                int mid = (begin + end) / 2;//中间下标
                if (arr[mid] < dest) {
                    begin = mid + 1;
                } else if (arr[mid] > dest) {
                    end = mid - 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }
    }
    
    
    展开全文
  • 本篇文章来聊一聊折半插入排序。 基本思想 先来回顾一下直接插入排序的算法思想,就是在前面已经排好序的子序列中寻找一个待插入的位置,然后将待插入元素插入到该位置上。 其中寻找插入位置的过程我们是与每一个...

    本篇文章来聊一聊折半插入排序。

    基本思想

    先来回顾一下直接插入排序的算法思想,就是在前面已经排好序的子序列中寻找一个待插入的位置,然后将待插入元素插入到该位置上。

    其中寻找插入位置的过程我们是与每一个元素进行比较,相当于顺序查找,我们知道顺序查找的效率是比较低的,那么有没有办法能够提高查找插入位置的效率呢?

    很巧的是,前面的序列既然已经是有序的了,我们何不采用折半查找来找出插入位置呢?折半查找的前提就是序列有序,采用折半查找法查找插入位置的插入排序算法,我们称其为折半插入排序。

    图解排序过程

    折半插入算法非常简单,前提你得掌握直接插入排序和折半查找的算法,来看一个例子:
    在这里插入图片描述
    原序列的前四个元素已经有序,则从i位置元素开始进行插入排序,先将i位置元素存入下标0作为哨兵,然后在子序列中寻找待插入位置。

    这时我们可以采用折半查找法进行查找,定义三个变量low、high和mid,初始low = 1,high = i - 1,则mid为2。

    让哨兵位置元素值与mid位置元素值比较,7大于5,所以插入位置应该在右半区࿰

    展开全文
  • 折半排序法(二分插入排序法)

    千次阅读 2016-07-14 09:45:24
    /*------------------------------------------------------------------------------------------------  折半排序(二分插入排序) 排序原理:其实也属于插入类型,分已排序和未排序部分.然后将未排序
  • 1、折半插入排序(binary insertion sort)是对插入排序算法的一种改进,由于排序算法过程中,就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列,这样我们不用按顺序依次寻找插入点,...
  • 折半插入排序法---排序算法(二)

    千次阅读 2013-10-23 11:53:17
    1.排序原理 2.代码 #include void printArray(int a[],int size){ printf("数组为:[%d] ",a[0]); for (int i=1;i;i++) { printf(" %d ",a[i]); } printf("\n"); }
  • 排序算法总结之折半插入排序

    千次阅读 2014-08-29 18:27:29
    基本思想 折半插入排序是对直接插入排序的简单改进,对于直接插入排序而言,当第i-1趟需要将第i个元素插入前面的0~i-1个元素序列中时,总是需要从i-1个元素开始,逐个比较每个元素,直到找到它的位置。这显然没有...
  • 排序折半插入排序

    千次阅读 多人点赞 2018-08-30 11:53:16
    折半插入排序是直接插入排序的改进版,减少了待插入元素与已排序序列中元素的比较次数,主要是结合了顺序中的二分查找的思想,但移动次数上并没有比直接插入排序少。
  •   对于插入排序,如果比较操作的代价比交换操作大的话,可以采用二分查找来减少比较操作的次数,我们称为二分插入排序 算法描述:   在直接插入排序的基础上,利用二分(折半)查找算法决策出当前元素所要插入的...
  • 之前已经介绍过了插入排序原理了。但是对于插入位置的选择就可以通过二分查找的方式进行求取,加快算法运行。 1. 编码 template struct Disp { void operator()(T value) { cout ; } }; //折半插入排序 ...
  • 折半插入排序(C语言)

    千次阅读 多人点赞 2020-06-09 18:35:11
    1.排序原理 利用折半查找的方法来查找插入的位置,然后再直接将需要插入的数据插入该位置即可 排序过程 以从小到大排序为例,首先用key存储需要排序的数据 第一步:折半查找——用low、mid、high划分两个区域...
  • 折半插入排序与直接插入排序算法原理相同。只是,在向已排序的数据中插入数据时,采用来折半查找(二分查找)。先取已经排序的序列的中间元素,与待插入的数据进行比较,如果中间元素的值大于待插入的数据,那么待...
  • 排序2:插入排序折半插入排序

    千次阅读 2014-09-25 21:32:07
    直接插入排序把原始序列分成两部分,已有序和仍无序部分。每趟排序,从仍无序的部分中选取头个元素,在已有序的部分中寻找插入位置...说的没错,接下来要介绍的折半插入排序正是读者们想看到的。  继续以序列49、38、
  • 插入排序算法之折半插入排序算法

    千次阅读 2018-04-19 11:34:24
    在百度百科开了折半排序算法的原理后,自己试着根据原理写出了版本一的算法,版本二是参照巨人的实现思想,版本二才是重点。版本一可以忽略不看。算法同样的目的是寻找正确的插入点。版本一:实现思想:第一步:获取...
  • 经典排序算法(4)——折半插入排序算法详解

    万次阅读 多人点赞 2016-03-16 13:12:51
    折半插入排序(Binary Insertion Sort)是一种插入排序算法,通过不断地将数据元素插入到合适的位置进行排序,在寻找插入点时采用了折半查找。 一、算法基本思想 (1)基本思想 折半插入排序的基本思想是:...
  • 所以可以将折半查找思想用于在有序记录r[1...i-1]中确定应插入的位置,相应的算法排序称为折半插入算法。 算法的基本过程:  1)计算 0 ~ i-1 的中间点,用 i 索引处的元素与中间值进行比较,如果 i 索引处的...
  • 选择法排序 选择法排序是指:如果要把一个数组从小到大排列,那么就从该数组中依次选择最小的数字来排序。从第一个数字开始,将第一个数字与数组中剩下数字中最小的那一个交换位置,然后将第二个数字与剩下数字中...
  • 折半插入算法是对直接插入排序算法的改进,排序原理同直接插入算法: 把n个待排序的元素看成一个有序表和一个无序表,开始时有序表中只有一个元素,无序表中有n-1个元素;排序过程即每次从无序表中取出第一个元素,...
  • 插入排序(直接插入排序折半插入排序、希尔排序)快速排序(基于交换的一种排序方式,最常见的是 冒泡排序)选择排序(简单选择排序、堆排序)归并排序基数排序 一、直接插入排序 基本操作:将一个数据插入到已排...
  • java实现折半插入排序算法

    千次阅读 2015-09-04 06:03:49
    前言折半插入排序算法是一种排序的算法,它通过“折半查找”在比较区查找插入点的位置,这样可以减少比较的次数,移动的次数不变,时间复杂度仍为 O(n^2);算法描述
  • 二,折半插入排序 三,希尔排序 四,简单选择排序排序 冒泡排序 快速排序 归并排序 基数排序 #include&amp;amp;amp;lt;stdio.h&amp;amp;amp;gt; #include&amp;amp;amp;lt;stdlib.h&amp;...
  •  折半插入算法是对直接插入排序算法的改进,排序原理同直接插入算法:  把n个待排序的元素看成一个有序表和一个无序表,开始时有序表中只有一个元素,无序表中有n-1个元素;排序过程即每次从无序表中取出第一个...
  •  二分插入排序(Binary Insertion Sort,折半插入排序 OR拆半插入排序),采用折半查找方法。  二分查找插入排序原理:是直接插入排序的一个变种;区别是:在有序区中查找新元素插入位置时,为了减少元素比较...
  • 直接插入排序基本原理:对于给定的一组记录,初始时假设第一个记录自成一个有序序列,其余的记录为无序序列;接着从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序的序列中,直至最后一个...
  • 折半排序

    2018-11-27 17:40:38
    //算法8.1 直接插入排序 //2018年11月26日 #include &lt;iostream&gt; #include&lt;stdlib.h&gt; using namespace std; #define MAXSIZE 20 //顺序表的最大长度 typedef struct { int key; ...
  • 以下是我对常见的几种排序算法的总结并给出的代码,基于C++语言实现,存储格式是顺序表。本人才疏学浅,如果有错漏还请各位指正。 一、存储格式:顺序表 int *data; //存储数据(data[1...size]存储待排序序列,data...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,736
精华内容 2,294
关键字:

折半法排序原理