运用递归实现快速排序算法（二分排序）

快速排序算法

首先了解什么是哨兵排序，哨兵排序就是找到一个基准将整个数组按照基准分成前半段比基准小，后半段比基准大分成两组。之后将这两组分别继续递归执行哨兵排序，直到 l >= r 达到递归终点，完成排序。 具体的动画流程可以登陆：网站查看。

import org.junit.Test;

public class erfenPaixu {
          
   
    /**
     * 首先调用哨兵方法之后在使用递归的方法循环将基准左边部分和右边部分排序
     * ，直到达到递归出口l = r为止。
     * @param nums
     * @param l
     * @param r
     */
    void erfen(int[] nums, int l, int r) {
          
   
        if (l >= r) return;
        int i = shaobing(nums, l, r);
        erfen(nums, l, i - 1);
        erfen(nums, i + 1, r);
    }

    /**
     * 利用哨兵划分将数组根据基准分为两半
     *
     * @param nums
     * @param l 初始状态左边的索引
     * @param r 初始状态右边的索引
     * @return 返回一个i的边界值
     */
    int shaobing(int[] nums, int l, int r) {
          
   
        //i 为 l的初始状态，j 为 r的初始状态
        int i = l;
        int j = r;
        while (i < j) {
          
   
            //i从左往右找大于基准的第一个数，j从右往左找小于基准的第一个数，把他俩交换
            //继续从当前位置的i，j继续循环查找，直到 i = j 将 i = j 所在位置与基准交换
            while (i < j && nums[j] >= nums[l]) j--;
            while (i < j && nums[i] <= nums[l]) i++;
            swap(nums, i, j);
        }
        swap(nums, i, l);
        return i;
    }

    /**
     * 交换数组中的元素
     *
     * @param nums 数组
     * @param i
     * @param j
     */
    public void swap(int[] nums, int i, int j) {
          
   
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    @Test
    public void test() {
          
   
        int nums[] = {
          
   8, 2, 11, 9, 1, 5, 3};
        erfen(nums, 0, nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
          
   
            System.out.print(nums[i] + ",");
        }
    }
}