递归排序数组（图文讲解）

短命女 2023-07-10 15:32 35阅读 0赞

# 递归排序数组 #

**题目要求**  
计划输入一组乱序数组给递归函数，然后输出排好序的数组（从小到大）。

题中要求用递归来给数组排序，所以我们可以通过次递归函数排一个的情况，将每个数排到相应位置上。对这个问题，我给出了两个方案。

**方案一：前排法**  
将要排序的元素下标和值都先保存下来，然后再向“前面”和其他元素比较。  
![未排序数组][20200303151958940.png]  
首先由于递归函数的调用，k不断“-1”，最后到k==1的时候停止，然后开始回到“上一个”递归函数，开始第二个元素排序。  
![第二个元素排序][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]  
第二个元素排序  
我们可以想象将第一个元素“拿出来”，与第一个元素比较，如果temp比arr\[index\]大的话则放回原位，否则与第一个元素交换。  
![第三个元素排序][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 1]  
![排序][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 2]  
第三个元素排序出现了前面比后面大的情况。当第二个元素（6）大于temp（3）时，第二个元素成为第三个元素。  
![排序成功][20200303154837102.png]  
temp要与第一个元素相比较，大于第一个元素则，temp成为了第二个元素，排序成功。  
接下来步骤都相似，我就不再这里一一列举了（若想加深理解，可以看看后排法，图文更加详细、清晰）。

//递归排序数组
    #include<bits/stdc++.h>
    using namespace std;
    void f(int *arr, int k)
    { 
    	if(k==1) return;
    	f(arr, k-1);
    	int temp=arr[k];
    	int index=k-1;
    	while(index>0&&temp<arr[index])
    	{ 
    		arr[index+1]=arr[index];
    		index--;
    	}
    	arr[index+1]=temp;
    }
    int main()
    { 
    	int arr[5]={ 1,6,3,4,5};
    	f(arr,4);
    	for(int i=0; i<5; i++)
    	{ 
    		cout<<arr[i]<<" ";
    	}
    	return 0;
    }

**方案二：后排法**  
后排法和前排法异曲同工，只是将排序起点改为从最后一个元素开始，为了让更好理解递归，而不是单单解题，我建议可以对一道递归题，写出不同的递归函数，最后我再献上讲解图。  
![比较][20200303155733479.png]  
与前排法相似，我们一开始将倒数第二个元素与倒数第一个元素作比较。我们可以看到temp<5排序不变，接下来3<4排序也不变。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 3]  
当k=1时，我们发现temp=6大于k+1元素，于是我们就要向后比较。  
将3放到第k个元素位置，将temp与k+2元素比较。我们发现temp还是大于k+2元素，于是我们就要向后比较。将4放到第k+1元素位置，将temp与k+3元素比较。我们又发现temp还是大于k+3元素，于是我们就要向后比较。将4放到第k+1元素位置，将temp与k+3元素比较。  
![不断比较][2020030316082695.png]  
可是已经没有元素能再比较了，所以此时的temp也就是6，是数组中最大的元素，放在最末尾。最后我们比较第k个元素与第k+1个元素。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 4]  
1<3，得知排序不改变。  
![排序成功][20200303161627672.png]

//后排法
    #include<bits/stdc++.h>
    using namespace std;
    void f(int *arr, int k)
    { 
    	if(k==4) return;
    	f(arr, k+1);
    	int temp=arr[k];
    	int index=k+1;
    	while(index<5&&temp>arr[index])
    	{ 
    		arr[index-1]=arr[index];
    		index++;
    	}
    	arr[index-1]=temp;
    }
    int main()
    { 
    	int arr[5]={ 1,6,3,4,5};
    	f(arr,0);
    	for(int i=0; i<5; i++)
    	{ 
    		cout<<arr[i]<<" ";
    	}
    	return 0;
    }

希望能够将自己的一些学习经验分享给有需要的人。  
我是小郑，一个坚持不懈的小白。

[20200303151958940.png]: https://img-blog.csdnimg.cn/20200303151958940.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200303153652977.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200303153959579.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200303154516210.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[20200303154837102.png]: https://img-blog.csdnimg.cn/20200303154837102.png
[20200303155733479.png]: https://img-blog.csdnimg.cn/20200303155733479.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200303160057846.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[2020030316082695.png]: https://img-blog.csdnimg.cn/2020030316082695.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200303161222882.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70
[20200303161627672.png]: https://img-blog.csdnimg.cn/20200303161627672.png