java - 索引排序。发生了一些非常奇怪的事情

Question

       public int[] indexSort(){
    int[] sortedarr = new int[max];

    for(int i=0;i<max;i++){
        int key=0;
        int duplicates = 0;
        for(int j=0;j<max;j++){
            if(arr[i]>arr[j]) key++;
            else if(arr[i]==arr[j]) duplicates++;

        }
        while(duplicates>0&&key<max){


            sortedarr[key] = arr[i];
            key++;
            duplicates--;
        }
    }
    return sortedarr; }

while 循环是如何工作的？即使没有重复项(duplicates=0)，while 循环仍然会执行。

我的心很困惑。索引排序是否应该按 O(n^3) 运行？

Answer 1

总有一个“重复”:当i == j时。

您可能应该在 i+1 处开始内部循环:

for(int i=0;i<max;i++){
    int key=0;
    int duplicates = 0;
    for(int j=i+1;j<max;j++){