折半插入排序

C语⾔数组的五种简单排序，选择法排序，冒泡法排序、交换法排序、插⼊法排序、折半法排序⽂章⽬录1、选择法排序选择法排序是指每次选择索要排序的数组中的最⼩值（这⾥是由⼩到⼤排序，如果是由⼤到⼩排序则需要选择最⼤值）的数组元素，将这些数组元素的值与前⾯没有进⾏排序的数组元素值进⾏互换代码实现需要注意的是：声明⼀个数组和两个整形变量，数组⽤于存储输⼊的数字，⽽整形变量⽤于存储最⼩的数组元素的数值与该元素的位置，在我的代码中实现为a[] temp position。

代码具体如下#include<stdio.h>int main(){int m,n,k;printf("please input the length of the array:");scanf("%d",&k);int a[k];int temp;int position;printf("please input the number of the array:\n");for(m=0;m<k;m++){printf("a[%d]=",m+1);scanf("%d",&a[m]);}/*从⼩到⼤排序*/for(m=0;m<k-1;m++){temp=a[m]; //设置当前的值为最⼩值position=m; //记录当前的位置for(n=m+1;n<k;n++){if(a[n]<temp){temp=a[n]; //如果找到⽐当前的还要⼩的数值，则更换最⼩的数值与位置position=n;}}a[position]=a[m];a[m]=temp;}for(m=0;m<k;m++){printf("%d\t",a[m]);}return 0;}结果如下2、冒泡法排序冒泡法排序就是值在排序时，每次⽐较数组中相邻的两个数组元素的值，将⽐较⼩的（从⼩到⼤排序算法，如果是从⼤到⼩排序算法就是将较⼤的数排在较⼩的数前⾯）排在⽐较⼤的前⾯在代码实现的过程中：声明⼀个数组与⼀个整型变量，数组⽤于存放数据元素，整型变量⽤于交换时作为中间变量。

（共八种排序方法：直接插入排序，折半插入排序，冒泡排序，简单选择排序，希尔排序，快速排序，堆排序，归并排序）一.简单排序1.直接插入排序：a)思想：每次从后面无序表中取出第一个元素，通过循环比较把它插入到前面有序表的合适位置，使前面有序表仍然有序。

b)稳定性：稳定c)时空效率：时间复杂度：O(n^2) 空间复杂度：O(1)d)代码：/******************************************function: InsertSort 直接插入排序paramaters: list[] 形参数组length 数组长度（并非最大下标）******************************************/void InsertSort(int list[],int length){int temp,i,j;for(i=1;i<length;i++){if(list[i]<list[i-1]){temp=list[i];//保存小值list[i]=list[i-1];//大值向后移一位for(j=i-1;j>=1&&temp<list[j-1];j--){list[j]=list[j-1];}list[j]=temp;}}}2.折半插入排序：a) 思想：在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到low>hight，找到插入位置low，然后把low到i-1的所有元素均后移一位，再把第i个元素放在目标位置low上。

b) 稳定性：稳定c) 时空效率：时间复杂度：O(n^2) 空间复杂度：O(1)d) 代码：/******************************************function: BInsertSort 折半插入排序又叫二分法插入排序paramaters: list[] 形参数组length 数组长度（并非最大下标）******************************************/void BInsertSort(int p[],int length){int i,j,low,high,m,temp;for(i=1;i<length;i++){temp=p[i];low=0;high=i-1;while(low<=high){m=(low+high)/2;if(p[i]<p[m])//插入点是high+1,而非m,因为有的循环m变化了，而m与high没有发生关系，//循环就结束了，他们的关系还保留在上一层，因此插入点应该用high来保存{high=m-1;}else low=m+1;}// 其实用low更方便点，不用再对low做任何改变/*for(j=i-1;j>=high+1;j--){p[j+1]=p[j];}p[high+1]=temp;*/for(j=i-1;j>=low;j--){p[j+1]=p[j];}p[low]=temp;}}3.冒泡排序：a) 思想：依次比较相邻的两个数，将小数放在前面，大数放在后面。

各种排序的实现与效率分析一、排序原理（1）直接插入排序基本原理：这是最简单的一种排序方法，它的基本操作是将一个记录插入到已排好的有序表中，从而得到一个新的、记录增1的有序表。

效率分析：该排序算法简洁，易于实现。

从空间来看，他只需要一个记录的辅助空间，即空间复杂度为O（1）.从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。

当待排序列中记录按关键字非递减有序排列（即正序）时，所需进行关键字间的比较次数达最小值n-1，记录不需移动；反之，当待排序列中记录按关键字非递增有序排列（即逆序）时，总的比较次数达最大值（n+2）(n-1)/2，记录移动也达到最大值（n+4）(n-2)/2.由于待排记录是随机的，可取最大值与最小值的平均值，约为n²/4.则直接插入排序的时间复杂度为O（n²）.由此可知，直接插入排序的元素个数n越小越好，源序列排序度越高越好（正序时时间复杂度可提高至O（n））。

插入排序算法对于大数组，这种算法非常慢。

但是对于小数组，它比其他算法快。

其他算法因为待的数组元素很少，反而使得效率降低。

插入排序还有一个优点就是排序稳定。

（2）折半插入排序基本原理：折半插入是在直接插入排序的基础上实现的，不同的是折半插入排序在将数据插入一个有序表时，采用效率更高的“折半查找”来确定插入位置。

效率分析：由上可知该排序所需存储空间和直接插入排序相同。

从时间上比较，折半插入排序仅减少了关键字间的比较次数，为O(nlogn)。

而记录的移动次数不变。

因此，折半查找排序的时间复杂度为O(nlogn)+O（n²）= O（n²）。

排序稳定。

（3）希尔排序基本原理：希尔排序也一种插入排序类的方法，由于直接插入排序序列越短越好，源序列的排序度越好效率越高。

Shell 根据这两点分析结果进行了改进，将待排记录序列以一定的增量间隔dk 分割成多个子序列，对每个子序列分别进行一趟直接插入排序, 然后逐步减小分组的步长dk，对于每一个步长dk 下的各个子序列进行同样方法的排序,直到步长为1 时再进行一次整体排序。

24种插入法24种插入法是一种优化排序算法，它的基本思想是将一个列表分为已排序区间和未排序区间，每次从未排序区间取出一个元素，插入到已排序区间的正确位置，使已排序区间保持有序。

在这个过程中，相邻元素的比较和交换次数都很少，所以可以提高排序的效率。

此外，24种插入法还有一些变体，可以根据不同情况选用相应的插入法，达到更好的排序效果。

以下是24种插入法的详细介绍：1. 直接插入排序直接插入排序是最简单的插入法，它将未排序元素插入到已排序区间合适的位置。

时间复杂度为O(n²)，空间复杂度为O(1)。

2. 折半插入排序折半插入排序是对直接插入排序的优化，它采用二分查找的方式找到插入位置。

时间复杂度为O(n²)，空间复杂度为O(1)。

3. 希尔排序希尔排序是一种针对直接插入排序的改进，它将列表按照一定步长分组，每个子列表采用直接插入排序，随着步长逐渐缩小，最终变为一组，完成排序。

时间复杂度为O(nlogn)，空间复杂度为O(1)。

4. 二路插入排序二路插入排序是对直接插入排序的改进，它采用两个指针，在有序区间之前和之后分别插入未排序元素。

时间复杂度为O(n²)，空间复杂度为O(1)。

5. 多关键词插入排序多关键词插入排序是针对多关键词排序的优化，它将排序条件拆分为多个关键词，分别进行插入排序。

时间复杂度为O(nlogn)，空间复杂度为O(1)。

6. 基数插入排序基数插入排序是对基数排序的优化，它使用插入法对每个桶内的元素进行排序，并合并桶内已排序的元素。

时间复杂度为O(dn)，空间复杂度为O(max)。

7. 大小插入排序大小插入排序是对多关键词排序的优化，它根据元素的大小关系建立排序树，对树进行遍历并插入已排序区间。

时间复杂度为O(nlogn)，空间复杂度为O(nlogn)。

8. 块插入排序块插入排序是对桶排序的优化，它将待排序元素分为若干块，分别进行插入排序，再将已排序块合并。

折半插入排序算法：也叫二分插入排序算法。

这种算法和直接插入算法基本一样。

都是属于插入排序。

所以时间复杂度为N2，空间复杂度为1.最好情况时间复杂度是n。

先看看这种算法思想。

折半插入算法与直接插入不同是：不是比的过程，那是插的过程。

二分排序想名字就是把有序的东西分成2半。

比如说你向1 2 3 4 5 6这个有序序列插入4,你怎么插，你可以先和6比，在和5比这样可以做。

但是作为一个有序序列你如果和中间比，如果比中间大就和后面那一部分比，然后后面又找中间部分。

在平均的情况下比直接插这比要快。

例如：有一个数要排列97 6 4 5 1 5 7第一趟排，就找第二个数看看和前一个数的大小，然后确定插入的位置7 96 4 5 1 5 7 后面同理6 7 94 5 1 5 74 6 7 95 1 5 74 5 6 7 91 5 71 4 5 6 7 9571 4 5 5 6 7 971 4 5 5 6 7 7 9看这个排序过程和直接插入排序一模一样只是代码实现上是不同的。

不同在向有序序列插入的过程。

大家看看实现代码：package com.fish.sort;public class MiddleInsertSort {public static void main(String[] args) {int[] array = new int[] { 9, 7, 6, 4, 5, 1, 5, 7 };myResult(array);}public static void myResult(int[] array) {for (int i = 1; i < array.length; i++) {// 比较当前数和前一个数的大小if (array[i] < array[i - 1]) {// 后一个数比前一个数小，就把后面的大数放一个交换区int swap = array[i];// 定义高低位是用来确定，前面有序序列的大小。

详解排序算法（⼀）之3种插⼊排序（直接插⼊、折半插⼊、希尔）直接插⼊排序打过牌的⼈都知道，当我们拿到⼀张新牌时，因为之前的牌已经经过排序，因此，我们只需将当前这张牌插⼊到合适的位置即可。

⽽直接插⼊排序，正是秉承这⼀思想，将待插⼊元素与之前元素⼀⼀⽐较，从⽽找到合适的插⼊位置。

那么使⽤直接插⼊排序，具体是怎样操作的呢？我们取 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 来进⾏⽰范。

（1）第1轮排序，3之前⽆可⽐较值，因此我们从44开始操作，取44和3⽐较，⼤于3，顺序保持不变。

得数据3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（2）第2轮排序，取38和44⽐较，38 < 44，再将38与3⽐较，38 > 3，故将38放于第2位，得数据3, 38, 44, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（3）第3轮排序，取5与44⽐较，5 < 44，再将5与38⽐较，5 < 38，再将5与3⽐较，5 > 3, 置于第2位，得数据3, 5, 38, 44, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（4）如此经过14轮排序后，得到最终结果2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50动态图javascript实现function directInsertSort (arr) {let compare, // 对⽐元素下标current // 待插⼊元素值for (let i = 1; i < arr.length; i++) {current = arr[i]compare = i - 1while (current < arr[compare] && compare >= 0) {arr[compare + 1] = arr[compare]compare--}arr[compare + 1] = current}return arr}折半插⼊排序细⼼的同学可能已经注意到，当我们要将⼀个元素插⼊合适的位置时，其之前的元素是有序的，因此，我们可以⽤折半查找的⽅式来⽐对并插⼊元素，也就是所谓的折半插⼊排序。

国家开放大学电大《数据结构》网络课形考任务4作业及答案形考任务4一、单项选择题（每小题2分，共40分）题目1对线性表进行二分查找时，要求线性表必须（）o选择一项：A.以链接存储方式B.以链接存储方式，旦数据元素有序C.以顺序存储方式D.以顺序存储方式，且数据元素有序题目2采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

选择一项：A.nB.（n-l）/2C.n/2D.（n+1） /2题目3有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。

选择一项：A.29/9B.29/10C.26/10D.31/10题目4已知一个有序表为｛11, 22, 33, 44, 55, 66, 77, 88, 99）,则顺序查找元素55需要比较（）次。

选择一项：A. 6B. 3C.5D. 4题目5有数据（53, 30, 37, 12, 45, 24, 96）,从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）o选择一项：A.12, 24, 30, 37, 45, 53, 96B.30, 24, 12, 37, 45, 96, 53C.45, 24, 53, 12, 37, 96, 30D.37, 24, 12, 30, 53,45, 96题目6对于顺序存储的有序表{5, 12, 20, 26, 37, 42, 46, 50, 64},若采用折半查找，则查找元素26的比较次数是（）。

选择一项：A.4B. 6C. 3D. 5题目7在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（）o选择一项：A.希尔排序B.直接选择排序C.冒泡排序D.直接插入排序题目8从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。

将其放入已排序序列的正确的位置上，此方法称为（）。

选择一项：A.插入排序B.选择排序C.归并排序D.交换排序题目9依次将每两个相邻的有序表合并成一个有序表的排序方法称为（）o选择一项：A.交换排序B.归并排序C.插入排序D.选择排序题目10当两个元素出现逆序的时候就交换位置，这种排序方法称为（）。

1.冒泡排序：
2.简单选择排序：
3.快速排序：
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

4.直接插入排序：
5.折半插入排序：
折半插入排序（binary insertion sort）是对插入排序算法的一种改进，在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为
a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。

代码：
6.希尔排序：。

Python理解折半插入排序引言插入排序中有直接插入排序，善于思考的能够发现该算法在进插入的时候是采用了顺序查找的方法，而在要查找的表中数据本身有序的前提下可以使用折半查找来代替顺序查找，这种排序的算法就是折半插入排序算法。

算法描述本篇文章描述的是折半插入排序算法，折半插入排序算法的原理就是利用折半查找的方法来查找插入的位置，然后直接将需要的数据插入该位置就可以了。

第一步：先将需要排序的序列中的第一个数据看成是一个有序序列。

第二步：从第二个元素开始，逐个进行插入。

第三步：在插入的时候先使用折半查找在有序序列中找到该数据应该插入的位置，比较该数据与有序序列中的中间值大小。

给定一个序列为a[0], a[1], a[2]……a[i-1], a[i], a[i+1]……a[n-1]。

假设前面i个元素已经是有序序列，现在将第i个元素插入其中，首先需要做的是找到插入元素的位置，然后再插入。

此时定义两个指针为low和high，low指向a[0],high指向a[i-1],使用折半查找，前面有序序列的中间值为a[mid]，mid=(low+high)/2,则前面序列为a[0], a[1], a[2]…a[mid]…a[i-1]。

将a[i]与a[mid]进行比较，若a[i]>a[mid] ，说明a[i]的位置就应该在mid和high之间，再在mid和high之间用相同方法进行查找。

若a[i]< a[mid], 说明a[i]的位置就应该在mid和low之间，再在mid和low之间用相同方法进行查找。

找到相应位置后就将该数据插入到该位置，这样就进行了一次折半插入排序。

例题：给定序列[5，2，6，0，9]，对其进行排序首先把5当成有序序列1.此时mid为5，将2与5做比较，2比5小，插在5前面则为[2，5， 6，0，9]2.将6先与2比较，再与6比较得[2，5， 6，0，9]3.将0先与5作比较，比5小，则位置在5左边，再与2比较，比2小，则再2左边。

折半插入排序
折半插入排序法，又称四舍五入排序法。

是按照折半法和插入法交替进行逐步排除错误的一种方法，也叫“舍弃小的，保留大的”或“用全排出去，用缺补上来”排序法.它适合于成对象形的数据，也就是说要求将某些对象先看作一组，然后再把它们每一对当作两个来排列，这样容易产生正确的结果。

常见的排序问题，通常包含多对对象，而且要求所选择的对象都必须有相同的特征值。

由于相邻的两个单元可能互为相反数，故在实际操作过程中往往需要将两者按互为倒数来处理，这就引申出一系列简便计算，即求整数部分的个位数字，因此排序也是很容易解决的。

下面举例说明其思路和方法。

例如有10名学生参加考试，前8人平均成绩为80分，最后2人平均成绩为90分，则求出平均成绩为81分的2人平均成绩的值。

应用该方法时要注意以下几点：1、运算符号、公式及各种运算之间不能混淆；2、在用这种方法时还需进一步分析原来顺序中有无矛盾，是否具备等价性（平均成绩相等），排除非同质的现象（比如全为80分，或全为90分）；3、用该方法解决的问题，只要求得到最终结果，不要求知道开始时的情况，但要求知道结束时的情况。

在用这种方法时还需进一步分析原来顺序中有无矛盾，是否具备等价性（平均成绩相等），排除非同质的现象（比如全为80分，或全为90分）。

3、使用了这种方法后，若遇到不能直接利用上述方法解决的问
题，可采取折半插入排序法。

例如，已知某班男女生人数分别为20人和21人，求男生人数占总人数的百分比。

4、用该方法解决的问题，只要求得到最终结果，不要求知道开始时的情况，但要求知道结束时的情况。

排序算法：折半插⼊排序算法分析：（1）时间复杂度 从时间上⽐较，折半查找⽐顺序查找快，所以就平均性能来说，折半插⼊排序优于直接插⼊排序。

折半插⼊排序所需要的关键字⽐较次数与待排序序列的初始排列⽆关，仅依赖于记录的个数。

不论初始序列情况如何，在插⼊第i个记录时，需要经过logi+1(向下取整+1)次⽐较，才能确定它插⼊的位置。

所以当记录的初始排列为正序或接近正序时，直接插⼊排序⽐折半插⼊排序执⾏的关键字⽐较次数要少。

折半插⼊排序的对象移动次数与直接插⼊排序相同，依赖于对象的初始排列。

在平均情况下，折半插⼊排序仅减少了关键字的⽐较次数，⽽记录的移动次数不变。

因此，折半插⼊排序的时间复杂度仍然为O（n^2）。

（2）空间复杂度 折半插⼊排序所需附加存储空间和直接插⼊排序相同，只需要⼀个记录的辅助空间r[0]，所以空间复杂度为O（1）算法特点：（1）是稳定排序。

（2）因为要进⾏折半插⼊查找，所以只能⽤于顺序结构，不能⽤于链式结构。

（3）适合初始记录⽆序、n较⼤的情况。

#include<iostream>#include<vector>using namespace std;void BSort(int a[],int n){for (int i = 1; i < n; i++)//数组中的第⼀个元素最为已经排好的序列，所以从数组的第⼆个元素开始排{int key = a[i];//带插⼊元素int low = 0, high = i - 1;while (low <= high){int mid = (low + high) / 2;if (key < a[mid]){high = mid - 1;}else{low = mid + 1;}}for (int j = i - 1; j >= high + 1; j--){//i-1是已经排好序的序列的数量，high+1是待插⼊的的位置，元素后移腾出high+1这个位置a[j + 1] = a[j];}a[high + 1] = key;}}int main(){int a [11] = { 2,6,4,5,54,53,53,5,34,34,32};BSort(a, 11);for (int i = 0; i < 11; i++){cout << a[i] << " ";}return 0;}。

详解折半插⼊排序算法折半插⼊排序算法的时间复杂度：O(nlogn)折半插⼊排序利⽤⼆分法的思想，在⼀个有序的序列中，找到新元素在该序列中的位置，然后插⼊。

如图1所⽰，共有n个元素，前i个元素已经是有序序列，现在要将第i个元素插⼊其中。

折半插⼊排序需要做两步⼯作：找到待插⼊元素的位置、插⼊。

图1 插⼊排序⽰意图⾸先要定义两个指针(不是语法⾥⾯的指针，是下标的意思)low和high⽤于寻找a[i]的插⼊位置，low指向a[0]，high指向a[i-1]，中点mid=(low+high)/2，图2 “折半”⽰意图如图2所⽰⼆分法的思想是，⽐较a[i]与a[mid]的⼤⼩，若a[i]>a[mid]，说明a[i]的位置应该在mid~high之间，将区间[low,high]缩短为[mid+1,high]，令指针low=mid+1；若a[i]<=a[mid]，说明a[i]的位置应该在low~mid之间，将区间压缩为[low,mid-1]，令指针high=mid-1。

每次折半之后，a[i]的位置应该在[low,high]之间。

如此循环，low与high渐渐靠近，直到low>high跳出循环，a[i]的位置找到，low即为a[i]应该放置的位置。

找到a[i]的位置之后进⾏插⼊，先将a[low]~a[i-1]这些元素向后平移⼀个元素的位置，然后将a[i]放到low位置。

⽤Dev-C++编写的C++代码：#include <iostream>using namespace std;void BinSort(int *a,int n) //对int数组进⾏从⼩到⼤的排序{for(int i=1;i<n;i++) //开始以a[0]作为有序序列，从a[1]开始找到当前元素a[i]应该放置的位置{int low=0,high = i-1,mid;//每次寻找a[i]的位置，都要更新这些数据while(low<=high) //⼆分思想循环寻找a[i]的位置{mid = (low+high) / 2;if(a[i]<=a[mid])high = mid - 1; //high指针减⼩elselow = mid + 1; //low指针增加} //循环结束，low就是a[i]应该放置的位置int temp = a[i];for(int j=i;j>low;j--) //将元素向后平移a[j] = a[j-1];a[low] = temp; //将元素temp = a[i] 放置到low位置}}int main() //举例说明{int n = 10;int a[10] = {5,8,9,4,7,5,6,3,1,11};BinSort(a,n);for(int i=0;i<n;i++)cout << a[i] << " ";cout << endl;return 0;}⼀个细节：为什么内层的循环while(low<=high){...}结束之后以low作为a[i]应该放置的位置?观察指针low与high重合之前与之后⼆者位置变化情况。

数据结构之排序---折半插⼊排序（时间复杂度O（nlog2n））排序Time Limit: 1000MS Memory limit: 32678K题⽬描述给你N(N<=100)个数,请你按照从⼩到⼤的顺序输出。

输⼊输⼊数据第⼀⾏是⼀个正整数N,第⼆⾏有N个整数。

输出输出⼀⾏，从⼩到⼤输出这N个数，中间⽤空格隔开。

⽰例输⼊51 4 32 5⽰例输出1 2 3 4 5#include <math.h>#include <string.h>#include <stdio.h>#include <iostream>#include <string>#include <algorithm>using namespace std;//折半插⼊排序void B_insertsort(int a[], int n){int i, j;int mid, low, high;for(i=2; i<=n; i++){a[0]=a[i]; //a[0] 只是我写的这个算法模板的“中转站”，实际数据存在下标: 1--->n ⾥⾯low=1; high=i-1;while(low <= high){mid = (low+high)/2;if(a[0]>a[mid]) // 此语句将决定是“由⼤到⼩” 还是 “由⼩到⼤”排序的顺序！low=mid+1;elsehigh=mid-1;}for(j=i-1; j>=high+1; j--){a[j+1]=a[j];}a[high+1]=a[0];}}int main(){int a[200];int i, j;int n;while(~scanf("%d", &n)){for(i=1; i<=n; i++){cin>>a[i];}B_insertsort(a, n);for(j=1; j<=n; j++){if(j==1)cout<<a[j];elsecout<<" "<<a[j]; }cout<<endl;}return 0;}。