首页 > 编程语言 >折半插入排序算法思想及代码实现

折半插入排序算法思想及代码实现

时间:2024-08-01 18:27:02浏览次数:16  
标签:折半 arr 插入排序 元素 插入 算法 排序

折半插入排序(Binary Insertion Sort)是插入排序算法的一种优化版本。插入排序的基本思想是将一个记录插入到已经排序好的有序表中,从而得到一个新的、记录数增加1的有序表。传统的插入排序在寻找插入位置时,采用的是顺序比较的方式,即逐个与有序表中的元素进行比较,直到找到比待插入元素大的元素或达到有序表的末尾。而折半插入排序则是在这个查找过程中使用了二分查找(Binary Search)的思想,从而减少了比较的次数,提高了排序的效率。

折半插入排序算法思想

  1. 初始化:假设数组的第一个元素是已经排序好的,因此从第二个元素开始遍历数组。

  2. 二分查找插入位置:对于每个待排序的元素(从第二个元素开始),使用二分查找的方法在已经排序好的数组部分中查找该元素的正确插入位置。即,在已排序序列中从后往前(或从前往后,取决于具体实现)使用二分查找法找到第一个不小于(或大于)待插入元素的位置。

  3. 插入元素:找到插入位置后,将该位置及之后的所有元素都向后移动一位,为新元素腾出空间,然后将新元素插入到找到的位置。

  4. 重复:重复步骤2和3,直到遍历完整个数组。

折半插入排序的特点

  • 优点
    • 相较于传统的插入排序,折半插入排序在查找插入位置时采用了二分查找,减少了比较次数,提高了效率。
    • 折半插入排序仍然是稳定的排序算法,即相等的元素在排序后的相对位置不会改变。
  • 缺点
    • 虽然查找插入位置时使用二分查找减少了比较次数,但元素移动的次数并未减少,这仍然是插入排序的一个主要瓶颈。
    • 对于数据量很大的情况,折半插入排序的性能仍然不够高效,特别是对于已经接近有序的数组,其效率提升并不明显。

适用场景

折半插入排序适用于数据量不大,且数据基本有序的情况。在数据量较小时,其效率可以接近甚至超过一些更复杂的排序算法,如快速排序、归并排序等。但在数据量较大时,由于其元素移动的开销较大,性能可能不如其他排序算法。

Java代码实现

import java.util.Arrays;
/*
有序区内
arr[high]以及之前的元素都小于等于element
从arr[low]及以后的元素都大于element
 */
public class BinaryInsertSort {
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};
        binaryInsertSort(arr);
    }

    private static void binaryInsertSort(int[] arr) {
        //        i代表待插入元素的索引
        for (int i=1;i<arr.length;i++){
//            待排的素
            int element=arr[i];
//            已排序区域的最后元素索引
            int low=0;
            int high=i-1;
//            如果待插入元素比已排序区的最后一个元素大则不用管直接进行下一轮插入
            if(element>arr[high]){
                continue;
            }
//
            while(low<=high){
                int mid=(low+high)/2;
                if(element<arr[mid]){
                    high=mid-1;
                }else {
                    low=mid+1;
                }
            }
//            有序区内
//            arr[high]以及之前的元素都小于等于element
            if (high < 0) {
                // 如果 high < 0,说明所有已排序的元素都大于或等于 element
                // 将 element 插入到数组的开始位置
                for (int j = i; j > 0; j--) {
                    arr[j] = arr[j - 1];
                }
                arr[0] = element;
            } else {
                // 从已排序的最后一个元素开始到arr[high+1]依次往后移
                for (int j = i - 1; j >= high + 1; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[high + 1] = element;
            }
            System.out.println(Arrays.toString(arr));
        }
    }
}

标签:折半,arr,插入排序,元素,插入,算法,排序
From: https://blog.csdn.net/a486368464/article/details/140848383

相关文章

  • 数据结构与算法 - 递归
    一、递归1. 概述定义:在计算机科学中,递归是一种解决计算问题的方法,其中解决方案取决于同一类问题的更小子集。比如单链表递归遍历的例子:voidf(Nodenode){if(node==null){return;}println("before:"+node.value)f(node.next);pr......
  • 数据结构与算法 - 链表
    一、链表1.概述定义:在计算机科学中,链表是数据元素的线性集合,其每个元素都指向下一个元素,元素存储上并不连续。可以分类为:单向链表,每个元素只知道其下一个元素是谁双向链表,每个元素直到其上一个元素和下一个元素循环链表,通常的链表尾节点tail指向的都是null,而循环链表......
  • OpenSSH秘钥指纹图像生成算法
    OpenSSH秘钥指纹图像生成算法使用SSH秘钥生成时产生疑惑,它的randomartimage是如何生成的?下面进行了探索和研究引入生成位数为4096位的rsa公私钥ssh-keygen-trsa-b4096Generatingpublic/privatersakeypair.Enterfileinwhichtosavethekey(/root/.s......
  • 第2章 基础算法
    2.1初级(1)尺取法⭐反向扫描(左右指针)hdu2029Palindromes_easyversionimportjava.util.Scanner;publicclassMain{ publicstaticvoidmain(String[]args){ Scannersc=newScanner(System.in); intn=sc.nextInt(); for(;n>0;n--){ char[]s......
  • 论文阅读:高效的广义最稠密子图发现算法
    摘要这篇论文提出了一种高效算法,通过利用广义超模密度定义和......
  • 机器学习-算法分类以及用途
    1.监督学习算法线性回归(LinearRegression)目的:用于预测一个或多个自变量(X)与因变量(Y)之间的线性关系。应用领域:房价预测、销售预测、温度预测等连续值预测问题。逻辑回归(LogisticRegression)目的:虽然名为回归,但实际上是用于二分类问题的分类算法。应用领域:垃圾邮件识别、......
  • prim算法求最小生成树
    prim算法求最小生成树#include<bits/stdc++.h>usingnamespacestd;constintN=600;intg[N][N];//n的平方约等于m,所以用邻接矩阵,存放权值。g[i][j]表示边ij的长度为g[i][j]constintinf=0x3f3f3f3f;//无穷大0x3f3f3f3fintdist[N];//该点到集合里点的最小值boolst[N]......
  • 克鲁斯卡尔算法
    克鲁斯卡尔算法稀疏图-->用克鲁斯卡尔算法克鲁斯卡尔算法套路:首先存放每条边用struct然后按照权值从小到大排序然后如果这条边的两个端点已经在一个连通块就不要把这条边放进来(因为生成树不能有闭合回路)如已经有边12,边13不能再放入边23判断连通块用find函数利用并查集算法......
  • 刀具磨损预测工器具磨损预测-RIME-CNN-SVM霜冰算法优化-完整代码数据
    直接看项目演示:刀具磨损预测工器具磨损预测-RIME-CNN-SVM霜冰算法优化_哔哩哔哩_bilibili效果演示:代码: importnumpyasnpimporttorchimporttorch.nnasnnimporttorch.nn.functionalasFimporttorch.optimasoptimfromtorch.utils.dataimportDataLoad......
  • 代码随想录算法训练营第56天 | 广搜和深搜应用
    110.字符串接龙https://kamacoder.com/problempage.php?pid=1183代码随想录https://www.programmercarl.com/kamacoder/0110.字符串接龙.html#思路105.有向图的完全可达性https://kamacoder.com/problempage.php?pid=1177代码随想录https://www.programmercarl.com/kamaco......