c - 选择排序计数比较

Question

我有一个带有选择排序的程序，它可以生成随机数并按升序和降序排序。问题在于比较的计数。它给出了 10 0000 个数字之前的正确数字，但是当我生成 100k 个数字时，它返回的值比公式中的值错误。 这是我的选择排序代码。

void select (int n, float *pole2,int *compare,int *move,char decide)
{
    *compare=0; // number of comparisons
    *move=0;

int i; 
     for (i = 0; i < n - 1; i++)
     {                              
         int j, poz_min;
         float temp,min;
         min = pole2[i];
         poz_min = i;//
         for (j = i+1; j < n; j++)
         {  
                *compare+=1;
                 if (pole2[j] < min)
                 {  
                    min = pole2[j];
                    *move+=1;
                    poz_min=j;
                 }  
         }
         temp = pole2[i];
         pole2[i] = pole2[poz_min];
         pole2[poz_min] = temp;
         *move+=3;
     }


// Writing to a binary file     

FILE *fw;
    fw = fopen("Select_SORT.DAT", "wb+");
int z;
for(z = 0; z < n; z++)
    {
        fwrite(&pole2[z], sizeof(pole2[z]), 1, fw);
    }
 fclose(fw);


 fseek(fw, 0, SEEK_SET);


}

Answer 1

那是因为对于 100K 实际上有 10^10 比较。您系统上的 int 无法容纳它。为了安全起见，请尝试使用long long。还要将您得到的结果与 INT_MAX 进行比较。你就会明白了。

对于n个元素，有O(n^2)(准确地说是n*(n-1)/2)比较如果是选择排序。