时间戳

首页 > 解决方案 > 在冒泡排序中计算气泡，如何在更短的时间内得到这个计数

python - 在冒泡排序中计算气泡，如何在更短的时间内得到这个计数

问题描述

如何在更短的时间内获得此计数。如果有可能用更少的时间获得它，我有时间超越这种类型。

swaped = True
count = 0
while swaped != False:
    swaped = False
    **count** = **count**+1
    # here is bubble count
    for i in range(0, N-1):
        if(arr[i] > arr[i+1]):
            temp = arr[i]
            arr[i] = arr[i+1]
            arr[i+1] = temp
            swaped = True

print(count)

标签： pythonbubble-sort

解决方案

您编写的冒泡排序代码已尽可能优化。因此，您需要为算法找到替代方案来达到目的。完成交换次数的算法之一是使用归并排序。您可以使用归并排序来计算 O(nlogn) 时间内的交换。这个问题被称为反转计数。我在下面提供了一个代码示例，可以在 O(nlogn) 时间内完成此操作。

def mergeSort(arr, n): 
    temp_arr = [0]*n 
    return tmergeSort(arr, temp_arr, 0, n-1) 

# This Function will use MergeSort to count inversions 

def tmergeSort(arr, temp_arr, left, right): 

    # Inversions_count
    inv_count = 0

    if left < right: 

        # Mid of an array
        mid = (left + right)//2

        # calculating inversions_count for the left array.
        inv_count = tmergeSort(arr, temp_arr, left, mid) 

        # calculating inversions_count for the right array.
        inv_count += tmergeSort(arr, temp_arr, mid + 1, right) 

        # Merging two sorted arrays.
        inv_count += merge(arr, temp_arr, left, mid, right) 
    return inv_count 

# Merging two sorted arrays. 
def merge(arr, temp_arr, left, mid, right): 
    i = left     
    j = mid + 1 
    k = left      
    inv_count = 0
 
    while i <= mid and j <= right: 

        # No inversion if arr[i] <= arr[j] 

        if arr[i] <= arr[j]: 
            temp_arr[k] = arr[i] 
            k += 1
            i += 1
        else: 
            # Inversion will occur if arr[i] > arr[j] 
            temp_arr[k] = arr[j] 
            inv_count += (mid-i + 1) 
            k += 1
            j += 1

    # The remaining elements of left array are copied
    while i <= mid: 
        temp_arr[k] = arr[i] 
        k += 1
        i += 1

    # The remaining elements of right array are copied
    while j <= right: 
        temp_arr[k] = arr[j] 
        k += 1
        j += 1

    for loop_var in range(left, right + 1): 
        arr[loop_var] = temp_arr[loop_var] 
        
    return inv_count 
  
# Given array is 
arr = [83, 20, 9, 50, 115, 61, 17] 
n = len(arr) 
result = mergeSort(arr, n) 
print("Inversions_count =", result)

推荐阅读