关于三路快排循环体内的swap次数

Question

老师你好，我在本地测试了近乎有序且无重复元素的测试用例下三路快排的循环体内的swap次数（不计算每次开头的随机交换以及最后的交换），次数均等于数组长度，这应该不是巧合吧？

Answer 1

liuyubobobo 2018-10-26 15:00:30

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

------

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

// 对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)的算法，所以数组过大的话，交换次数很容易整型溢出：）

加油！：）

• 提问者 幻幻梨 #1

  测试用例是按照老师的算法生成的近乎有序数组
      public static int  sort3(Integer[] arr,int l,int r,int k){
          if (l >= r){
              return k;
          }
  
          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){
                  SortTestHelper.swap(i,--gt,arr);
                  k++;
              }
              else if(arr[i] < v){
                  SortTestHelper.swap(i,++lt,arr);
                  k++;
                  i++;
              }
              else{
                  i++;
              }
          }
          SortTestHelper.swap(l,lt,arr);
  
          sort3(arr,l,lt-1,k);
          sort3(arr,gt,r,k);
          return k;
      }
  用k记录交换次数

• 提问者 幻幻梨 #2

  额，不能截图，我就贴文本了，不知道为什么换行就没了，我再贴一个

• liuyubobobo 回复 提问者 幻幻梨 #3

  我在原答案上进行了补充。加油！：）

点开查看后面1条评论