如何在单个循环中对数组进行排序？

Question

所以我正在经历不同的排序算法.但几乎所有的排序算法都需要2个循环来对数组进行排序.冒泡排序和插入排序的时间复杂度对于最佳情况是O(n),但是O(n ^ 2)是最坏情况,其再次需要2个循环.有没有办法在单个循环中对数组进行排序？

Answer 1

这里,Python中的单循环冒泡排序:

def bubbly_sortish(data):
    for _ in xrange(len(data)**2):
        i, j = _/len(data), _%len(data)
        if i<j and data[i] > data[j]:
            data[i], data[j] = data[j], data[i]

A = [5, 1, 2, 3, 5, 6, 10]
bubbly_sortish(A)

print A            

当然这是个玩笑.但这表明循环次数与算法复杂性无关.

现在,如果你问是否可以用O(n)比较对数组进行排序,不行,那是不可能的.对于基于比较的排序算法,下限是Ω(n log n).