数据结构与算法基础（王卓）（35）：交换排序之快排【第一阶段：第一遍遍历】网站首页 技术杂谈

void 遍历一遍(SqList L)
{
    int low, high;
    L.r[0] = L.r[1];
    low = 1;
    high = L.length;
    while (low < high)
    {
        if (L.r[high].key < L.r[0].key)
        {
            L.r[low] = L.r[high];
            low++;
        }
        if (L.r[0].key < L.r[low].key)
        {
            L.r[high] = L.r[low];
            high--;
        }
    }
}

通过看视频操作我们发现，我们这里写的程序存在一定的

问题：

在我们写的程序语句里：

当元素不需要移动的时候，我们对程序没有进行任何操作

这样当程序出现不需要移动的元素的时候，我们的程序就开始停滞不前

甚至当low和high都出现该种情况的时候，程序会直接进入死循环停止

Project 2:

void 遍历一遍(SqList L)
{
    int low, high;
    L.r[0] = L.r[1];
    low = 1;
    high = L.length;
    while (low < high)
    {
        if (L.r[high].key < L.r[0].key)
            L.r[low] = L.r[high];
        low++;
        if (L.r[0].key < L.r[low].key)
            L.r[high] = L.r[low];
        high--;
    }
}

问题：

但是其实我们这样改/把程序改成这样也不对，在我们写的程序语句里：

当我们对元素进行移动了以后

我们还要去进行移动low和high指针的操作

这样我们后面下一个要（需要）移动的元素

就没办法插入到空格（空着）的元素里面了

Project 3:

void 遍历一遍(SqList L)
{
    int low, high;
    L.r[0] = L.r[1];
    low = 1;
    high = L.length;
    while (low < high)
    {
        if (L.r[high].key < L.r[0].key)
            L.r[low] = L.r[high];
        else
            low++;
        if (L.r[0].key < L.r[low].key)
            L.r[high] = L.r[low];
        else
            high--;
    }
}

问题：

在这里，我们对程序的更改未免有点矫枉过正了

实际上，因为我们对程序执行的流程不清晰，导致了我们的思维混乱

结果我们对程序的修改越改越错：

当程序指向的元素需要移动时，移动完以后：

原来该元素的指针不用动（作为下一轮指向空格元素的指针）

if (L.r[high].key < L.r[0].key)：

high不动

if (L.r[0].key < L.r[low].key)：

low不动

然后：

该元素移动到的位置的指针需要移动，我接下来总不能是来比较你这个上一轮刚刚移动的元素吧：

if (L.r[high].key < L.r[0].key)：

low++

if (L.r[0].key < L.r[low].key)：

high--

Project 4:

void 遍历一遍(SqList L)
{
    int low, high;
    L.r[0] = L.r[1];
    low = 1;
    high = L.length;
    while (low < high)
    {
        if (L.r[high].key < L.r[0].key)
        {
            L.r[low] = L.r[high];
            low++;
        }
        else
            high--;
        if (L.r[0].key < L.r[low].key)
        {
            L.r[high] = L.r[low];
            high--;
        }
        else
            low++;
    }
}

Project 5:

另外，我们对于这个程序算法还缺少最后一步操作：把哨兵重新放到中间去

void 遍历一遍(SqList L)
{
    int low, high;
    L.r[0] = L.r[1];
    low = 1;
    high = L.length;
    while (low < high)
    {
        if (L.r[high].key < L.r[0].key)
        {
            L.r[low] = L.r[high];
            low++;
        }
        else
            high--;
        if (L.r[0].key < L.r[low].key)
        {
            L.r[high] = L.r[low];
            high--;
        }
        else
            low++;
    }
    L.r[low] = L.r[high] = L.r[0];
}

OK，实际上这里我还是预留了一个小彩蛋给大家的，感兴趣的话可以看一看下一篇日记哦

哈哈，实际上你们必须得看、不得不看，因为这里我们写的语句虽然没错，但也不完全对，哈哈

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。