排序——折半（二分）插入排序

野性酷女 2022-09-10 05:26 203阅读 0赞

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASeKAmG0gSmll_size_20_color_FFFFFF_t_70_g_se_x_16]

**基本思想**

折半插入排序，又称二分插入排序，先用折半查找1找到应该插入的位置，再移动元素

**步骤（从小到大排序）**

1.  找到没有排序的元素
2.  标记元素
3.  对前面排好序的元素进行折半，low、high 上下界，mid标记为中间的元素
4.  将标记元素与 mid 位置上的元素进行比较，如果标记元素<mid 位置上的元素，则应该插入到mid 的左边，high=mid-1；如果标记元素>mid 位置上的元素，则应该插入到 mid 的右边，low=mid+1。重复第3步
5.  当 low>high 时停止折半查找，将\[low，i-1\]内的元素全部右移，并将标记元素插入到 low 所指的位置

**算法代码**

#include <iostream>
    using namespace std;
    
    //折半（二分）插入排序算法(设置 nums[0] 为哨兵暂存标记元素)
    void InsertSort(int nums[],int n){
    	int i,j,low,high,mid;
    	for(i=2;i<n;i++){
    		if(nums[i]<nums[i-1]){				//若 nums[i]<nums[i-1] 即当前项比前一项小 
    			nums[0]=nums[i];				//nums[0] 暂存 nums[i] 
    			low=1,high=i-1;					//low、high用于标记已排好序列的上下界 
    			while(low<=high){				//查找标记元素要插入的位置 
    				mid=(low+high)/2;			//mid 指向已排序区间的中间位置
    				if(nums[mid]>nums[0]){      
    					high=mid-1;				//插入元素应在左子区间
    				}else{
    					low=mid+1;				//插入元素应在右子区间
    				}
    			}					
    			for(j=i;j>low;j--){ 
    				nums[j]=nums[j-1];			//将[low,i-1]的元素全部右移 
    			}
    			nums[low]=nums[0];				//将 nums[0] 插入到下标为 low 的位置 
    		}
    	}
    }
    
    //打印数组 
    void printNum(int numbers[],int n){
    	for(int i=1;i<n;i++){
    		cout<<numbers[i]<<" ";
    	}
    }
    
    int main()
    {
    	int numbers[13]={0,3,44,5,44,47,15,36,26,27,2,99,1};
    	int n=sizeof(numbers)/sizeof(numbers[0]);	//数组长度 
    	InsertSort(numbers,n);		//调用 InsertSort 函数进行插入排序 
    	printNum(numbers,n);		//打印数组 
        return 0;
    }

**算法性能分析**

*  空间复杂度： O ( 1 ) O(1) O(1)
 *  时间复杂度： O ( n 2 ) O(n^2) O(n2)
 *  算法稳定性2：稳定

--------------------

1.  二分查找的基本思想是将  n n n 个元素分成大致相等的两部分，取  a \[ n 2 \] a\\left \[ \\frac\{n\}\{2\}\\right \] a\[2n\] 与  x x x 做比较，如果 x = a \[ n 2 \] x=a\\left \[ \\frac\{n\}\{2\}\\right \] x=a\[2n\]，则找到  x x x，算法中止；如果 x < a \[ n 2 \] x<a\\left \[ \\frac\{n\}\{2\}\\right \] x<a\[2n\]，则只要在数组  a a a 的左半部分继续搜索  x x x，如果 x > a \[ n 2 \] x>a\\left \[ \\frac\{n\}\{2\}\\right \] x>a\[2n\] 则只要在数组  a a a 的右半部搜索  x x x。 ↩︎
2.  算法的稳定性：若待排序表中有两个元素  R i R\_i Ri 和  R j R\_j Rj，其对应的关键字相同即  k e y i = k e y j key\_i = key\_j keyi=keyj，且在排序前  R i R\_i Ri 在  R j R\_j Rj 的前面，若使用某一排序算法排序后，  R i R\_i Ri 仍在  R j R\_j Rj 的前面，则称这个排序算法是**稳定**的，否则称排序算法是**不稳定**的。 ↩︎

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASeKAmG0gSmll_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/1c4d59f73d104115bc7e3895f12b5f1b.png