那里建设网站好,网站建设行业资讯,西安微信网站开发,开源cms建站折半插入排序#xff08;Binary Insertion Sort#xff09;是一种插入排序算法#xff0c;通过不断地将数据元素插入到合适的位置进行排序#xff0c;在寻找插入点时采用了折半查找。 一、算法基本思想 #xff08;1#xff09;基本思想 折半插入排序的基本思想是#x… 折半插入排序Binary Insertion Sort是一种插入排序算法通过不断地将数据元素插入到合适的位置进行排序在寻找插入点时采用了折半查找。 一、算法基本思想 1基本思想 折半插入排序的基本思想是顺序地把待排序的序列中的各个元素按其关键字的大小通过折半查找插入到已排序的序列的适当位置。 2运行过程 直接插入排序的运作如下 1、将待排序序列的第一个元素看做一个有序序列把第二个元素到最后一个元素当成是未排序序列。 2、从头到尾依次扫描未排序序列将扫描到的每个元素插入有序序列的适当位置在查找元素的适当位置时采用了折半查找方法。如果待插入的元素与有序序列中的某个元素相等则将待插入元素插入到相等元素的后面。 3示例 二、算法实现核心代码 C实现 void binary_insertion_sort(int arr[], int len)
{int i, j, temp, m, low, high;for (i 1; i len; i){temp arr[i];low 0; high i-1;while (low high){m (low high) / 2;if(arr[m] temp)high m-1;elselow m1;}}for (j i-1; jhigh1; j--)arr[j1] arr[j];arr[j1] temp;
} Java实现 public void binary_insertion_sort(int arr[])
{int i, j, temp, m, low, high, len arr.length;for (i 1; i len; i){temp arr[i];low 0; high i-1;while (low high){m (low high) / 2;if(arr[m] temp)high m-1;elselow m1;}}for (j i-1; jhigh1; j--)arr[j1] arr[j];arr[j1] temp;
} 三、性能算法时间、空间复杂度、稳定性分析 折半查找只是减少了比较次数但是元素的移动次数不变。折半插入排序平均时间复杂度为O(n^2)空间复杂度为O(1)是稳定的排序算法。
