0

我目前正在编写快速排序算法的实现，并且我有一个效率问题，特别是关于对数组进行分区。我在排序之前对数组进行分区的方式涉及选择枢轴或分区元素作为数组中的第一个元素（我知道。这不是最有效的方法），然后设置两个变量 - “高”和“低” - 分别是数组的最后一个索引和第一个索引。我有一个 while 循环设置，它通过切换某些元素并递增和递减低和高直到它们相等来对数组进行分区。

我的问题是我正在使用 switch 语句来控制要移动的索引，而不是设置两个单独的 while 循环来执行此操作。在这种情况下使用 switch 语句是否更有效？

以下是相关代码：

    //used to determine which side of the array to move the element to
    #define RIGHT 1
    #define LEFT 0

    void partition( int nums[], int size )
    {
         int pivot = nums[0], low = 0, high = size - 1, turn = LEFT;

         while ( low != high )
         {

             switch (turn)
             {
                case RIGHT:
                     if ( nums[low] >= pivot )
                     {
                         nums[high] = nums[low];
                         high--;
                         turn = LEFT;
                     }
                     else
                         low++;
                     break;

                case LEFT:
                     if ( nums[high] <= pivot )
                     {
                         nums[low] = nums[high];
                         low++;
                         turn = RIGHT;
                     }
                     else
                         high--;
                     break;
            }
        }

        nums[low] = pivot;
     }
4

2 回答 2

1

如果不进行实际测试，您将无法知道。编译器有时可以做一些令人惊奇的事情（无论好坏都令人惊讶）。一般来说，我希望它更快地转移到两个循环，因为状态保存在程序计数器中，但编译器可能会这样做或更好。它也会随着编译时的优化设置而变化。

于 2013-01-22T05:12:56.163 回答
1

我的猜测是两个循环，但测量

通常最好将不变表达式从循环中向外移动。这种优化称为代码提升。或循环不变的代码运动。 它获胜的原因很明显。现在，在您的情况下，编译器不清楚什么是不变的，但您知道turn变量的变体比low和high少。

所以，我的猜测是两个循环更好，但唯一确定的方法是测量它。

于 2013-01-22T05:21:54.863 回答