折半插入排序

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当两个元素出现逆序的时候就交换位置，这种排序方法称为（）。