[蓝桥省题](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不动会是什么场景？

从上可以得知，如果只移动mod的话，那么程序则正常运行。

那么，这道题的答案就是mod++

教学视频如下所示：

本文链接：

https://nullcode.fun/95.html