Cree una estructura que contenga dos campos: index y value .

Cree una matriz de estas estructuras, donde cada elemento (estructura) es el índice original y el valor de un elemento en la matriz.

Ordene la estructura usando SOLO el valor en O (nlogn).

Cuando haya terminado, itere la matriz en el orden ordenado para obtener los índices ordenados.

usar qsort Por ejemplo

 #include <stdio.h> #include <stdlib.h> int *TheArray; int cmp(const void *a, const void *b){ int ia = *(int *)a; int ib = *(int *)b; return (TheArray[ia] > TheArray[ib]) - (TheArray[ia] < TheArray[ib]); } int main(void) { int a[] = {2,3,4,5,8,2,5,6}; size_t len = sizeof(a)/sizeof(*a); int a_index[len]; int i; for(i = 0; i < len; ++i) a_index[i] = i; TheArray = a; qsort(a_index, len, sizeof(*a_index), cmp); for(i = 0; i < len; ++i) printf("%d ", a_index[i]);//5 0 1 2 6 3 7 4 : qsort is not a stable. printf("\n"); return 0; }

¿No sería esto esencialmente solucionable con una implementación de cualquier algoritmo de clasificación, con el siguiente ajuste:

Donde normalmente compararías algo como: if (a[x] < a[x+1])

Ahora estarás haciendo: if (a[a_index[x]] < a[a_index[x+1]])

Y en lugar de: swap(a[x], a[x+1])

Estarás haciendo: swap(a_index[x], a_index[x+1])

(Donde a_index se inicializa para contener el rango de índices en orden secuencial inicialmente (0..sizeof(a))

Dado que esencialmente a_index es solo una tabla de búsqueda, donde el valor para ordenar es el valor correspondiente en a. (En la práctica, esto es solo otro nivel de indirección en comparación con lo que normalmente hacemos cuando ordenamos, ya que normalmente tampoco compararíamos (x) y (x+1) directamente)

Se puede hacer una solución similar sin hacer una clasificación en el lugar también, siempre que realice todas sus comparaciones con los valores correspondientes en a, en lugar de comparar el