我可以简化 C 中的选择排序吗？

Question

C中的选择排序通常写成下面的代码形式，引入一个min_pos变量，其中存储了[=13的特定步骤中数组的最小数的索引=]循环：

void selectionsort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int min_pos = i;
        for (int j = i + 1; j < n; j++)
        {
            if (A[j] < A[min_pos])
            {
                min_pos = j;
            }
            if (min_pos != i)
            {
                int temp;
                temp = A[i];
                A[i] = A[min_pos];
                A[min_pos] = temp;
            }
        }
    }
    return;
}

但是，当我们使用下面的代码可以得到相同的结果时，是否有必要引入这个变量？

void selectionsort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (A[j] < A[i])
            {
                int temp;
                temp = A[i];
                A[i] = A[j];
                A[j] = temp;
            }
        }
    }
    return;
}

Answer 1

我认为这两种算法都不是特别有效，更有效的写法如下：

void selectionsort(int A[], int n)
{
   for (int i = 0; i < n - 1; i++)
   {
       int min_pos = i;
       for (int j = i + 1; j < n; j++)
       {
           if (A[j] < A[min_pos])
           {
               min_pos = j;
           }
       }
       if (min_pos != i)
       {
           int temp;
           temp = A[i];
           A[i] = A[min_pos];
           A[min_pos] = temp;
       }
   }
   return;
}

注意 min_pos 变量是如何用作交换位置的临时存储的。这是有益的，因为交换需要三个操作，而使用 min_pos 只需要一个操作。

Answer 2

两个函数实现相同的结果，但没有一个是 selection sort. They implement a less efficient algorithm called exchange sort 的正确实现。

对于选择排序，应对数组中的每个元素执行一次交换。这可能是第一个函数中 min_pos 变量的目的。

这是修改后的版本：

void selectionsort(int A[], int n)
{
   for (int i = 0; i < n - 1; i++)
   {
       int min_pos = i;
       for (int j = i + 1; j < n; j++)
       {
           if (A[j] < A[min_pos])
           {
               min_pos = j;
           }
       }
       if (min_pos != i)
       {
           int temp = A[i];
           A[i] = A[min_pos];
           A[min_pos] = temp;
       }
   }
}

Answer 3

这是一个名为 portfolio courses

的 YouTube 频道所有者的精彩解释（未修改）

哇 - 这是一个很棒的问题！ :-) 所以上面的算法也可以工作，但它只是以不同的方式对数组进行排序。至于为什么我们可能不这样做：

这是一个关于选择排序的视频，上面的算法不是选择排序（虽然很接近）。在选择排序中，我们在未排序的部分找到 smallest/largest 元素，并将其与最左边的未排序算法交换。其他方法也可能有效，但它们将不再是选择排序。上述方法将进行比所需更多很多的交换。
为了比较，我在这里修改了这段代码来测试两种不同的算法：https://github.com/portfoliocourses/c-example-code/blob/main/selection_sort.c。我修改了代码以计算所需的交换次数（请参阅下面有关选择排序和您所做的新算法的修改）。选择排序只需要 6 次交换，而上面的代码需要 31 次交换。

使用选择排序的原因之一是当执行交换的时间成本很高时它很有用：https://en.wikipedia.org/wiki/Sorting_algorithm#Selection_sort。我知道这是维基百科，但看到这句话：“它不超过 n 次交换，因此在交换非常昂贵的地方很有用。”

选择排序：

  int num_swaps = 0;
  for (int i = 0; i < length - 1; i++)
  {
    // find the position of the minimum element in the unsorted portion of 
    // the array
    int min_pos = i;
    for (int j = i + 1; j < length; j++)
      if (a[j] > a[min_pos]) min_pos = j;
    
    // if that element is NOT the element at index i, then swap that element 
    // with the element at index i
    if (min_pos != i)
    {
      int temp = a[i];
      a[i] = a[min_pos];
      a[min_pos] = temp;
      num_swaps++;
    }
  }

新算法：

int num_swaps = 0;
for (int i=0; i<length-1; i++)
{
  for (int j=i+1; j<length; j++)
  {
      if(a[i]>a[j])
      {
          int temp;
          temp = a[i];
          a[i] = a[j];
          a[j] = temp;
          num_swaps++;
      }
  }
}

我可以简化 C 中的选择排序吗？

Can I simplify selection sort in C?

c

selection-sort