[蓝桥省题](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的数放到中间,如下图示:

img

思路:由于是代码填空题,我们首先应将题目给出的代码复制到编译器下,看看有没有语法错误,然后再根据代码的解读对需要填空的地方填空。

我们可以看到,题目一开始将mod、left两指针分别指向头端,而right则指向尾端,分了三个情况处理,其中前两个情况如下:

  • 当mod所指的元素小于0时,将mod与left交换位置

    • mod与left全部右移
  • 当mod所指的元素大于0时,需将mod与right交换位置

    • mod不变,right向左移动

从上述我们可以得知,题目的意思就是让我们对mod==0时作操作,我们拿上面的数组来演示以下

img

img

好,此时问题来了

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++

教学视频如下所示:

本文链接:

https://nullcode.fun/95.html
1 + 5 =
快来做第一个评论的人吧~