是否可以使用快速排序来计算计数反转的次数？

Question

我已经使用归并排序解决了问题，现在我在想是否可以使用快速排序来计算数字？我也编写了快速排序的代码，但我不知道如何计算。这是我的代码：

def Merge_and_Count(AL, AR):
    count=0
    i = 0
    j = 0
    A = []
    for index in range(0, len(AL) + len(AR)):        
        if i<len(AL) and j<len(AR):
            if AL[i] > AR[j]:
                A.append(AR[j])
                j = j + 1
                count = count+len(AL) - i
            else:
                A.append(AL[i])
                i = i + 1
        elif i<len(AL):
            A.append(AL[i])
            i=i+1
        elif j<len(AR):
            A.append(AR[j])
            j=j+1
    return(count,A)

def Sort_and_Count(Arrays):
        if len(Arrays)==1:
            return (0,Arrays)
        list1=Arrays[:len(Arrays) // 2]
        list2=Arrays[len(Arrays) // 2:]
        (LN,list1) = Sort_and_Count(list1)
        (RN,list2) = Sort_and_Count(list2)
        (M,Arrays)= Merge_and_Count(list1,list2)
        return (LN + RN + M,Arrays)

Answer 1

通常不会，因为在分区过程中，当您将一个值移动到枢轴的正确一侧时，您不知道有多少个值比它小，有多少个比它大。因此，一旦您这样做，您就会丢失有关原始输入中反转次数的信息。

Answer 2

这个问题我也遇到过好几次了，总体来说，我觉得用快速排序来计算倒排计数应该还是可以的，只要我们对原来的快速排序算法做一些修改即可。 （但我还没有验证过，抱歉）。

考虑一个数组

3, 6, 2, 5, 4, 1

。支持我们使用

3

作为枢轴，投票最多的答案是正确的，因为交易所可能会打乱其他数字的顺序。但是，我们可以通过引入一个新的临时数组来做到不同：

1. 第一次迭代数组。迭代过程中，将所有小于

   3

   的数字移动到临时数组中。对于每个这样的数字，我们还记录它之前有多少个比

   3

   大的数字。在这种情况下，数字

   2

   前面有 1 个数字

   6

   ，数字

   1

   前面有 3 个数字

   6, 5, 4

   。这可以通过简单的计数来完成。
2. 然后我们将

   3

   复制到临时数组中。
3. 然后我们再次迭代数组，将大于 3 的数字移到临时数组中。最后我们得到了

   2 1 3 6 5 4

   。

问题是在这个过程中丢失了多少反演对？该数字是第一步中所有数字的总和，以及第二步中小于主元的数字的个数。然后我们计算所有反转数，其中一个是 >= 枢轴，另一个是 < pivot. Then we could recursively deal with the left part and the right part.

Answer 3

@Yun Gau给出的解决方案是正确的，这是我实现的代码：

fn calc_inversions_quick_sort(vec: &[usize]) -> usize {
    fn partition_count(vec: &mut [usize], low: usize, high: usize) -> (usize, usize) {
        let pivot = vec[low];
        let ind_len = high - low + 1;
        let mut i = low;
        let mut count = 0;
        let mut small_ind = Vec::with_capacity(ind_len);
        let mut big_ind = Vec::with_capacity(ind_len);
        let old_v = vec.to_vec();
        for j in low + 1..=high {
            if vec[j] < pivot {
                count += j - i;
                small_ind.push(j);
                i += 1;
            } else {
                big_ind.push(j);
            }
        }
        let perm = [small_ind, vec![low], big_ind].concat();
        for (ind, p) in perm.iter().enumerate() {
            vec[low + ind] = old_v[*p];
        }

        (i, count)
    }
    fn quick_sort_count(vec: &mut [usize], low: usize, high: usize) -> usize {
        let mut res = 0;
        if low < high {
            let (pos, count) = partition_count(vec, low, high);
            res += count;
            if pos > low + 1 {
                res += quick_sort_count(vec, low, pos - 1);
            }
            if high > pos + 1 {
                res += quick_sort_count(vec, pos + 1, high);
            }
        }
        res
    }

    let mut v = vec.to_vec();
    let len = vec.len();
    quick_sort_count(&mut v, 0, len - 1)
}