C#中数组类型数据结构的选择排序时间复杂度

Question

我在 C# 中使用数组（不是数组列表）实现了选择排序。大多数地方提到的选择排序的时间复杂度是O(n^2).

在我下面的实现中，我将其视为 O(n^3)。有没有办法让它成为 O(n^2)？

很多书上把选择排序的时间复杂度定义为O(n^2)，我看到作者没有考虑数组中pop或者元素移除步骤的时间复杂度也是O(n) .

using System;
public class SortArray
{
 public int[] SlectionSort(int[] arr)
 {
   int[] newarr = new int[arr.Length];
   for(int i=0; i<newarr.Length; i++)
   {
     int smallest_index = findSmallest(arr);
     newarr[i] = arr[smallest_index];
     arr = pop(arr, smallest_index);
   }
   return newarr;
 }

 public int findSmallest(int[] arr)
 {
   int smallest = arr[0];
   int smallest_index = 0;

   for(int i = 1; i < arr.Length; i++)
   {
     if(arr[i] < smallest)
     {
       smallest = arr[i];
       smallest_index = i;
     }
   }
   return smallest_index;
 }

 public static int[] pop(int[] arr, int index)
 {
   int size = arr.Length - 1; 
   int[] newArr = new int[size];
   int n = 0;
   for(int i=0; i < arr.Length; i++)
   {
     if( i > newArr.Length-1)
     { 
     break;
     }
   if(i < index)
   {
      newArr[i] = arr[i];
   }
   else 
   {
     newArr[i] = arr[i+1];
   }
 }
 return newArr;
 }
}

Answer 1

简而言之，您通过强制选择排序在固定（而不是动态）内存上运行来延迟选择排序。当您看到列出复杂性的通用算法时，这更像是一个指南，而不是一个承诺。如果您的数据结构与算法不匹配，您将无法达到相同的上限时间复杂度。

I see the author doesn't consider the time complexity for pop or element removal step in array which is also O(n).

这表明您输入的内容组织不当。举一个更极端的例子，如果我坚持将我的列表存储在磁带上，则数组访问是 O(n)，因为我需要等待磁带在读头下绕线。这并不意味着算法更复杂。这意味着实现在算法的道路上设置了障碍。

在某些情况下，这可能是必要的约束。但是对于问题中的情况，您只需要一个不采用算法来删除和插入项目的数据结构，例如 List.

C#中数组类型数据结构的选择排序时间复杂度

Selection sort time complexity for array type data structure in C#

c#

algorithm

data-structures

selection-sort