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

StackOverflow https://stackoverflow.com/questions/17299

题

我正在尝试在 C/C++ 中构建一个函数来对数组进行排序，并用其“分数”或排名替换每个值。它接收一个指向整数数组的双指针数组，并根据整数的取消引用值对双指针进行排序。我已经尝试了好几次让它发挥作用，但无法将其放下。再次，它必须根据双指针指向的值对它们进行排序。这就是我所拥有的：

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.
        }
    }
  }
}
有帮助吗？

解决方案

你很接近了。交换时您正在引用数组项的地址，这是不必要的。数组中的项是指针，这就是需要交换的内容。

见下文：

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.
            }
        }
    }
}

另外，请查看 这篇关于冒泡排序的可爱博客文章 如果你感兴趣的话（对不起，无耻的插件:)）。希望对你的作业有帮助；）

编辑：请注意微妙的“优化”，您从数组长度开始倒数，并且仅递增直到内部循环中的“i”。这可以使您免于不必要地重新分析已排序的项目。

其他提示

呵呵，这不是作业。

如果是这样的话，那么考虑使用 STL 来管理数组和排序。它更容易开发和维护，并且 std::sort 算法比冒泡排序渐近更快。

你应该考虑使用 std::swap() 进行交换。如果您这样做，请这样称呼它：

swap( obj1, obj2 );

而不是：

std::swap( obj1, obj2 );

由于第一个调用语义将允许正确的命名空间查找来找到正确的重载（如果存在）。请务必具备：

using namespace std;

或者：

using std::swap;

某处。

嗯，我对 STL 没有太多经验。你能举个例子吗？

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

#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;
    }
}

完成 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;
}

数组的第一次打印将显示无序的地址。第二个，排序后，将显示排序的地址。在我的编译器上，我们有：

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

看一下 STL 的 <algorithm> 标头 http://www.cplusplus.com/reference/algorithm/您会发现很多实用程序。请注意，您还有其他更适合您的容器实现（std::list？std::地图？）。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top