二分插入排序

墨蓝 2022-05-28 00:39 139阅读 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 条评论，139人围观）

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

相关阅读

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

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

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

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

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

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

相关 Java二分插入排序

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

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

相关二分插入排序

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

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

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

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

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

相关插入排序——直接插入排序

/ 直接插入排序算法思想：将整个数据表分成左右两个子表，其中左子表为有序表，右子表为无序表；整个排序过程就是将右子表中的元素逐

布满荆棘的人生/ 2022年03月20日 02:52/ 0 赞/ 305 阅读

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

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

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

相关排序 - 插入排序 [1 - 直接插入排序]

在这篇文章中，你将看到最容易理解的一种排序方法：直接插入排序。请保证你有连续的20分钟来看这个算法，如果你用2分钟就看明白了，好吧，你一定是超人。首先来描

布满荆棘的人生/ 2022年01月14日 01:34/ 0 赞/ 333 阅读

相关插入排序——直接插入排序

思路：对位置i上的元素排序(设为升序)时（设为Ai），假设从0~(i-1)位置上的元素都已经全部排好序。所以，只需要为Ai在已经排好序的元素中找到合适的位置，并将其

本是古典何须时尚/ 2021年12月13日 23:27/ 0 赞/ 415 阅读

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

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

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