02299: Ultra-QuickSort

http://cs101.openjudge.cn/practice/02299/

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence 9 1 0 5 4 , Ultra-QuickSort produces the output 0 1 4 5 9 . Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

输入

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

输出

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

样例输入

样例输出

6
0

来源

Waterloo local 2005.02.05

python

"""
问题：分析特定排序算法，通过交换两个相邻的序列元素来处理n个不同的整数序列，直到序列按升序排序。
任务是确定需要执行多少次交换操作才能对给定的输入序列进行排序。  

可以通过使用归并排序的修改版本来解决，计算在每次合并步骤中需要的交换次数。
在归并排序中，将数组分成两半，对每一半进行排序，然后将它们合并在一起。

在合并步骤中，计算需要交换的次数，因为每当从右半部分取出一个元素时，
需要交换与左半部分中剩余元素相同数量的次数。
"""
def merge_sort(lst):
    # The list is already sorted if it contains a single element.
    if len(lst) <= 1:
        return lst, 0

    # Divide the input into two halves.
    middle = len(lst) // 2
    left, inv_left = merge_sort(lst[:middle])
    right, inv_right = merge_sort(lst[middle:])

    merged, inv_merge = merge(left, right)

    # The total number of inversions is the sum of inversions in the recursion and the merge process.
    return merged, inv_left + inv_right + inv_merge

def merge(left, right):
    merged = []
    inv_count = 0
    i = j = 0

    # Merge smaller elements first.
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            inv_count += len(left) - i #left[i~mid)都比right[j]要大，他们都会与right[j]构成逆序对，将他们加入答案

    # If there are remaining elements in the left or right half, append them to the result.
    merged += left[i:]
    merged += right[j:]

    return merged, inv_count

while True:
    n = int(input())
    if n == 0:
        break

    lst = []
    for _ in range(n):
        lst.append(int(input()))

    _, inversions = merge_sort(lst)
    print(inversions)

卢卓然-23-生命科学学院，思路：

Ultra-QuickSort题目使用的排序方法是归并排序（本题解答是基于归并排序的解法，用其他解法如冒泡排序时间复杂度较高）。在归并排序中，将序列递归地分为左右两半，分别排序后再合并到一起。在归并排序中，合并函数的书写是重点，也是本题关注的点。在两个有序序列进行合并的过程中，若通过交换两个相邻数字的位置来实现合并，一共需要交换多少次，就是本题需要解决的问题。

以下是归并排序（mergesort）的代码。merge(arr,l,m,r)函数是合并两个有序序列的函数。函数的主体是三个while。第一个while运用双指针法，是对两个序列的合并，涉及到了元素位置的改变。第二、三个while是简单地将L1或L2中的剩余有序元素复制到arr队尾，并不涉及到元素位置的改变。所以只需关注第一个while的内容。

现在来分析用双指针法合并两个有序序列时，与其（复杂度上）等效的交换相邻数字的方法是怎样实现的。在双指针法中，是将 L1[i]和L2[j]中更小的一个放在arr的k处，在两个指针逐渐变大的过程中，将合并后的递增序列覆盖在arr的一段上。这种方法相对交换相邻数字，无疑很节省时间复杂度。交换相邻数字，关心的只是数字之间的相对位置，而不是绝对位置。所以可以假定这样的规则：当L1[i]<=L2[j]时，不改变数字的相对位置；当L1[i]>L2[j]时，将L2[j]通过不断换位向前移动，从而“插入”到L1[i]的前面一个位置。

那么L2[j]需要换多少次才能达到L1[i]前面呢？想象用交换位置法得到新序列的过程，那么在L2[j]动身之前，L2中所有L2[j]之前的元素已经全部跑到了L1[i]的左边，并且与L1中L1[i]左边的元素组成了递增序列。L2[j]的“目的地”就是这个已组成的递增序列和L1[i]之间的位置。L2和目的地之间相隔的元素，也就是L1中L1[i]及其之后的元素，其数量为n1-i（n1为原L1的长度）。所以在这一步中，交换的次数为d+=(n1-i)。

随着递归的进行，每一次合并中d不断累加，最终就可以得到总交换次数。

python

import sys
sys.setrecursionlimit(100000)
d=0
def merge(arr,l,m,r):
    '''对l到m和m到r两段进行合并'''
    global d
    n1=m-l+1#L1长
    n2=r-m#L2长
    L1=arr[l:m+1]
    L2=arr[m+1:r+1]
    ''' L1和L2均为有序序列'''
    i,j,k=0,0,l#i为L1指针，j为L2指针，k为arr指针
    '''双指针法合并序列'''
    while i<n1 and j<n2:
        if L1[i]<=L2[j]:
            arr[k]=L1[i]
            i+=1
        else:
            arr[k]=L2[j]
            d+=(n1-i)#精髓所在
            j+=1
        k+=1
    while i<n1:
        arr[k]=L1[i]
        i+=1
        k+=1
    while j<n2:
        arr[k]=L2[j]
        j+=1
        k+=1
def mergesort(arr,l,r):
    '''对arr的l到r一段进行排序'''
    if l<r:#递归结束条件，很重要
        m=(l+r)//2
        mergesort(arr,l,m)
        mergesort(arr,m+1,r)
        merge(arr,l,m,r)
results=[]
while True:
    n=int(input())#序列长
    if n==0:
        break
    array=[]
    for b in range(n):
        array.append(int(input()))
    d=0
    mergesort(array,0,n-1)
    results.append(d)
for r in results:
    print(r)

02299: Ultra-QuickSort ​

02299: Ultra-QuickSort