C++中的指针数组排序算法

Question

希望我能得到一些有关我编写的排序方法的建议。

这只是我正在制作的另一个程序的测试，但是这个测试有一个我无法解决的错误。这段代码的目的是创建一个 int 指针数组，并通过常规 int 数组的内容对该数组中的指针进行排序。

我的第二个 for 循环存在问题，它不允许我使用 j!=-1，因此无法对数组的第一个元素进行排序。请帮忙。谢谢！

 //create array
 int c[8] = {3,1,5,7,8,2,6,4};
 //create pointer array
 int *newptr[8];
 for(int k = 0; k<8; k++)
 {
     newptr[k] = &c[k];
 }
//sort pointer array
for(int j = 0; j<8; j++)
{
    cout << "test1\n\n";
    cout << *newptr[j] << "and" << *newptr[j+1];
    for(;*newptr[j] < *newptr[j+1] && j!=0; j--) 
    //using j!=-1 doesn't work which causes me to not be able to sort the first element
    //in the array properly
    {
        cout<< "test2";
        int *temp;
        temp = newptr[j+1];
        newptr[j+1] = newptr[j];
        newptr[j] = temp;
    }
}**

- Connor

Answer 1

顺序很重要。

更改

for(;*newptr[j] < *newptr[j+1] && j!=0; j--) 

至：

for(; j != -1 && *newptr[j] < *newptr[j+1]; j--) 

可能存在的错误会导致代码崩溃。这是因为for循环中的表达式是从左到右进行评估的。所以在检查j != -1之前，*newptr[j]就被评估了。因此，在某些情况下，当评估*newptr[j]时，j可能等于-1，这是非法的。

改变顺序还有第二个原因：短路求值。

在评估由两个条件A和B组成的表达式时，C++不总是需要评估两个条件。

例如，在语句中：

if (A && B) {
  //do something 
}

如果A被评估为false，那么无论B评估为什么，显然A && B都不能评估为true。因此，B的值甚至不会被检查。所以在你的情况下，在表达式中。

j != -1 && *newptr[j] < *newptr[j+1]

如果j != -1为假，C++就不需要评估表达式的其余部分来知道整个表达式是假的。因此，*newptr[j]永远不会发生，您也不会遇到错误。

- maditya

---

任何允许 j 值小于 -1 的未来代码更改都可以使用像 j>-1 这样的语句进行阻止。 - R Hughes

Answer 2

正如maditya所指出的那样，问题在于表达式在检查索引本身之前尝试访问无效索引，但我看到这个问题被标记为C++。你有没有明确的理由不使用STL？

struct sorter {
  bool operator() (const int* i, const int* j) { return (*i<*j);}
};

int c[8] = {3,1,5,7,8,2,6,4};
int *newptr[8];
for(int k = 0; k<8; k++)
  newptr[k] = &c[k];

std::sort(newptr, newptr+8, sorter());

甚至在C++11中可以更短：

int c[8] = {3,1,5,7,8,2,6,4};
int *newptr[8];
for(int k = 0; k<8; k++)
  newptr[k] = &c[k];
std::sort(newptr, newptr+8, [](const int *i, const int *j){return *i < *j;});

- Jack

---

我刚开始学习C++，所以我认为自己创建函数比使用别人的函数更有益。 - Connor

如果你想通过创建函数来学习C ++，那么这是可以的；但对于其他所有目的，这是错误的。 - Kyle_the_hacker

@user2651901：这就是我的观点，在C++中几乎必须使用STL。忘记它没有任何意义，因此虽然学习语法和语言的语义很有用，但在其他方面应该避免使用它。 - Jack