折半插入排序（内部排序插入排序）

待我称王封你为后i 2022-05-19 06:43 340阅读 0赞

/*
    算法思想：先折半查找出元素的待插入的位置，然后统一的移动待插入位置后面的元素
    肖煜 
    */
    #include<stdio.h>
    #include<stdbool.h>
    void BinaryInsertSort(int *a, int n)   
    {
        int i, j, k, low, high, m;
        for(i = 1; i < n; i++) {
            low = 0;
            high = i - 1;
    
            while(low <= high) {
                m = (low + high) / 2;
                if(a[m] > a[i]) high = m - 1;
                else low = m + 1;
            }
    
            if(j != i - 1) {
                int temp = a[i];
                for(k = i - 1; k >= high + 1; k--)
                    a[k + 1] = a[k];
                a[k + 1] = temp;
            }
        }
    }
    //void BinaryInsertSort(int A[],int n){
    //	int i,j,low,high,mid;
    //	for(i=2;i<n;i++){
    //		A[0] = A[i];
    //		low = 1;high = i-1;
    //		while(low<high){
    //			mid = (low+high)/2;
    //			if(A[mid]>A[0])
    //			high = mid - 1;
    //			else
    //			low = mid + 1;
    //			
    //		}
    //		for(j=i-1;j>=high+1;--j){
    //			A[j+1] = A[j];
    //		}
    //		A[j+1]=A[0];
    //	}
    //}
    void printArray(int *a, int n)
    {
        for(int i = 0; i < n; i++){
            printf("%d ", a[i]);
    
        }
        printf("\n");
    }
    int main()
    {
        int a[7] = {5,2,1,8,10,23,22};
        BinaryInsertSort(a, 7);
        printArray(a, 7);
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关折半插入排序

折半插入排序算法及测试 package sort; //折半插入排序 public class BinaryInsertSortTest \{ public st

小鱼儿/ 2024年02月17日 15:31/ 0 赞/ 23 阅读

相关折半插入排序

折半插入排序： include <stdio.h> define MaxSize 20 typedef int KeyType; //定义关键字类

左手的ㄟ右手/ 2023年03月13日 03:00/ 0 赞/ 40 阅读

相关排序之直接插入排序和折半插入排序

直接插入排序和折半插入排序 include <iostream> include <cstdio> define Maxsi

朴灿烈づ我的快乐病毒、/ 2022年08月22日 14:13/ 0 赞/ 240 阅读

相关折半插入排序

2016年7月28日08:21:18 折半插入排序:折半插入排序算法是对直接插入排序算法的改进,它的主要改进在于在已经有序的子集中确定待排序元素的位置

亦凉/ 2022年07月16日 13:41/ 0 赞/ 218 阅读

相关折半插入排序

2016年7月28日08:21:18 折半插入排序:折半插入排序算法是对直接插入排序算法的改进,它的主要改进在于在已经有序的子集中确定待排序元素的位置

秒速五厘米/ 2022年07月13日 23:47/ 0 赞/ 220 阅读

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

前言之前已经介绍过了插入排序的原理了。但是对于插入位置的选择就可以通过二分查找法的方式进行求取，加快算法运行。 1. 编码 template<typen

川长思鸟来/ 2022年06月12日 00:19/ 0 赞/ 232 阅读

相关折半插入排序（内部排序插入排序）

/ 算法思想：先折半查找出元素的待插入的位置，然后统一的移动待插入位置后面的元素肖煜 / include<stdio.h>

待我称王封你为后i/ 2022年05月19日 06:43/ 0 赞/ 341 阅读

相关折半插入排序

插入的基本思想 ①每次插入，都从前面的有序子表中查找出待插入元素应该被插入的位置；　　②给插入位置腾出空间，将待插入元素复制到表中的插入位置。　　注意到该算法中，

待我称王封你为后i/ 2022年05月09日 08:28/ 0 赞/ 289 阅读

相关插入排序--直接插入、折半插入

昨天写了交换排序的算法（包括冒泡排序、快速排序），今天写一写插入排序。插入排序有三种：直接插入排序、折半插入排序、希尔排序。时间有限，今天先写一下直接插入排序和折半插入排序

青旅半醒/ 2022年04月10日 05:11/ 0 赞/ 263 阅读

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

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

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