不知

二分法插入排序

2021-11-02|来源:|发布者:

二分法插入排序,简称二分排序,是在插入第i个元素时,对前面的0~i-1元素进行折半,先跟他们中间的那个元素比,如果小,则对前半再进行折半,否则对后半进行折半,直到left

1. 时间复杂度

二分插入排序是稳定的与二分查找的复杂度相同;

最好的情况是当插入的位置刚好是二分位置 所用时间为O(log₂n);

最坏的情况是当插入的位置不在二分位置 所需比较次数为O(n),无限逼近线性查找的复杂度。

S<=∑n「log₂n「-2^n「log₂n「+1

k= 1

平均时间O(n^2)

2. 算法实现

二分法排序C语言

/* 二分法插入排序的算法源程序*/
#include<stdio.h>
#define MAXNUM 100
typedef int KeyType;
typedef int DataType;
typedef struct
{
    KeyType key; /* 排序码字段 */
    /*DataType info; 记录的其它字段 */
} RecordNode;
typedef struct
{
    int n; /* n为文件中的记录个数,n<MAXNUM */
    RecordNode record[MAXNUM];
} SortObject;
void binSort(SortObject * pvector) /* 按递增序进行二分法插入排序 */
{
    int i, j, left, mid, right;
    RecordNode temp;
    RecordNode *data = pvector->record;
    for( i = 1; i < pvector->n; i++ )
    {
        temp = data[i];
        left = 0;
        right = i-1; /* 置已排序区间的下、上界初值 */
        while (left <= right)
        {
            mid = (left + right)/2; /* mid指向已排序区间的中间位置 */
            if (temp.key < data[mid].key)
                right = mid-1; /* 插入元素应在左子区间 */
            else left = mid+1; /* 插入元素应在右子区间 */
        }
        for (j = i-1; j >= left; j--)
            data[j+1] = data[j]; /* 将排序码大于ki的记录后移 */
        if (left != i) data[left] = temp;
    }
}
SortObject vector= {10, 49,38,65,97,76,13,27,49,50,101};
int main()
{
    int i;
    binSort(&vector);
    for(i = 0; i < vector.n; i++)
    printf("%d ", vector.record[i]);
    getchar();
    return 0;
}

二分法排序JAVA

public static void advanceInsertSortWithBinarySearch(int[] arr) {
	    for (int i = 1; i < arr.length; i++) {
	        int temp = arr[i];
	        int low = 0, high = i - 1;
	        int mid = -1;
	        while (low <= high) {            
	            mid = low + (high - low) / 2;            
	            if (arr[mid] > temp) {               
	                high = mid - 1;            
	            } else { // 元素相同时,也插入在后面的位置                
	                low = mid + 1;            
	            }        
	        }        
	        for(int j = i - 1; j >= low; j--) {            
	            arr[j + 1] = arr[j];        
	        }        
	        arr[low] = temp;    
	    }
	}

二分法排序Python

# 二分法插入排序是在插入排序的基础上,使用二分法查找将元素插入的方法
# 基本原理:(升序)
# 1.将元素依次放入有序序列中
# 2.取出待排序元素,与有序序列的前半段进行比较
# 3.缩小有序序列范围,进一步划分比较,直至范围内仅有1或2个数字
# 4.将插入值与范围进行比较
# 3.重复实现升序
# 实现过程:外层循环控制循环次数,中层循环实现有序排列,内层循环实现查找插入
import random

# 生成序列
Range = 10
Length = 5
list = random.sample(range(Range),Length)
print('before sort:',list)

# 元素插入
for i in range(1,Length):            #从第2个元素开始,插入到前一部分元素中
    beg,end = 0,i-1                  #定义插入范围
    mid = (beg + end) // 2           #定义二分/中间边界

    while beg < end:                #当边界顺序时,进行二分比较
        mid = (beg + end) // 2
        if mid == beg:               #如果中间值与边界相等,则边界已确定,结束二分
            break
        #在确定中间与边界不相等时,对边界继续缩小
        if list[i] == list[mid]:
            break
        elif list[i]<list[mid]:
            end = mid
        else:
            beg = mid

    #首先确定是否因为找到同值而提前终止
    if list[i] == list[mid]:
        list.insert(mid, list[i])
        list.pop(i + 1)
    else:
        if beg == end:              #如果范围内仅仅有一个值
            if list[i] < list[beg]:
                list.insert(beg,list[i])
            else:
                list.insert(beg+1, list[i])
            list.pop(i + 1)
        elif beg < end:             #如果范围内有两值
            if list[i] < list[beg]:
                list.insert(beg,list[i])
            elif list[i] < list[end]:
                list.insert(end, list[i])
            else:
                list.insert(end+1, list[i])
            list.pop(i + 1)
        else:
            print("wrong, start at ",beg,', and end with ',end)

print('after sort:',list)

二分法排序Go语言

// BinaryInsertionSort 二分插入排序
func BinaryInsertionSort(arr []int) {
    len := len(arr)
    if len < 2 {
        return
    }

    for i := 1; i < len; i++ {
        low := 0
        high := i
        for low <= high {
            middle := (low + high) / 2
            if arr[middle] > arr[i] {
                high = middle - 1
            } else {
                low = middle + 1
            }
        }

        for j := i - 1; j >= low; j-- {
            arr[j], arr[j+1] = arr[j+1], arr[j]
        }
    }
    return
}
用手机扫一扫访问本站
利民吧文章数据均来自于互联网,版权归原作者所有。如有侵犯您权利的资源,请联系我们处理。
Copyright © 2016-2024 利民吧 版权所有