如何根据指向的值对双指针数组进行排序？

I am trying to build a function in C/C++ to sort an array and replace each value with its "score" or rank. It takes in a double pointer array to an array of ints, and sorts the double pointers based on the dereferenced value of the integers. I have tried quite a few times to make it work, but can't get it down. Once again, it must sort the double pointers based on the values they point to. This is what I have:

我试图在C / C ++中构建一个函数来对数组进行排序,并用它的“得分”或排名替换每个值。它将一个双指针数组接收到一个int数组,并根据整数的解引用值对双指针进行排序。我已经尝试过很多次才能使它工作,但不能让它失效。它必须再次根据它们指向的值对双指针进行排序。这就是我所拥有的:

void SortArray( int ** pArray, int ArrayLength )
{
  int i, j, flag = 1;     // set flag to 1 to begin initial pass
  int * temp;             // holding variable orig with no *
  for(i = 1; (i <= ArrayLength) && flag; i++)
  {
    flag = 0;
    for (j = 0; j < (ArrayLength -1); j++)
    {
        if (*pArray[j+1] > *pArray[j])    // ascending order simply changes to <
        { 
            temp = &pArray[j];            // swap elements
            pArray[j] = &pArray[j+1];
            pArray[j+1] = &temp;
            flag = 1;                     // indicates that a swap occurred.
        }
    }
  }
}

5 个解决方案

#1

You're close. You're referencing the address of the array items when you swap, which isn't necessary. The items in the array are pointers, and that's what needs to be swapped.

你很亲密您在交换时引用了数组项的地址,这是不必要的。数组中的项是指针,这是需要交换的内容。

See below:

void SortArray( int ** pArray, int ArrayLength )
{
    int i, j, flag = 1;    // set flag to 1 to begin initial pass
    int * temp;             // holding variable orig with no *
    for(i = ArrayLength - 1; i > 0 && flag; i--)
    {
        flag = 0;
        for (j = 0; j < i; j++)
        {
            if (*pArray[j] > *pArray[j+1])      // ascending order simply changes to <
            { 
                temp = pArray[j];             // swap elements
                pArray[j] = pArray[j+1];
                pArray[j+1] = temp;
                flag = 1;               // indicates that a swap occurred.
            }
        }
    }
}

Also, check out this lovely blog post on Bubble Sorting in case you're interested (sorry, shameless plug :)). Hope that helps you with your homework ;)

另外,如果你感兴趣的话,请查看这篇关于Bubble Sorting的可爱博客文章(对不起,无耻的插件:))。希望能帮助你完成作业;)

Edit: Note the subtle "optimisation" where you count back from the array length and only increment up until 'i' in the inner loop. This saves you from needlessly reparsing items that have already been sorted.

编辑:请注意细微的“优化”,您可以从数组长度开始向后计数,直到内循环中的“i”为止。这样可以避免不必要地重新排序已经排序的项目。

#2

Heh, this isnt homework.

嘿,这不是功课。

If thats the case then consider using the STL to manage arrays and sort. Its easier to develop and maintain and the std::sort algorithm is asymptotically faster than bubble sort.

如果是这种情况,那么考虑使用STL来管理数组和排序。它更易于开发和维护,并且std :: sort算法渐渐比冒泡排序更快。

#3

You should consider using std::swap() to do your swapping. If you do, call it as such:

您应该考虑使用std :: swap()进行交换。如果您这样做,请将其称为:

swap( obj1, obj2 );

rather than:

std::swap( obj1, obj2 );

As the first calling semantic will allow the proper namespace lookup to find the correct overload if one exists. Be sure to have either:

因为第一个调用语义将允许正确的命名空间查找以找到正确的重载(如果存在)。一定要有:

using namespace std;

or:

using std::swap;

somewhere.

#4

Hmm, I don't have much experience with the STL. Could you give an example?

嗯,我对STL没有多少经验。你举个例子吗?

This program creates a vector of ints, sorts it, and displays the results.

该程序创建一个int向量,对其进行排序,并显示结果。

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
    vector<int>; vec;
    vec.push_back(7);
    vec.push_back(5);
    vec.push_back(13);
    sort(vec.begin(), vec.end());

    for (vector<int>::size_type i = 0; i < vec.size(); ++i)
    {
        cout << vec[i] << endl;
    }
}

#5

To complete Brian Ensink's post, you'll find the STL full of surprises. For example, the std::sort algorithm:

要完成Brian Ensink的帖子,你会发现STL充满惊喜。例如,std :: sort算法:

#include <iostream>
#include <vector>
#include <algorithm>

void printArray(const std::vector<int *> & p_aInt)
{
   for(std::vector<int *>::size_type i = 0, iMax = p_aInt.size(); i < iMax; ++i)
   {
      std::cout << "i[" << static_cast<int>(i) << "] = " << reinterpret_cast<unsigned     int>(p_aInt[i]) << std::endl ;
   }

   std::cout << std::endl ;
}


int main(int argc, char **argv)
{
   int a = 1 ;
   int b = 2 ;
   int c = 3 ;
   int d = 4 ;
   int e = 5 ;

   std::vector<int *> aInt ;

   // We fill the vector with variables in an unordered way
   aInt.push_back(&c) ;
   aInt.push_back(&b) ;
   aInt.push_back(&e) ;
   aInt.push_back(&d) ;
   aInt.push_back(&a) ;

   printArray(aInt) ; // We see the addresses are NOT ordered
   std::sort(aInt.begin(), aInt.end()) ; // DO THE SORTING
   printArray(aInt) ; // We see the addresses are ORDERED

   return EXIT_SUCCESS;
}

The first printing of the array will show unordered addresses. The second, after the sort, will show ordered adresses. On my compiler, we have:

阵列的第一次打印将显示无序地址。排序后的第二个将显示有序的地址。在我的编译器上,我们有:

i[0] = 3216087168
i[1] = 3216087172
i[2] = 3216087160
i[3] = 3216087164
i[4] = 3216087176

i[0] = 3216087160
i[1] = 3216087164
i[2] = 3216087168
i[3] = 3216087172
i[4] = 3216087176

Give STL's <algorithm> header a look http://www.cplusplus.com/reference/algorithm/ You'll find a lot of utilities. Note that you have other implementation of containers that could suit you better (std::list? std::map?).

给STL的标题看看http://www.cplusplus.com/reference/algorithm/你会发现很多实用程序。请注意,您有其他更适合您的容器实现(std :: list?std :: map?)。

#1