c - 了解 C 的排序算法

Question

我正在准备周五的 GNU C 测试。评论中有一个问题我无法理解。 “以下算法将数组按升序排序。该算法对排序内容的顺序(随机、排序顺序、反向排序顺序)敏感。根据比较和排序的确切次数以数字方式评估算法性能最小和最大运行时间性能所需的交换。当 N 接近 ∞ 时，其整体性能以大“O”表示法表示。您必须分析性地支持您的答案才能获得学分。在算法输入中具有相同值的 key 如何处理排序完成后出现吗？”

//Sort Grades in ascending order by locating grade[0], then grade[1], etc.
   void AscendingSort( int intArray[ ], int numInt){
    for(int j = 0; j < numInt - 1; j++ ){
      for(int k = j + 1; k < numInt; k++ ){ 
          if( grades[ j ] > grades[ k ] ){ 
             int temp = grades[ j ]; 
             grades[ j ] = grades[ k ];
            grades[ k ] = temp;
            }
          }
        }
      }

所以我相信这是一个冒泡排序，对于排序顺序的最佳情况，复杂度为 O(N)。对于更坏的情况(逆序)和随机顺序，它将是 O(N^2)。那么我该如何准确计算呢？我如何根据给定的信息实际计算比较和交流的次数？另外，如果您能详细了解排序算法，我将不胜感激，我很难理解这一点。 :(提前致谢!!

Answer 1

首先，您需要了解冒泡排序和选择排序之间的区别。

• Selection Sort :排序是通过将所有元素与第一个元素进行比较来完成的。然后对第二个元素进一步重复，依此类推。

• Bubble Sort :排序是通过比较数组的两个相邻索引来完成的。

为了计算复杂性，请考虑numInt = 5

现在，从最里面的循环开始考虑:

k = 0+1=1; k<5

此循环将一直持续到 k 计算结果为 4，当 k=5 时循环结束且不进行比较。因此，循环从 k=1 执行到 k=5，即 5 次，其中 = intNum 次。

现在考虑这里的外循环:

j = 0; j<4 

此循环将一直持续到 j 计算结果为 3，当 j=4 时循环结束且不进行比较。因此，循环从 j=0 执行到 j=4，即 5 次，其中 = intNum 次。

对于嵌套循环，我们乘以循环的复杂性。因此它的计算结果为

intNum*intNum = intNum^2

和O(intNum^2)。

引用these further details of complexity evaluation .