基础算法题——求自定类型元素序列的中位数（插入排序、希尔排序）

约定不等于承诺〃 2022-12-20 03:22 128阅读 0赞

### [求自定类型元素序列的中位数][Link 1] ###

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]  
![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 1]  
![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 2]  
插入排序会超时，希尔排序可通过全部样例。

### 解决方案：插入排序 ###

#### [参考博客——插入排序][Link 2] ####

引入插入排序参考博客的思想：插入排序的工作方式非常像人们排序一手扑克牌一样。  
开始时，我们的左手为空并且桌子上的牌面朝下。我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中牌进行比较，如果有大于手中的牌则插入该牌的后面。接着摸桌子上的牌，继续重复上述步骤，如下图所示：  
![排序][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 3]  
（用上述的扑克牌排序习惯模拟插入排序可谓十分形象）

ElementType Median(ElementType A[], int N){ 
    	//InsertionSort()
    	for(int i=1; i<N; i++){ 
    		ElementType tmp=A[i];
    		for(int j=i; j>=0; j--){ 
    			if(tmp<A[j-1])
    				A[j]=A[j-1];
    			else{ 
    				A[j]=tmp;
    				break;
    			}
    		}
    	}
    	
    	return A[N/2];
    }

![结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 4]

### 解决方案：希尔排序 ###

希尔排序与插入排序类似，更准确地说是一种高效的插入排序。  
插入排序在相对有序的数列中的效率最高，而希尔排序就是将无序的数列转换为相对有序的数列，再转换为无序数列。

ElementType Median( ElementType A[], int N ){ 
    	float temp;
    	//每组两个、四个、八个... 
    	for(int gap=N/2; gap>0; gap=gap/2)
    	for(int i=gap; i<N; i++)
    	for(int j=i-gap; j>=0&&A[j]>A[j+gap]; j=j-gap){ 
    		temp = A[j];
    		A[j] = A[j+gap];
    		A[j+gap] = temp;
    	}
    		
    	return A[N/2];//返回中间元素
    }

![结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 5]

[Link 1]: https://pintia.cn/problem-sets/14/problems/743
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/071e8ca3bab344fea2781a7fc38b45f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/b358bb7aa31c4813abea78863cd14ecf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/b89db7b1d8394295a2a9ab473d565ec8.png
[Link 2]: https://blog.csdn.net/zxm317122667/article/details/83344178?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160499187919725225065483%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=160499187919725225065483&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-2-83344178.pc_first_rank_v2_rank_v28p&utm_term=%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F&spm=1018.2118.3001.4449
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/49b4f21b1d68475cb517584904efd48a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/5453ebf6e269496c86f966d66a7fac2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221120/02a5f8b07fde4182911ea902b0f62701.png