二分插入排序

墨蓝 2022-05-28 00:39 164阅读 0赞

### 二分插入排序 ###

##### 算法描述： #####

二分插入排序通过从第二个数开始将需要排序的数分为两个部分，左边部分有序，右边部分无序，然后从右边部分第一个数开始，一个一个插入前面有序部分，与直接插入排序唯一不同的是：二分插入排序会先找出左边有序部分的中间值，然后与需要插入的值比较，所以在插入之前，就只需要与左边有序部分的一半值进行比较。因此，在数据量比较大的时候，二分插入排序算法就更加高效，速度更快。

##### 时间复杂度：O(n\*n) #####

##### 空间复杂度：o(1) #####

java实现：

public static void binaryInsertSort(int[] str) {
    		for (int i = 1; i < str.length; i++) {
    			if (str[i] < str[i - 1]) {
    				int temp = str[i]; // 定义temp存储所要插入的数
    				int left = 0; // 最左边的数，从str[0]开始
    				int right = i - 1; // 最右边位，所要插入那个数的前一位
    				while (left <= right) {
    					int mid = (left + right) / 2; // mid中间位
    					if (str[mid] < temp) { // 中间位与str[i]比较
    						left = left + 1;
    					} else { // 通过if语句找到应该插入的位置str[left]
    						right = right - 1;
    					}
    				}
    				for (int j = i; j > left; j--) { // 将str[left]->str[i-1]的数都往后移一位
    					str[j] = str[j - 1];
    				}
    				str[left] = temp; // 最后将str[i]插入str[left]
    			}
    		}
    	}

GitHub地址：[https://github.com/xckNull/Algorithms-introduction.git][https_github.com_xckNull_Algorithms-introduction.git]

[https_github.com_xckNull_Algorithms-introduction.git]: https://github.com/xckNull/Algorithms-introduction.git

发表评论取消回复

表情：

评论列表（有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读

相关冒泡、选择、插入、二分排序算法

冒泡排序: 首先,冒泡排序又称起泡排序我这里总结了排序两种冒泡排序一种是普通的冒泡排序,一种是优化后冒泡,冒泡排序就是拿第一个数其他所有的数去比较,经过一趟比较把这组数据最大

拼搏现实的明天。/ 2023年10月17日 14:26/ 0 赞/ 52 阅读

相关二分查找插入排序算法

二分查找插入算法二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排

╰+哭是因爲堅強的太久メ/ 2023年07月06日 14:46/ 0 赞/ 26 阅读

相关折半插入排序(二分插入排序)-JAVA语言版本

import java.util.Arrays; public class BinaryInsertSort { //这般插入排序

曾经终败给现在/ 2023年06月07日 12:26/ 0 赞/ 20 阅读

相关 C语言实现插入排序和二分查找

include <iostream> using namespace std; // 输出数组 void printAll(int a

刺骨的言语ヽ痛彻心扉/ 2023年03月14日 10:51/ 0 赞/ 54 阅读

相关插入排序-简单插入排序和二分插入排序

插入排序：插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从

亦凉/ 2022年12月12日 13:58/ 0 赞/ 241 阅读

相关 Java二分插入排序

public class BinaryInsertSort\{ public static void main(String args \[\])\{

淡淡的烟草味﹌/ 2022年08月21日 04:50/ 0 赞/ 143 阅读

相关二分插入排序

二分插入排序算法描述：二分插入排序通过从第二个数开始将需要排序的数分为两个部分，左边部分有序，右边部分无序，然后从右边部分第一个数开始，一个一个插入前面有序部

墨蓝/ 2022年05月28日 00:39/ 0 赞/ 165 阅读

相关 java--冒泡排序、选择排序、二分查找、插入排序

冒泡排序、选择排序、二分查找、插入排序冒泡排序冒泡排序的思想就是两两比较，按从小到大输出的话，两个值相比，较小的放前大的放后，那么第一次两两比较结束后，最大

桃扇骨/ 2022年05月15日 17:39/ 0 赞/ 316 阅读

相关二分排序(折半插入排序)探究

算法思想：二分法插入排序是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比。如果小，则对前半再进行折半，否则对后半进行折半，直到left>r

川长思鸟来/ 2022年03月18日 07:14/ 0 赞/ 255 阅读

相关插入排序——折半插入排序

折半插入排序是基于直接插入排序的优化。 [直接插入排序][Link 1] 将第i个元素插入时，通过折半查找的方式，来查找第i个元素合适的位置。推导过程当0~

悠悠/ 2021年12月13日 14:45/ 0 赞/ 386 阅读