求数组元素排序后位置

Question

请大家帮帮忙，需要类似下面代码的功能，这个是我写的，未考虑元素重复问题而且效率太低，有比较好的方法吗？    public static int[] sSort(double[] arr){
        int[] result=new int[arr.length];
        int temp;
        
        for(int i=0;i<arr.length;i++){
            temp=0;
            for(int j=0;j<arr.length;j++){
                if(arr[j]>arr[i])temp++;
            }
            result[temp]=i;
        }
        return result;
    }

Answer 1

/**
 * project_name: Test
 * package_name: csdn_Test_20071126
 * package_declaration: package csdn_Test_20071126;
 * filename: ArraySortTest.java
 * author: yuhaiming
 * date: 2007-12-8
 */
package csdn_Test_20071126;
import java.text.*;
import java.util.*;
public class ArraySortTest {
/**
 * 主处理函数
 */
public static void disposal(){
int[] a = {1,2,8,6,3};
Arrays.sort(a);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+"  ");
}
}
/**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
disposal();
}}

Answer 2

to:seaforce谢谢，不过你可能没注意到我的代码，我需要的不是排序功能。
排序后查找也可以得到我需要的功能，但是需要的空间比较大。

Answer 3

看你的功能是按照从大到小的顺序进行排序的，可以按照这样的思路实现：
1、第一次从所有的数字中挑出最大数字的下标，放在结果数组的第一个位置
2、从剩余的数字中挑出最大数字的下标，然后放在结果数组的第二个位置
3、依次类推
int[] m = {4,3,2,5,1};
int result[] = new int[m.length];
for(int i = 0;i < m.length;i++){
     int maxIndex = i;
     for(int j = i + 1;j < m.length;j++)
           if(m[maxIndex] < m[j]){
                  maxIndex = j;
           }
     }
     result[i] = maxIndex;
}

Answer 4

to:Mailbomb
谢谢，你的思路我也想过，就是在“从剩余的数字中挑出最大数字的下标”这里
比较麻烦。所以我用遍历整个数组去实现。btw:你的代码那种方式是错误的。

Answer 5

这段代码改写了Arrays.sort，增加一个索引数组，排序过程同时修改索引数组。即使用快速排序。对10,000个随机数测试，速度相当快。请参考。class SortTest {
public static int[] indexSort(double []arr) {
int length = arr.length;
int[] index = new int[length];
for(int i=0; i<length; ++i)
index[i] = i;
sort1(arr, index, 0, length);
for(int i=0; i<length/2; ++i) //Reverse to descending order
swap(index, i, length-1-i);
return index;
}
/** Sorts the specified sub-array of doubles into ascending order. */
private static void sort1(double[] dx, int[] ix, int off, int len) {
     // Insertion sort on smallest arrays
     if (len < 7) {
     for (int i=off; i<len+off; i++)
     for (int j=i; j>off && dx[ix[j-1]]>dx[ix[j]]; j--)
     swap(ix, j, j-1);
     return;
     }
    
     // Choose a partition element, v
     int m = off + (len >> 1);       // Small arrays, middle element
     if (len > 7) {
     int l = off;
     int n = off + len - 1;
     if (len > 40) {        // Big arrays, pseudomedian of 9
     int s = len/8;
     l = med3(dx, ix, l,     l+s, l+2*s);
     m = med3(dx, ix, m-s,   m,   m+s);
     n = med3(dx, ix, n-2*s, n-s, n);
     }
     m = med3(dx, ix, l, m, n); // Mid-size, med of 3
     }
    
     double v = dx[ix[m]];
     // Establish Invariant: v* (<v)* (>v)* v*
     int a = off, b = a, c = off + len - 1, d = c;
     while(true) {
     while (b <= c && dx[ix[b]] <= v) {
     if (dx[ix[b]] == v)
     swap(ix, a++, b);
     b++;
     }
     while (c >= b && dx[ix[c]] >= v) {
     if (dx[ix[c]] == v)
     swap(ix, c, d--);
     c--;
     }
     if (b > c)
     break;
     swap(ix, b++, c--);
     }
    
     // Swap partition elements back to middle
     int s, n = off + len;
     s = Math.min(a-off, b-a  );  vecswap(ix, off, b-s, s);
     s = Math.min(d-c,   n-d-1);  vecswap(ix, b,   n-s, s);
    
     // Recursively sort non-partition-elements
     if ((s = b-a) > 1)
     sort1(dx, ix, off, s);
     if ((s = d-c) > 1)
     sort1(dx, ix, n-s, s);
    }
    
    /** Swaps x[a] with x[b]. */
    private static void swap(int[] x, int a, int b) {
     int t = x[a];
     x[a] = x[b];
     x[b] = t;
    }
    
    /** Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */
    private static void vecswap(int[] x, int a, int b, int n) {
     for (int i=0; i<n; i++, a++, b++)
     swap(x, a, b);
    }
    
    /** Returns the index of the median of the three indexed doubles. */
    private static int med3(double[] dx, int[] ix, int a, int b, int c) {
     double da=dx[ix[a]];
     double db=dx[ix[b]];
     double dc=dx[ix[c]];
     return (da<db ? (db<dc ? b : da<dc ? c:a) : (db>dc ? b : da>dc ? c:a));
    }
}

Answer 6

排序后查找也可以得到我需要的功能，但是需要的空间比较大。
大于十个以上冒泡法就不效率了
看看这个方法：
Arrays.binarySearch(double[] a, double key) 

Answer 7

谢谢ltc_mouse和其他留言的朋友，结贴了。