[蓝桥省题](C2013_6) 三部排序
6、(三部排序)一般的排序又许多经典算法,如快速排序,希尔排序等
但实际应用时,经常会或多或少又一些特殊的要求,我们没必要套用那些经典算法,可以根据实际情况建立更好的解法
比如,对一个整型数组中的数字进行分类排序:
使得负整数都靠左端,正数都靠右端,0在中部,注意问题的特点是:负数区域和正数区域内并不要求有序
以下的程序实现了该目标。
其中x指向带排序的整型数组,len是数组的长度,代码如下:
void sort3p(int* x, int len)
{
int mod = 0;
int left = 0;
int right = len - 1;
while (mod <= right)
{
if (x[mod] < 0)
{
int t = x[left];
x[left] = x[mod];
x[mod] = t;
left++;
mod++;
}
else if (x[mod] > 0)
{
int t = x[right];
x[right] = x[mod];
x[mod] = t;
right--;
}
else
{
-----------------------------------//填空位置
}
}
}
题意:如上述,这是一道代码填空题,它应该属于快速排序的一个变种,三个指针,要将小于0的数放到左边,大于0的数放到右边,等于0的数放到中间,如下图示:
思路:由于是代码填空题,我们首先应将题目给出的代码复制到编译器下,看看有没有语法错误,然后再根据代码的解读对需要填空的地方填空。
我们可以看到,题目一开始将mod、left两指针分别指向头端,而right则指向尾端,分了三个情况处理,其中前两个情况如下:
当mod所指的元素小于0时,将mod与left交换位置
- mod与left全部右移
当mod所指的元素大于0时,需将mod与right交换位置
- mod不变,right向左移动
从上述我们可以得知,题目的意思就是让我们对mod==0时作操作,我们拿上面的数组来演示以下
好,此时问题来了
mod和left要等于0怎么办?我们可以知道,0要放到中间,那么肯定不能移动right指针,我们再看看给定条件:小于0时,交换mod和left并且,两指针后移
那么这肯定是等于0的一个突破口,我们现在来考虑再等于0时,是移动mod还是移动left?
从判断条件我们可以知道,如果移动left,那么将永远不会进入判断条件,因为判断是对mod做判断的!
然后在mod小于0时,程序才会对mod与left与right和mod之间做交换。
那么移动mod?让left不动会是什么场景?
<video controls="" src="https://axuannote-1304271763.cos.ap-nanjing.myqcloud.com/%E4%B8%89%E9%83%A8%E6%8E%92%E5%BA%8F~1.mp4"></video>
从上可以得知,如果只移动mod的话,那么程序则正常运行。
那么,这道题的答案就是mod++
教学视频如下所示: