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

Question

我想在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. 
     } 
    } 
    } 
} 

Answer 1

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

见下文：

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

此外，检查出this lovely blog post on Bubble Sorting的情况下，你有兴趣（对不起，无耻插头:)）。希望可以帮助你做作业;）

---

编辑：请注意，你指望从数组长度后面只有等到“我”在内环增加了微妙的“优化”。这可以避免不必要地重新分析已排序的项目。

Answer 2

嘿，这不是作业。

如果是这种情况，那么考虑使用STL来管理数组和排序。它更容易开发和维护，而std :: sort算法比气泡排序渐近地快。

Answer 3

您应该考虑使用std::swap()进行交换。如果你这样做，把它作为这样的：

swap(obj1, obj2); 

而不是：

std::swap(obj1, obj2); 

作为第一通话语义将允许适当的名称空间查询，找到正确的过载（如果存在）。一定要有两种：

using namespace std; 

或：

using std::swap; 

地方。

Answer 4

嗯，我没有太多的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; 
    } 
} 

Answer 5

要完成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的<算法>头一看http://www.cplusplus.com/reference/algorithm/ 你会发现很多的工具。请注意，您还有其他可以更适合您的容器的实现（std :: list？std :: map？）。