hymn

快速排序：

在每一轮挑选一个基准元素，并让其他比他大的移动到一边，比他小的移动到另一边，从而把数组拆解成两个部分。这种思路叫做分治法。

时间复杂度：O(nlogn)

package sort;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author: daixyhymn
 * @description: 快排
 * @date: 2020/11/4 14:50
 */
public class QuickSort {

  /**
   * 快排
   * @param array
   * @param startIndex
   * @param endIndex
   */
  public static void quickSort(int[] array, int startIndex, int endIndex){
    // 递归条件结束： startIndex 大于 endIndex
    if (startIndex >= endIndex) {
      return;
    }
    // 得到基准元素，分成两部分进行递归
    int pivotIndex = partition2(array, startIndex, endIndex);

    // 根据基准元素，分成两部分进行递归
    quickSort(array, startIndex, pivotIndex - 1);
    quickSort(array, pivotIndex + 1, endIndex);
  }

  /**
   * 用栈的形式
   * @param array
   * @param startIndex
   * @param endIndex
   */
  public static void quickSortStack(int[] array, int startIndex, int endIndex){
    // 用一个集合栈来代替递归的函数栈
    Stack<Map<String, Integer>> quickStack = new Stack<>();
    // 整个数列的气质下标，以哈希的形式入栈
    Map rootParam = new HashMap();
    rootParam.put("startIndex", startIndex);
    rootParam.put("endIndex", endIndex);
    quickStack.push(rootParam);

    // 循环结束条件：栈为空时
    while (!quickStack.isEmpty()) {
      // 栈顶出栈，得到起止下标
      Map<String, Integer> param = quickStack.pop();
      // 得到基准元素位置
      int pivotIndex = partition(array, param.get("startIndex"), param.get("endIndex"));

      // 根据基准元素位置分成两个部分，把每一部分的起止下标入栈
      if (param.get("startIndex") < pivotIndex -1) {
        Map<String, Integer> leftParam = new HashMap<>();
        leftParam.put("startIndex", param.get("startIndex"));
        leftParam.put("endIndex", pivotIndex -1);
        quickStack.push(leftParam);
      }

      if (pivotIndex + 1 <  param.get("endIndex")) {
        Map<String, Integer> rightParam = new HashMap<>();
        rightParam.put("startIndex", pivotIndex + 1);
        rightParam.put("endIndex", param.get("endIndex"));
        quickStack.push(rightParam);
      }
    }
  }

  /**
   * 双边循环法
   * @param array
   * @param startIndex
   * @param endIndex
   * @return
   */
  public static int partition2(int[] array, int startIndex, int endIndex){
    // 取第一个 位置（也可以随机位置）的元素作为基准元素
    int pivot = array[startIndex];
    int left = startIndex;
    int right = endIndex;

    while (left < right) {
      while (left < right && array[right] > pivot) {
        right--;
      }
      while (left < right && array[left] <= pivot) {
        left++;
      }
      if (left < right) {
        int p = array[left];
        array[left] = array[right];
        array[right] = p;
      }
    }
    // pivot 和指针重合点交换
    array[startIndex] = array[left];
    array[left] = pivot;

    return left;
  }

  /**
   * 单边循环法
   * @param array
   * @param startIndex
   * @param endIndex
   * @return
   */
  public static int partition(int[] array, int startIndex, int endIndex){
    int pivot = array[startIndex];
    int mark = startIndex;

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

  public static void main(String[] args) {
    int[] array = new int[]{4,5,1,6,5,9,2,0};
    quickSortStack(array, 0, array.length -1);
    System.out.println(Arrays.toString(array));
  }
}