如何排序在一个循环数组？ [英] How to sort an array in a single loop?

问题描述

所以，我所经历的不同的排序算法。但几乎所有的排序算法需要2循环的数组进行排序。冒泡排序与放的时间复杂度;插入排序是O（n），最佳案例，但为O（n ^ 2）这又需要2个循环最坏的情况。有没有办法在一个循环数组排序？

So I was going through different sorting algorithms. But almost all the sorting algorithms require 2 loops to sort the array. The time complexity of Bubble sort & Insertion sort is O(n) for Best case but is O(n^2) as worst case which again requires 2 loops. Is there a way to sort an array in a single loop?

推荐答案

下面，一个单回路冒泡排序在Python：

Here, a single-loop Bubble Sort in 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            

当然，这是一个笑话。但是，这显示了循环的数量已经很少做与算法的复杂度。

Of course this is a joke. But this shows the number of loops has little to do with algorithm complexity.

现在，如果你问是否可以用O（n）的比较，不，的这是不可能的。下界是Ω（N log n）的比较为基础的排序算法。

Now, if you're asking if it is possible to sort an array with O(n) comparisons, no, it's not possible. The lower bound is Ω(n log n) for comparison-based sorting algorithms.

这篇关于如何排序在一个循环数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！