算法之快速排序5非递归实现

一：概述

绝大多数的递归逻辑都可以利用栈的方式去代替。代码中一层一层的方法调用，本身就是使用一个方法调用栈。每次进入一个新的方法，就相当于入栈。每次有方法返回就相当于出栈。

所以，可以把原本的递归实现转换成一个栈的实现，在栈中存储每一次方法调用的参数。

二：具体代码实现

/*
  非递归实现快速排序
 */
public class Sort6 {
      public static void quickSort(int[] arr, int startIndex,int endIndex) {
          // 用一个集合栈来代替递归的函数栈
          Stack<Map<String, Integer>> quickSortStack = new Stack<Map<String, Integer>>();

          // 整个数列的起止下标，以哈希的形式入栈
          Map rootParam = new HashMap();
          rootParam.put("startIndex", startIndex);
          rootParam.put("endIndex", endIndex);
          quickSortStack.push(rootParam);

          // 循环结束条件：栈为空时
          while(!quickSortStack.isEmpty()) {
              // 栈顶元素出栈，得到起止下标
              Map<String, Integer> param = quickSortStack.pop();
              // 得到基准元素位置
              int pivotIndex = partition(arr, param.get("startIndex"),param.get("endIndex"));
              // 根据基准元素分成两个部分，把每一部分的起止下标入栈
              if(param.get("startIndex") < pivotIndex - 1) {
                  Map<String, Integer> leftParam = new HashMap<String, Integer>();
                  leftParam.put("startIndex", param.get("startIndex"));
                  leftParam.put("endIndex", pivotIndex);
              }
              if(pivotIndex + 1 < param.get("endIndex")) {
                  Map<String, Integer> rightParam = new HashMap<String,Integer>();
                  rightParam.put("startIndex", pivotIndex + 1);
                  rightParam.put("endIndex", param.get("endIndex"));
                  quickSortStack.push(rightParam);

              }



          }
      }

     public static int partition(int[] arr, int startIndex, int endIndex)
     {
         // 取第1个位置(也可以选择随机位置)的元素作为基准元素
         int pivot = arr[startIndex];
         int mark = startIndex;

         for(int i = startIndex + 1; i <  endIndex;i++) {
             if(arr[i] < pivot) {
                 mark ++;
                 int p = arr[mark];
                 arr[mark] = arr[i];
                 arr[i] = p;
             }
         }

         arr[startIndex] = arr[mark];
         arr[mark] = pivot;
         return mark;

     }


public static void main(String[] args) {
    int[] arr = new int[] {4, 7, 6, 5, 4, 3, 2, 8, 1};
    quickSort(arr, 0 ,arr.length - 1);
    System.out.println(Arrays.toString(arr));
      }


}

和之前的递归相比非递归的方式代码变动只发生在quickSort中。该方法引入了一个存储Map类型元素的栈，用于存储每一次交换的起始下标和结束下标。

每一次循环，都会让栈顶的元素出栈，通过partition方法进行分治，并且按照基准元素的位置分成左右两个部分，左右两个部分再分别入栈。当栈为空时，说明排序已经完毕。