这种排序有什么名字吗？

Question

我写过/使用过这种排序。我只是想知道它是否有任何名称或与任何现有的排序算法相似。顺便说一句，它甚至有效/有价值还是不正确？

int s = 20;

int unsorted_array[s];

//(adding numbers to unsorted_array)
//We assume that every number is different to avoid any difficulties.

int i, i2, pos;
int sorted_array[s];

//!!! sorting algo starts here:

for(i=0; i<s; i++){
   pos = 0;
   for(i2=0; i2<s; i2++){

      if(unsorted_array[i] > unsorted_array[i2]){
         pos += 1;
      }
   }

   sorted_array[pos] = unsorted_array[i];

}

所以你怎么看？比其他种类的分类方法慢/快吗？我还在学习。感谢您的任何答复！

Answer 1

它比其他种类的排序方法慢/快吗？

让我们分析该函数的时间复杂度。随着未排序列表的大小增长，它将需要做多少工作？

重要的部分是循环。他们会告诉我们您需要执行多少次操作，这很重要。您的循环可细分为：

for(1 to s){
   for(1 to s){
       do that thing
   }
}

对于每个元素，必须重新检查每个元素。如果有2个项目，则意味着您执行了4次操作。3项，9次。4项，16倍。我们说时间复杂度是n^2（n是大小的约定），因为随着大小的增加，步数是平方的。这意味着所需的时间将随着大小的增加而呈指数增长。10件物品要花100倍。每100件物品需要10,000。以1,000为单位，需要1,000,000。n^2如果可能，应避免使用。

大多数排序算法可以在n * log(n)准线性时间内完成工作。随着大小的增加，时间将增加n * log(n)。这比线性快，但比指数慢。log(n)通常是自然对数或ln(n)。如果是10件商品，则大约需要23次。100约460。1000约6900。所以您的算法较慢。

上面的算法n * log(n)增长如此之快，因此有必要扭曲垂直时标，以使用性能更好的算法将它们有意义地拟合在同一张图上。

如您所料，对于大量项目，拥有更好性能的算法比更快地完成工作更为重要。一种n^2算法的执行速度比快100倍，n log n它将损失约600项。

n^2 = 100 n * ln(n)
n = 100 ln(n)
n / ln(n) = 100