[谷歌笔试题] 只能进行 0 与其他数的swap操作的排序


长度为 N 的数组乱序存放着 0 到 N-1,现在只能进行 0 与其他数的swap操作,请设计并实现排序。
注意:必须通过交换实现排序。
已邀请:

改了下,原来有点理解错了,0应该也是乱序的,所以先找0

这个简单。检查A[i]是否等于i,不是则换到 A[ A[i] ]。0相当于一个中间变量。

假设swap(i)是交换A[i]和0元素. 0元素在发挥完中间变量作用后总放回 A[0].

完整的python测试代码:
    # -*- coding: gb18030 -*-
    from random import shuffle
        
    def swap(i):
       global k
       A[k],A[i] = A[i], A[k]
       k = i
       
    N = 100
    A = range(0,N)
    shuffle(A)
    print A
    
    for i in xrange(N):
        if A[i] == 0:
            k = i
            swap(0)
            break
            
    i = 1
    k = 0
    while True:
        if i==N:
            break
        if A[i] == i:
            i += 1
            continue
        # 记现在的 A[A[i]] 为 b
        # 下面这步之后, A[A[i]]=0, A[0]=b
        swap(A[i])
        # 下面这步之后, a[a[i]]=a[i], a[i]=0, a[0]=b
        swap(i)
        # 下面这步后,a[i]=b,a[0]=0
        swap(0)
    
    print A




时间复杂度:找0的时间复杂度O(N). 每次循环要么发现当前已经放好,要么把未来的某个位置放好了,所以是O(N)。加起来还是 O(N).

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~