在 C++ 中对指针数组进行排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18052204/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sorting Array of Pointers in C++
提问by Connor
Hoping I can get a little advice on a sorting method I made.
希望我能得到一些关于我所做的排序方法的建议。
The purpose of this code is to create a int pointer array and sort the pointers in that array by the contents of regular int array. Then assign values for a different variable based on the location of the original int array.
此代码的目的是创建一个 int 指针数组，并按常规 int 数组的内容对该数组中的指针进行排序。然后根据原始 int 数组的位置为不同的变量赋值。
The strangeness I am experiencing with this code is that the test code which shouldn't effect anything as far as I know... IS actually effecting the contents of my pointers. Perhaps the values aren't changing but the way I'm writing the test code is causing errors.
我在这段代码中遇到的奇怪之处在于，据我所知，测试代码不应该影响任何东西......实际上影响了我的指针的内容。也许这些值没有改变，但我编写测试代码的方式导致了错误。
//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++)
{
for(; j > -1 && *newptr[j] < *newptr[j+1]; j--)
{
int *temp = newptr[j+1];
newptr[j+1] = newptr[j];
newptr[j] = temp;
}
}
//set lookuplocation
int lookuplocation;
for(int i = 0; i<8; i++)
{
cout << *newptr[i];
if(newptr[i] == &c[0])
{
cout << *newptr[i] << endl;
//If I use endl or \n to test the pointers values I end up with only
//a part of the correct data.
cout << "\nSuccess!\n";
lookuplocation = 0;
}
}
//Also for my last test sometimes the first element gets messed up as well
//test arrays
for(int k = 0; k<8; k++)
{
cout << "Element " << k << ": " << *newptr[k] << endl;
cout << "Element " << k << ": " << newptr[k] << endl;
}
回答by Bartek Banachewicz
I figured someone might actually need to sort an array of pointers in a sane way:
我认为有人可能实际上需要以一种理智的方式对指针数组进行排序：
#include <iostream>
#include <array>
#include <algorithm>
int main() {
std::array<int, 8> arr { 3, 5, 4, 1, 2, 7, 6, 8 };
std::array<int*, 8> p_arr;
for (unsigned i = 0; i < 8; ++i) {
p_arr[i] = &arr[i];
}
std::sort(p_arr.begin(), p_arr.end(), [](int* a, int* b) { return *a < *b; });
for (auto i : p_arr)
std::cout << *i;
}
The ugly middle loop is totally replace'able by range for over zippped range, but I don't have my own implementation with reference semantics right now, and I am too lazy to check the Boost one.1
丑陋的中间循环完全可以被范围替换为超过 ppedzip范围，但我现在没有自己的参考语义实现，而且我懒得检查 Boost 一个。1
Here's a live sample on Coliru.
Also, because I think we should repeat this over and over until newbies understand it:
另外，因为我认为我们应该一遍又一遍地重复这个，直到新手理解它：
- Don't reinvent the sorting wheel (unless it's a toy implementation)
- Try to avoid using pointers in C++ if reasonably possible.
- 不要重新发明分拣轮（除非它是一个玩具实现）
- 如果可能的话，尽量避免在 C++ 中使用指针。
1This is actually important in order to make sure both ranges (in this case two arrays) have the same length. Different zipping conventions either require the ranges to be of the same length (crashing or throwing otherwise) or fill in the empty data should one of the ranges be too short. While seemingly obvious in such a simple program, be careful in real-world code.
1这实际上很重要，以确保两个范围（在本例中为两个数组）具有相同的长度。不同的压缩约定要么要求范围具有相同的长度（否则会崩溃或抛出），或者如果范围之一太短则填充空数据。虽然在这样一个简单的程序中看起来很明显，但在实际代码中要小心。
回答by Kyle_the_hacker
If your array c[n]has for range [1 .. n], you can use the following algorithm which work in O(n) time complexity:
如果您的数组c[n]具有范围 [1 .. n]，则可以使用以下算法，该算法的时间复杂度为 O( n)：
for(int j = 0; j < n; j++)
while(*newptr[*newptr[j] - 1] != *newptr[j])
std::swap(newptr[*newptr[j] - 1], newptr[j]);
The idea behind it is to assign the value 1 to the pointer newptr[0], 2 to the pointer newptr[1], ..., and nto the pointer newptr[n-1]. There is no algorithm that is more efficient (especially in C++11, since std::swapwill use std::move).
它背后的想法是将值 1 分配给指针newptr[0]，将值 2 分配给指针newptr[1]，...，将n分配给指针newptr[n-1]。没有比这更有效的算法（尤其是在 C++11 中，因为std::swap会使用std::move）。
So for int c[8] = {3,1,5,7,8,2,6,4}, you get (disregarding the reference to value table):
因此，对于int c[8] = {3,1,5,7,8,2,6,4}，您会得到（不考虑对值表的引用）：
1233
Success!
45678
1233
成功！
45678
Update:If you want the reverse order:
更新：如果你想要相反的顺序：
for(int j = 0; j < n; j++)
while(*newptr[n - *newptr[j]] != *newptr[j])
std::swap(newptr[n - *newptr[j]], newptr[j]);
For int c[8] = {3,1,5,7,8,2,6,4}, you get:
对于int c[8] = {3,1,5,7,8,2,6,4}，你得到：
8765433
Success!
21
8765433
成功！
21
回答by MAnyKey
Popular approach is to implement generic sortfunction that sorts elements with given comparator, so you can abstract over array elements. There are some ways:
流行的方法是实现sort使用给定比较器对元素进行排序的通用函数，因此您可以对数组元素进行抽象。有一些方法：
template<typename ElementType, typename CompType>
void sort(ElementType array[], size_t size, CompType cmp);
template<typename ElementType, typename CompType>
void sort(std::vector<ElementType> & array, CompType cmp);
template<typename IteratorType, typename CompType>
void sort(IteratorType first, IteratorType last, CompType cmp);
Last way is preferable because you can abstract over container type too.
最后一种方法更可取，因为您也可以抽象容器类型。
回答by DDW
Change this first:
先改这个：
for(; j > -1 && *newptr[j] < *newptr[j+1]; j--)
for(; j > -1 && *newptr[j] < *newptr[j+1]; j--)
into
进入
for(int i=j; i > -1 && *newptr[i] < *newptr[i+1]; i--)
for(int i=j; i > -1 && *newptr[i] < *newptr[i+1]; i--)
It seems alot more efficient..
似乎效率更高。。
