非递归随机快排

之前写过递归形式的随机快排，但是发现效率并不理想，今天正好复习算法，就索性将递归的改为非递归的。

任何递归形式的方法都是系统压栈的，而我们可以自己压栈，也就是说所有的递归都可以改为非递归方法。

同样，先放出荷兰国旗问题：懂了这个才有学习快排的基础

递归形式的快排就不写了，可以参考这个，虽然写的不怎么详细：

说白了，思路就是自己压栈，不过最好先看懂递归的，自己创建一个栈，然后partition的结果是返回数组的左边界，等于区域的两个边界，以及数组的有边界。将这个数据压进栈中，退出整个过程的条件就是栈不为空，进入while之后，先将栈顶的数组拿出来，如果这个数组的左边界<右边界，才可以继续进行partition，然后这个partition的过程又分为做部分的partition，和右部分的partition，这两个部分的partition同样都需要先判断是否左边界<右边界，否则直接舍弃这次partition。当栈为空的时候，整个过程结束。

我是用了比较器的思想来进行验证自己的算法的正确与否的，数据量设定为 100,0000，这样的数据量足返回true，足以证明是正确的了。

下面看代码，过程中使用到了自己写的工具类，放到最后面：

/**
 * 非递归随机快排
 * @author BarryLee
 * @2018年8月16日@上午10:42:30
 */
public class _03quicksort {
  public void quicksort(int[]arr) {
    if(arr==null || arr.length<2) {
      return;
    }
    process(arr, 0, arr.length-1);
  }
  public void process(int[]arr,int left,int right) {
    if(left<right) {
      Stack<Integer[]>stack = new Stack<>();
      Random r = new Random();
      Utils.swap(arr, r.nextInt(right-left+1)+left, right);
      stack.push(partition(arr, left, right, arr[right]));
      while(!stack.isEmpty()) {
        Integer[]pro = stack.pop();
        if(pro[0]<pro[3]) {
          if(pro[0]<pro[1]) {
            Utils.swap(arr, r.nextInt((pro[1]-1)-pro[0]+1)+pro[0], pro[1]-1);
            stack.push(partition(arr, pro[0], pro[1]-1, arr[pro[1]-1]));
          }
          if(pro[2]<pro[3]) {
            Utils.swap(arr, r.nextInt(pro[3]-(pro[2]+1)+1)+pro[2]+1, pro[3]);
            stack.push(partition(arr, pro[2]+1, pro[3], arr[pro[3]]));
          }
        }
      }
    }
  }
  public Integer[] partition(int[]arr,int left,int right,int num) {
    int i = left;
    int less = left-1;
    int more = right;
    while(i<more) {
      if(arr[i]<num) {
        Utils.swap(arr, i++, ++less);
      }else if(arr[i]>num) {
        Utils.swap(arr, i, --more);
      }else {
        i++;
      }
    }
    Utils.swap(arr, more, right);
    return new Integer[] {left,less+1,more,right};
  }
  
  //测试 - 1000000数据测试
  @Test
  public void testQuickSort() {
    for(int i = 0;i<1000000;i++) {
      int[]arr1 = Utils.randomArr(30, 50);
      int[]arr2 = Utils.copyArr(arr1);
      quicksort(arr1);
      Arrays.sort(arr2);
      if(!Utils.isEqual(arr1, arr2)) {
        System.out.println(false);
        Utils.printArr(arr1);
        Utils.printArr(arr2);
        return ;
      }
    }
    System.out.println(true);
  }
  
}

public class Utils {
  /**
   * 交换两个数
   * @param arr
   * @param i
   * @param j
   */
  public static void swap(int[] arr,int i,int j){
    if(arr[i]==arr[j])return;
    arr[i] = arr[i]^arr[j];
    arr[j] = arr[i]^arr[j];
    arr[i] = arr[i]^arr[j]; 
  }
  
  /**
   * 打印一维数组
   * @param arr
   */
  public static void printArr(int[]arr) {
    for (int i : arr) {
      System.out.print(i+" ");
    }
    System.out.println();
  }
  /**
   * 打印一维数组
   * @param arr
   */
  public static void printArr(Integer[]arr) {
    for (Integer i : arr) {
      System.out.print(i+" ");
    }
    System.out.println();
  }
  
  /**
   * 打印二维数组
   * @param arr
   */
  public static void printArr(int[][]arr) {
    for (int[] is : arr) {
      for (int i : is) {
        System.out.print(i+" ");
      }
      System.out.println();
    }
    System.out.println();
  }
  
  /**
   * 生成一个一维随机数组
   * @param len
   * @param val
   * @return
   */
  public static int[] randomArr(int len ,int val){
    int arr[] = new int[len];
    for (int i = 0; i < arr.length; i++) {
      arr[i] = (int)(val*Math.random()-val*Math.random()); 
    }
    return arr;
  }

  /**
   * 判断两个数组是否相等
   * @param arr1
   * @param arr2
   * @return
   */
  public static boolean isEqual(int arr1[], int arr2[]) {
    if (arr1 == null || arr2 == null || arr1.length == 0 || arr2.length == 0 || arr1.length != arr2.length) {
      return false;
    }
    for (int i = 0; i < arr2.length; i++) {
      if (arr1[i] != arr2[i]) {
        return false;
      }
    }
    return true;
  }
  
  public static int[] copyArr(int[]arr) {
    if(arr==null || arr.length==0) {
      return new int[] {};
    }
    int[]arr2 = new int[arr.length];
    for(int i = 0;i<arr.length;i++) {
      arr2[i] = arr[i];
    }
    return arr2;
  }
}

--------------------------假装有分割线(2018.10.2)----------------------------------

下面是我今天改版的随机快排，代码稍微简洁了一些，看起来，舒服，思路是我想要的那种

package sort;

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

import org.junit.Test;

import pubs.MyUtils;

/*
 * 随机快排 - 非递归版
 */
public class QuickSort2 {
  public static void quickSort(int[]arr) {
    if(null==arr || arr.length<2) {
      return;
    }
    process(arr,0,arr.length-1);
  }

  private static void process(int[] arr, int left, int right) {
    if(left<right) {
      Stack<int[]>stack = new Stack<>();
      stack.push(partition(arr, left, right));
      while(!stack.isEmpty()) {
        int[]p = stack.pop();
        if(p[0]<p[1]-1) {//不能是p[0]+1<p[1]-1，因为p[0]是left，还没排好序
          stack.push(partition(arr, p[0],p[1]-1));
        }
        if(p[2]+1<p[3]) {
          stack.push(partition(arr, p[2]+1, p[3]));
        }
      }
    }
  }
  private static int[] partition(int[]arr ,int left,int right) {
    int n = arr[new Random().nextInt(right-left)+left];
    int less = left-1;
    int more = right+1;
    int i = left;
    while(i<more) {
      if(arr[i]>n) {
        MyUtils.swap(arr, i, --more);
      }else if(arr[i]<n) {
        MyUtils.swap(arr, i++, ++less);
      }else {
        i++;
      }
    }
    return new int[] {left,less+1,i-1,right};
  }
  @Test
  public void test() {
    boolean isTrue = true;
    for(int i = 0;i<100000;i++) {
      int[]arr1 = MyUtils.randomArr(100, 30);
      int[]arr2 = MyUtils.copyArr(arr1);
      quickSort(arr1);
      Arrays.sort(arr2);
      if(!MyUtils.isEqual(arr1, arr2)) {
        isTrue = false;
        MyUtils.printArr(arr2);
        MyUtils.printArr(arr1);
        break;
      }
    }
    System.out.println(isTrue);
  }
}