快速排序的递归和非递归实现

排序算法中很重要的快速排序

递归实现方式

递归实现方式的不同在于分区函数的不同

    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        //分区函数获取基准元素位置
        int pivotIndex = singleParition(arr, startIndex, endIndex);

        //分治递归
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

• 双向循环指针式，原理是利用左右指针分别维护较大数以及较小数区间

    private static int partition(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex]; //使用第一个值作为基准值
        int left = startIndex; //左指针
        int right = endIndex; //右指针
    
         //当两指针不重合时循环
        while (left != right) {
            //当右指针大于基准值的时候指针左移
            while (left < right && arr[right] > pivot) {
                right--;
            }
            //当左指针小于基准值的时候指针右移
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //交换左右指针
            if (left < right) {
                swap(arr, left, right);
            }
        }
      
        //交换基准元素值和左/右指针
        arr[startIndex] = arr[left];
        arr[left] = pivot;

        return left;
    }

• 单项循环指针式，使用单指针来区分较大和较小区域

    //单边循环分边函数,从小到大依次遍历，若小于基准值，则mark指针向右移动，
    //并且让移动后的mark指针当前遍历值互换，最后遍历结束互换mark和基准指针值，并返回mark指针位置
    private static int singleParition(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];
        int mark = startIndex;
        for (int i = startIndex; i <= endIndex; i++) {
            //若值比基准指针小则mark指针左移然后和该值交换
            if (arr[i] < pivot) {
                swap(arr, i, ++mark);
            }
        }
          //交换mark指针的基准值
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }

非递归实现方式

非递归实现方式主要借用了栈的数据结构，来完成递归操作，这里的分区函数和递归的一致

    public static void nonRecursiveQuickSort(int[] arr, int startIndex, int endIndex) {
  //初始化栈
        Stack<Map<String, Integer>> quickSortStack = new Stack<>();
        HashMap<String, Integer> paramMap = Maps.newHashMap();
        paramMap.put("startIndex", startIndex);
        paramMap.put("endIndex", endIndex);

        quickSortStack.push(paramMap);

        //栈不空
        while (!quickSortStack.isEmpty()) {
            Map<String, Integer> map = quickSortStack.pop();
            //从Map中获取对应属性值来获取基准点
            int pivot = singleParition(arr, map.get("startIndex"), map.get("endIndex"));
            if (map.get("startIndex") < pivot - 1) {
            //入栈模拟调用递归方法
                HashMap<String, Integer> left = Maps.newHashMap();
                left.put("startIndex", map.get("startIndex"));
                left.put("endIndex", pivot - 1);
                quickSortStack.push(left);

            }
            if (map.get("endIndex") > pivot + 1) {
                HashMap<String, Integer> right = Maps.newHashMap();
                right.put("endIndex", map.get("endIndex"));
                right.put("startIndex", pivot + 1);
                quickSortStack.push(right);

            }
        }
    }