选择排序计数比较

Question

我有一个Selection Sort的程序，它按升序和降序生成和排序随机数。问题在于计算比较。它给出了正确的数字，直到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）比较。

Answer 2

乍一看int *compare能够包含最大值65536.尝试long。

https://en.wikipedia.org/wiki/C_data_types