c - 这种排序有什么名字吗？

Question

我写/用过这种排序。我只是想知道它是否有任何名称，或者它是否类似于任何现有的排序算法。顺便问一下，它是否真的有效/有值(value)？

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

Is it slower/faster than other kinds of sorting methods?

让我们分析一下the time complexity of this function .随着未排序列表的大小增加，它需要做多少工作？

重要的部分是循环。他们会告诉我们你需要做多少次，这很重要。您的循环可以分解为:

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 应尽可能避免。

Most sorting algorithms可以在 n * log(n) 或准线性时间内完成工作。随着大小的增加，时间将增加 n * log(n)。这比线性快，但比指数慢。 log(n) 通常是 natural logarithm或 ln(n)。在 10 项时，大约需要 23 次。 100 大约 460。1000 大约 6900。所以你的算法比较慢。

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

您可以猜到，对于大量项目而言，拥有性能更好的算法比更快地处理事情更为重要。比 n log n 快 100 倍的 n^2 算法将丢失大约 600 个项目。

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