快速排序实现

Question

你好，我对C++很陌生，一直在钻研搜索和排序算法，并决定尝试编写自己的算法。这是我的原型：

void quicksort(int data[ ], size_t n);
// Precondition: data is an array with at least n components.
// Postcondition: The elements of data have been rearranged so
// that data[0] <= data[1] <= ... <= data[n-1].

void partition(int data[ ], size_t n, size_t& pivot_index);
// Precondition: n > 1, and data is an array (or subarray)
// with at least n elements.
// Postcondition: The function has selected some "pivot value"
// that occurs in data[0]..data[n-1]. The elements of data
// have then been rearranged, and the pivot index set so that:
//   -- data[pivot_index] is equal to the pivot;
//   -- Each item before data[pivot_index] is <= the pivot;
//   -- Each item after data[pivot_index] is > the pivot.

void setPivot(int data[ ], size_t n);
// Precondition: n > 1 and data is an array or subarray
// Postcondition: data[0] holds the selected pivot value
//  The original value of data[0] has been swapped with the selected pivot value

我写了我的main测试：

int main( )
{
    // Announce the program
    cout << "\nImplementing the QuickSort Algorithm\n";
    // Declare useful values
    const char BLANK = ' ';
    size_t i = 0;
    // Initialize our test data arrays
    const size_t SIZE1 = 10;
    int data1[]= {34, 33, 9, 45, 1, -1, 9, -18, 75, 100 };
    const size_t SIZE2 = 15;  // Number of elements in the array to be sorted
    int data2[]= {100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86 };
    const size_t SIZE3 = 1000;
    int data3[SIZE3];
    // Initialize the third array to random int values
    for (i = 0; i < SIZE3; i++)
        data3[i] = rand();
    // Beginning of quick sort tests
    // Sort the arrays and print the result with two blanks after each number
    quicksort(data1, SIZE1);
    cout << "\nSorted First Array: " << endl;
    for (i = 0; i < SIZE1; i++)
        cout << data1[i] << BLANK << BLANK;
    cout << endl;
    quicksort(data2, SIZE2);
    cout << "\nSorted Second Array: " << endl;
    for (i = 0; i < SIZE2; i++)
        cout << data2[i] << BLANK << BLANK;
    cout << endl;
    // On the large third array, just print the first ten and last ten values
    quicksort(data3, SIZE3);
    cout << "\nSorted Third Array (first ten): " << endl;
    for (i = 0; i < 10; i++)
        cout << data3[i] << BLANK << BLANK;
    cout << endl;
    cout << "Sorted Third Array (last ten): " << endl;
    for (i = SIZE3 - 10; i < SIZE3; i++)
        cout << data3[i] << BLANK << BLANK;
    cout << endl << endl;
    system("Pause");
    return EXIT_SUCCESS;
}

我已经开始了函数定义：

void quicksort(int data[ ], size_t n)
// Library facilities used: cstdlib
{
    size_t pivot_index; // Array index for the pivot element
    size_t n1;          // Number of elements before the pivot element
    size_t n2;          // Number of elements after the pivot element

    if (n > 1)
    {
        // Partition the array, and set the pivot index.
        partition(data, n, pivot_index);

        // Compute the sizes of the subarrays.
        n1 = pivot_index;
        n2 = n - n1 - 1;

        // Recursive calls will now sort the subarrays.
        quicksort(data, n1);
        quicksort((data + pivot_index + 1), n2);
    }
}

void partition(int data[ ], size_t n, size_t& pivot_index)
// Library facilities used: algorithm, cstdlib
{
    assert(n > 1);
    setPivot(data, n);
}

void setPivot(int data[ ], size_t n)
// Library facilties used: algorithm, cstdlib
// This function chooses a pivot value as the median of three
// randomly selected values.  The selected pivot is swapped with
// data[0] so that the pivot value is in the first position of the array
{
    assert(n > 1);

}

我的问题是，在速度方面，完成void partition(int data[], size_t n, size_t& pivot_index和void setPivot(int data[], size_t n)的最佳方式是什么？

Answer 1

这是一个很难回答的问题，我喜欢你双脚跳进去。因此，在构造编译器时，您可以根据一条指令相对于另一条指令所用的时间单位来选择指令。虽然您可以使用Raymond的建议，只使用预构造的代码，但是您不会从中学到多少东西。比较排序算法中最昂贵的两个指令是数组中的比较和交换，因此您希望将它们最小化。

我将首先讨论一个好的分区算法背后的数学问题。让我们假设支点在数据中，并考虑将这些昂贵的掉期最小化的最佳方法。用数组..。

   [34, 33, 9, 45, 1, -1, 9, -18, 75, 100]

一个好的分区将减少我们移动枢轴的次数，因为我们不能最小化我们移动某个地方的次数(如果可以的话，我们不会排序)。

wall:=1
for(i:=1; i < n; ++i){
   if(data[0]>data[i]){
      swap(data, wall, i)
      ++wall
   }
}

swap(data, wall-1, 0)
pivot_index:=wall-1

所以现在来回答为什么这是最有效的方法之一。

1. 它减少了昂贵的掉期的数量。
2. 它最大限度地减少了增加的数量。
3. 它确实使用的是++，它将100%转换为INC %reg程序集指令，这比将1添加到没有保证的寄存器中要快(.但最有可能的是)。((做这件事真的很学究)

接下来是选择枢轴的明智方法。在评论中，它写着中位数，但出于统计原因，我要改变它的意思，坚持选择三个随机数。Quick的运行时复杂性完全取决于支点的选择。选择错误，可能是O(n^2)，选择正确，它将近似于O(n*log(n))。枢轴的最佳选择是将数组均匀地分成两段等长的数字。50%的数据点比枢轴高，50%在以下，e.i。卑鄙的人。计算人口的平均值将是缓慢的，如果我们必须计算平均每一步的方法，那么我们将只使用样本的平均值来估计人口的平均值，从而破坏我们所得到的任何性能。

void setPivot(int data[ ], size_t n)

   index1:= rand_uniform()*n
   index2:= rand_uniform()*n
   index3:= rand_uniform()*n

   mean:=(data[index1]+data[index2]+data[index3])/3

   offset1:=abs(index1-mean)
   offset2:=abs(index2-mean)
   offset3:=abs(index3-mean)

   if(offset1 < offset2 && offset1 < offset3)
       swap(data,0,index1)
   else if(offset2 < offset1 && offset2 < offset3)
       swap(data,0,index2)
   else if(offset3 < offset1 && offset3 < offset2)
       swap(data,0,index3)

显然，这样做有很大的开销，但是setPivot具有恒定的时间复杂度，这意味着对于足够大的n，这样做更快，因为所选的piviot在统计上更多地将数据分成两个相等的部分，这是一个好的分治算法的全部要点。