javascript - 我为整数数组编写了一个自定义就地排序方法 (Javascript) - 时间复杂度？排序方法名称？

Question

我写了一个简单的算法，用于在 JS 中对整数数组进行排序。我想知道时间和空间复杂度是多少，这是否是一种有效的算法。我在网上找不到其他地方列出的这种排序方法(尽管它看起来类似于冒泡排序)。我意识到 JS 有一个内置的排序功能，但我写这个是为了练习。请让我知道您的想法:

function arraySort(array){
  var i = 0;

  //helper function to sort backwards
  function leftSort(j){
    if(array[j] < array[j-1]){
      //swap in place
      temp = array[j]
      array[j] = array[j-1]
      array[j-1] = temp
      if(j-1 > 0){
        //call recursively to swap further left
        leftSort(j-1)
      }
    }
  }

  //sort forwards
  while(i < array.length){
    if(array[i] > array[i+1]){
      //swap in place
      var temp = array[i]
      array[i] = array[i+1]
      array[i+1] = temp
      if(i>0){
        //sort swapped value backwards to the left
        leftSort(i)
      }
    }
    i++
  }

  leftSort(i)

  return array
}

Answer 1

这似乎本质上是一种具有特殊执行顺序的冒泡排序。

您的算法将数组来回移动 (n)*(0.5n) 次 -> O(n^2)。空间复杂度是常数，因为这是就地排序。