Interviewstreet的插入排序程序

Question

我試圖編程Interiewstreet的插入排序挑戰Link for the challenge 在Python中，這裏是我的代碼如下所示。

該程序運行良好的輸入元素的限制（我不知道），但返回一個錯誤的輸出大尺寸的輸入。任何人都可以指導我做錯了什麼？

# This program tries to identify number of times swapping is done to sort the input array 

""" 
=>Get input values and print them 
=>Get number of test cases and get inputs for those test cases 
=>Complete Insertion sort routine 
=>Add a variable to count the swapping's 
""" 

def sort_swap_times(nums): 
    """ This function takes a list of elements and then returns the number of times 
     swapping was necessary to complete the sorting 
    """ 

    times_swapped = 0L 
    # perform the insertion sort routine 
    for j in range(1, len(nums)): 
    key = nums[j] 
    i = j - 1 
    while i >= 0 and nums[i] > key: 
     # perform swap and update the tracker 
     nums[i + 1] = nums[i] 
     times_swapped += 1 
     i = i - 1 
    # place the key value in the position identified 
    nums[i + 1] = key 

    return times_swapped 


# get the upper limit. 
limit = int(raw_input()) 
swap_count = [] 

# get the length and elements. 
for i in range(limit): 
    length = int(raw_input()) 
    elements_str = raw_input() # returns a list of strings 

    # convert the given elements from str to int 
    elements_int = map(int, elements_str.split()) 

    # pass integer elements list to perform the sorting 
    # get the number of times swapping was needed and append the return value to swap_count list 
    swap_count.append(sort_swap_times(elements_int)) 


# print the swap counts for each input array 
for x in swap_count: 
    print x 

Answer 1

你的算法是正確的，但是這是一個很自然的做法的問題，並會給你大量的測試用例（即LEN（NUMS）> 10000）一時間超限信號。我們來分析算法的運行時複雜性。

for j in range(1, len(nums)): 
    key = nums[j] 
    i = j - 1 
    while i >= 0 and nums[i] > key: 
     # perform swap and update the tracker 
     nums[i + 1] = nums[i] 
     times_swapped += 1 
     i = i - 1 
    # place the key value in the position identified 
    nums[i + 1] = key 

在上面的片段所需的步驟的數量是正比於1 + 2 + .. + LEN（NUMS）-1，或LEN（NUMS）*（LEN（NUMS）-1）/ 2個步驟，它是O（len（nums）^ 2）。

提示：

使用的事實，所有的值將是[1,10^6]內。你在這裏真正做的是找到列表中的反轉次數，即查找所有對的i < j s.t. nums [i]> nums [j]。考慮一個數據結構，它允許您以對數時間複雜度查找每個插入操作所需的交換次數。當然，還有其他的方法。

擾流：

Binary Indexed Trees