求算法高手算下这个时间复杂度

Question

function partition(numbers: array, low: integer, high: integer)
i: integer = low
j: integer = high
tmp: integer
pivot: integer = numbers[(low + high) / 2]

loop(while i <= j)
  loop(while numbers[i] < pivot)
  i++
end loop

loop(while numbers[j] > pivot)
  j--
end loop

if(i <= j)
  tmp = numbers[i]
numbers[i] = numbers[j]
numbers[j] = tmp
i++
j--
end if
  end loop

return i
end function

function sort(numbers: array, low: integer, high: integer)
index: integer = partition(numbers, low, high)
if(low < index - 1)
  sort(numbers, low, index - 1)
end if
  if(index < high)
    sort(numbers, index, high)
end if
  end function

partition这个方法是干嘛的？
这个算法的时间复杂度是多少?
如果没有排序，而是随机的顺序，那时间复杂度是多少?

Answer 1

这是一个最简单的快速排序程序。

partition这个方法是干嘛的？

你先去了解下什么是快速排序，自然就理解了。

这个算法的时间复杂度是多少?

最佳时间复杂度 - nlog(n)；最差时间复杂度 - n*n。详见 https://subetter.com/algorith...

如果没有排序，而是随机的顺序，那时间复杂度是多少?

一个算法的时间复杂度我们一般有三个指标，最差、最佳、平均。前两个已经说过了，第三个解释起来很难，我也没本事解释，因为这确实很难很难很难！但可以告诉你答案，因为大牛已经解释过了，是 nlog(n)。

Answer 2

partition 方法做了以下事情：

1. 在当前数组 [begin, end] 中找一个数字作为基准数
2. 遍历数组，把比基准数小的都放在基准数左边，把比基准数大或者等于的都放在其右边，这样基准数所在的位置就是排序后它应该在的位置。
3. 递归上述过程，分别对基准数左边和右边的子数组做 partition 操作。

这是快排的思路。