首页 > 其他分享 >插入二分排序

插入二分排序

时间:2023-02-20 13:22:12浏览次数:32  
标签:二分 int 插入排序 pos 插入 排序

一、\(STL\)版本的插入二分排序

#include <bits/stdc++.h>
using namespace std;

const int N = 6;
int a[N] = {3, 2, 1, 4, 5, 7};

void BinInsertSort(int a[], int n) {
    for (int i = 1; i < n; i++) { // 把下标0的没处理,做为基础数据,其它的一个个做二分插入排序
        int x = a[i];             // 辅助变量x用来保存待排序的元素,因为后面有整体移动的过程,不单独记下来,后面就被改了
        // 这个代码其实很巧妙的,一个数组分两半用,一半是待插入的,另一个是插入完的,牛啊!
        int pos = lower_bound(a, a + i, x) - a;             // 在a数组中,范围[0,a+i)这个前闭后开的区间内查找第一个大于等于x的位置p
        for (int j = i - 1; j >= pos; j--) a[j + 1] = a[j]; // 移动元素,腾出空间,将pos位置倒出来
        a[pos] = x;                                         // 将待排序的元素插入
    }
}

int main() {
    // 插入排序+二分
    BinInsertSort(a, N);
    for (int i = 0; i < N; i++) printf("%d ", a[i]);
    return 0;
}

二、手写二分版本的插入二分排序

#include <bits/stdc++.h>
using namespace std;

const int N = 6;
int a[N] = {3, 2, 1, 4, 4, 7};

void BinInsertSort(int a[], int n) {
    for (int i = 1; i < n; i++) { // 把下标0的没处理,做为基础数据,其它的一个个做二分插入排序
        int x = a[i];             // 辅助变量x用来保存待排序的元素,因为后面有整体移动的过程,不单独记下来,后面就被改了
        // 这个代码其实很巧妙的,一个数组分两半用,一半是待插入的,另一个是插入完的,牛啊!

        // 手写二分lower_bound模板,左闭右开
        int l = 0, r = i; //[0~i-1] <=> [0,i)
        while (l < r) {
            int mid = (l + r) >> 1;
            if (a[mid] >= x)
                r = mid;
            else
                l = mid + 1;
        }
        // 此处写l,r都是一样的
        for (int j = i - 1; j >= r; j--) a[j + 1] = a[j]; // 移动元素,腾出空间,将pos位置倒出来
        a[r] = x;                                         // 将待排序的元素插入
    }
}

int main() {
    // 插入排序+二分
    BinInsertSort(a, N);
    for (int i = 0; i < N; i++) printf("%d ", a[i]);
    return 0;
}

标签:二分,int,插入排序,pos,插入,排序
From: https://www.cnblogs.com/littlehb/p/17137028.html

相关文章

  • 集合排序 指定元素 在最前or最后
    最近某个需求有个特点,集合中存在各种状态的元素,这些元素按照正常流程展示时直接倒序展示即可,但遇到特殊情况,某个元素需展示在最前。倒序处理指定元素在最前List<Integer......
  • 插入排序
    插入排序的时间复杂度是N^2。插入排序有N-1趟排序组成,对于i=1到N-1趟,插入排序保证从位置0到位置i的元素处于排好的状态。从位置j开始与前一个比较,符合条件的就交换,一直到不......
  • python 二分查找算法
    python二分查找算法 楔子如果有这样一个列表,让你从这个列表中找到66的位置,你要怎么做?l=[2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,......
  • 二分
    目录【整数二分】起止位置【小数二分】求算术平方根【二分答案】切割绳子二分本质给定一个具有单调性的区间\([l,r]\),中间切一刀\(mid=(l+r)/2;\)可以将区间分为两个......
  • Python实现排序算法
    冒泡排序defbubbleSort(arr):foriinrange(len(arr)-1):forjinrange(len(arr)-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1......
  • 排序
    排序题目描述本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。小蓝最近学习了一些排序算法,其中冒泡排序让他印象深刻。在冒泡排序中,每次只能交......
  • 对Map排序
     一下代码为给一个hashMap的key排序,value排序一样处理 publicstaticList<Map.Entry<String,Integer>>sortHashMapInteger(HashMap<String,Integer>map,finalStrin......
  • 各大排序算法的优缺点以及实现方法
    这篇文章,我们来谈谈一些关于排序的东西注意!这篇文章在写的时候混淆了一个概念,“稳定”本义指的是能保证两个相等的数,经过排序之后,序列的前后位置顺序不变。在本文中理解成......
  • [django]drf入门004 过滤排序分页(转载)
    原文:https://pythondjango.cn/1.分页目录为什么要分页?DRF提供的分页类PageNumberPagination类LimitOffsetPagination类CursorPagination类函数类视图中使用分......
  • Educational Codeforces Round 143 (Rated for Div. 2) C(二分+差分维护)
    EducationalCodeforcesRound143(RatedforDiv.2)C(二分+差分维护)C.TeaTasting题目大意:给定n杯茶,n个人,一个进行n论赏茶,赏茶的规律如下:第1轮,第一个人喝第1杯茶,......