我可以提高这个选择排序算法的运行时间吗？

Question

我一直在尝试编写自己的选择排序算法，并在随机生成的大小为 10000、50000 和 100000 的数组上对其进行测试。我的算法工作正常，但我试图让它尽快工作。在我的机器上，测试分别花费大约 0.45 秒、1.88 秒和 11.77 秒。有什么方法可以改进我的算法，使其运行得更快吗？

void SelectionSort(int array[], int len){

  int temp,i,j,min,minpos;


    for(j=0;j<len;j++){
         minpos=j;

       for(i=j+1;i<len;i++){

           if(array[minpos]>array[i]){
               minpos=i;
            }
         }

      temp=array[j];
      array[j]=array[minpos];
      array[minpos]=temp;

     }

}

Answer 1

如果一个数组只包含两个元素，那么由于外部循环的这种情况，它不会被排序

for(j=0;j<len-2;j++){
        ^^^^^^^

我认为如果在交换数组元素之前检查当前元素和最小元素是否相同，可以提高效率。

所以我想建议以下实现

void SelectionSort( int a[], size_t n )
{
    for ( size_t i = 0; i < n; i++ )
    {
        size_t min = i;;

        for ( size_t j = i + 1; j < n; j++ )
        {
            if ( a[j] < a[min] ) min = j;
        }

        if ( i != min )
        {
            int tmp = a[i];
            a[i] = a[min];
            a[min] = tmp;
        }
    }
}