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

Question

希望我能就我制作的排序方法得到一些建议.

这只是我正在制作的另一个程序的测试,这个测试有一个我无法弄清楚的错误.此代码的目的是创建一个int指针数组,并通过regular int数组的内容对该数组中的指针进行排序.

该错误是我的第二个for循环,它不允许我使用aj!= - 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;
    }
}**

Answer 1

订单很重要.

更改

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

至:

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

据推测,这个bug会导致代码崩溃.发生这种情况是因为for循环中的表达式是从左到右计算的.因此在检查之前是否*newptr[j]进行评估.因此,它是可以想象的,在某些时候,等于当评估,这是违法的.j != -1j-1*newptr[j]

由于第二个原因,改变顺序确实有所不同:短路评估.

当评价两个表达式由两个条件A和B,C++并不总是需要评估两个条件.

例如在声明中

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

如果A被评估false,那么无论评估什么,显然A && B都无法评估.所以从来没有检查过它的价值.所以在你的情况下,在表达式中trueBB

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

如果j != -1为false,则C++不需要计算表达式的其余部分,以便知道整个表达式为false.所以*newptr[j]永远不要发生,你没有得到这个bug.

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