可能重复:
就地数组重新排序?
我有原始的未排序数组,其结构如下:
{D, A, B, E, C}
以及按排序顺序排列的原始数组的索引数组:
{2, 3, 5, 1, 4} // Edited. Then I get {A, B, C, D, E}.
如何通过索引数组简单地重新排列原始数组?
我无法创建新数组并按索引位置插入元素。
我的 5 美分:
int new_i;
for (int i = 0; i < arr_size-1; ++i)
{
while ((new_i = index_arr[i]-1) != i)
{
std::swap(struct_arr[i], struct_arr[new_i]);
std::swap(index_arr[i], index_arr[new_i]);
}
}
O(N^2) 解决方案:
struct S[] = {D, A, B, E, C};
int o[] = {2, 3, 5, 1, 4};
int len = 5;
for (int i=1;i<=len;++i) {
for(int j=i-1; j<len;++j) {
if(o[j]==i) {
if (i!=j+1) {
swapSArrayItems(S, j, i-1);
swapIntArrayItems(o, j, i-1);
}
break;
}
}
}
这是一个有效的版本,但请注意它确实使indices
变量无效:
void sortItemsBasedOnIndices(char *items[], int indices[], size_t num)
{
// sort them
for (int i = 0; i < num; i++)
{
int newIndex = indices[i];
// take out the item at the specified index
char *newItem = items[newIndex];
// take out the item in that current position
char *oldItem = items[i];
// swap the two items
items[i] = newItem;
items[newIndex] = oldItem;
// now, tell the sorted indices the location of the old item after swap
for (int j = i; j < num; j++)
{
if (indices[j] == i)
{
indices[j] = newIndex;
break; // we only need the first one, so then we're done
}
}
}
}
int main()
{
char *items[] = { "D", "B", "E", "A", "C" };
int sortedIndices[] = { 3, 1, 4, 0, 2 }; // 0-based
int size = 5;
sortItemsBasedOnIndices(items, sortedIndices, size);
for (int i = 0; i < size; i++)
{
puts(items[i]);
}
}
#include <stdio.h>
void shuffle( char **arr, int *offs, size_t cnt);
void shuffle( char **arr, int *offs, size_t cnt)
{
unsigned idx,src,dst;
for (idx=0; idx < cnt; idx++) offs[idx] -= idx;
for (idx=0; idx < cnt; idx++) {
if (offs[idx] == 0) continue;
char *tmp;
tmp = arr[idx];
for(dst = idx; offs[dst] ; dst=src) {
src = dst+offs[dst] ;
arr[dst] = arr[src];
offs[dst] = 0;
if (offs[src] == 0 ) break;
}
arr[dst]=tmp;
}
}
int main (void)
{
unsigned idx;
char *array[5] = {"D","A","B","E","C"};
int index[5] = {1,2,4,0,3};
fprintf(stdout, "Original:\n");
for (idx=0; idx < 5; idx++) {
fprintf(stdout, "[%u]:%s\n", idx, array[idx] );
}
fprintf(stdout, "Shuffle:\n");
shuffle( array, index, 5);
fprintf(stdout, "After shuffle:\n");
for (idx=0; idx < 5; idx++) {
fprintf(stdout, "[%u]:%s\n", idx, array[idx] );
}
return 0;
}
更新:固定链结束条件(丑陋!)