修正桶排序

Question

代码运行良好，算法比插入排序快得多。我围绕HW中给出的参数构建了一个修改的桶排序，用50个迭代和40000个条目对一个ints向量进行排序。

由于是新的，而且不熟悉桶类，所以我还没有找到任何类似于此的代码示例。所以我的问题是关于我的风格和可能的优化空间。我如何简化这个算法？

void intVectSort2(vector<int> &V, int M)
   {
     // declare size for U and V
     int uSize = ((M * 2) + 1);
     int vectSize = V.size();

     // allocate memory for U array and initialize to zeros
     int *U = new int[uSize];
     for (int i = 0; i < uSize; i++)
       U[i] = 0;

     // step through M values and increment U when V is equal to M
     for (int j = 0; j < vectSize; j++)
       {
         int val = 0;
         int count = 0;
         int element = 0;
         int iterator = M;
         val = V[j];
         while (val != iterator)
           iterator--;
         element = iterator + M;
         count = U[element];
         count++;
         U[element] = count;
       }

     //load confirmed values in order back into V
     int index = 0;
     int currentSize = 0;
     for (int k = 0; k < uSize; k++)
       {
         int value = 0;
         int counter = 0;
         value = U[k];
         if (value != 0)
           {
             while (counter < value)
             counter++;
             currentSize += counter;
             for (index; index < currentSize; index++)
               V[index] = k - M;
           }
       }

     // free dynamic memory
     delete [] U;
   }

Answer 1

无意义环

有几个循环只会浪费时间：

while (val != iterator) iterator--;

该循环所做的工作与以下相同：

    iterator = val;

同样，这个循环：

while (counter < value) counter++;

与以下相同：

         counter = value;

方式太复杂了

填充桶的代码既混乱又复杂：

(int j= 0；j< vectSize；j++) { int val = 0；int计数= 0；int元素= 0；int迭代器= M；val = VJ；while (val !=迭代器)迭代器--；element =迭代器+ M；count = U元素；count++；U元素 = count；}

它实际上应该是一个单行循环：

for (int j = 0; j < vectSize; j++) {
    U[V[j]]++
}

请注意，这在范围0.m中使用桶，而您在范围M.2m中使用桶，没有充分的理由。

同样，可以将桶解压循环简化为：

int index = 0;
for (int i = 0; i <= M; i++) {
    for (int j = 0; j < U[i]; j++) {
        V[index++] = i;
    }
}

这假设您分配了U来保存M+1元素，以便允许在0..M范围内的值。