1回答

liuyubobobo

2018-10-26

已采纳

具体你是怎么测试的？测试用例是怎么生成的？

------

你的计算交换次数的代码有误，递归的写法应该是这样的。（基于你的代码进行的修改。）

// 对arr[l...r]进行三路快排，返回排序过程中的交换次数
private static int sort3(Integer[] arr,int l,int r){
    
    int swapTime = 0;
    if (l >= r)
        return swapTime; // 不需要排序，直接返回0
        
    int i = l+1; //用来遍历数组
    int lt = l; //[l+1...lt]里的元素均小于V
    int gt = r+1; //[lt..gt]里的元素均大于v,[lt+1...i）里的元素均等于v
    int v = arr[l];
    while(i < gt){
        if(arr[i] > v){
            swap(arr,i,--gt);
            swapTime++; // 添加交换次数
        }
        else if(arr[i] < v){
            swap(arr,i,++lt);
            swapTime++; // 添加交换次数
            i++;
        } else{
            i++;
        }
    }
    swap(arr,l,lt);
    swapTime ++; // 添加交换次数
    
    swapTime += sort3(arr,l,lt-1); // 添加上左边进行三路快排的交换次数
    swapTime += sort3(arr,gt,r); // 添加上右边进行三路快跑的交换次数
    return swapTime;
}

public static void sort3(Integer[] arr){

    int n = arr.length;
    int swapTime = sort3(arr, 0, n-1);
    System.out.println(swapTime);
}

你的写法，递归调用sort3的时候，把k传进去，但是k在本层递归函数中没有改变。所以后续的递归调用的交换次数根本没有计算！你返回的只是一层的交换次数。可以用一个小样本（5-10个数据）debug跟踪一下，理解一下你的代码问题出在哪里：）

由于对于近乎有序的数据，对于你的写法（没有使用随机化），每次if(arr[i] > v)近乎都成立，所以，最终返回的交换次数基本等于数组长度。

另外，比较简单的逻辑方式是在类中设置一个变量（相当于全局变量）来统计交换次数：）

我是使用如下代码来验证的我的递归算法的正确性：）

private static void sort4(Integer[] arr,int l,int r){
    if (l >= r)
        return;
    int i = l+1; //用来遍历数组
    int lt = l; //[l+1...lt]里的元素均小于V
    int gt = r+1; //[lt..gt]里的元素均大于v,[lt+1...i）里的元素均等于v
    int v = arr[l];
    while(i < gt){
        if(arr[i] > v){
            swap(arr,i,--gt);
            k++; // k是类中的静态成员变量，见后定义
        }
        else if(arr[i] < v){
            swap(arr,i,++lt);
            k++; // k是类中的静态成员变量，见后定义
            i++;
        } else{
            i++;
        }
    }
    swap(arr,l,lt);
    k ++; // k是类中的静态成员变量，见后定义
    
    sort4(arr,l,lt-1);
    sort4(arr,gt,r);
    return;
}

static int k; // 静态成员变量k，记录交换次数
public static void sort4(Integer[] arr){
    k = 0; // 初始化k为0
    int n = arr.length;
    sort4(arr, 0, n-1);
    System.out.println(k);
}

注意：在你的写法下（没有使用随机化），三路快排也将退化成O(n^2)的算法，所以数组过大的话，交换次数很容易整型溢出：）

加油！：）

0

4

幻幻梨

回复

liuyubobobo

明白了，谢谢老师！

2018-11-20

共4条回复