快速排序（Java递归实现）

快速排序：
在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列另一边，从而把数列拆解成两个部分。

代码实现：
基于双边循环法实现的快速排序，代码使用了递归的方式。

import java.util.Arrays;

/**
 * @author lizz
 * @ClassName QuickSort.java
 * @Description 快速排序
 * @createTime 2022年04月22日 09:39:00
 */
public class QuickSort {

    /**
     * 基于递归实现快速排序
     * @param array  要排序的数组
     * @param startIndex 开始下标
     * @param endIndex 结束下标
     */
    public void sort(int[] array,int startIndex,int endIndex){
        // 递归结束条件：开始下标大于或等于结束下标
        if(startIndex >= endIndex){
            return;
        }

        //得到基准元素的位置
        int pivotIndex = partition(array,startIndex,endIndex);
        //根据基准元素，分成两部分进行递归排序
        sort(array,startIndex,pivotIndex-1);
        sort(array,pivotIndex+1,endIndex);

    }

    /**
     * 分治（双边循环法）
     * @param array  待交换的数组
     * @param startIndex 开始下标
     * @param endIndex 结束下标
     * @return
     */
    public int partition(int[] array,int startIndex,int endIndex){
        // 取第一个元素作为基准元素（可以随机选择）
        int pivot = array[startIndex];
        int left = startIndex;
        int right = endIndex;
        while (left != right){
            //控制right指针比较并左移
            while(left < right  && array[right]> pivot){
                right--;
            }
            //控制left指针比较并右移
            while (left < right && array[left] <= pivot){
                left++;
            }
            //交换left和right指针所指向的元素
            if(left < right){
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
        }
        // pivot和指针重合点交换
        array[startIndex] = array[left];
        array[left] = pivot;

        return left;
    }

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

补充一下单边循环：

 /**
     * 分治（单边循环法）
     * @param array  待交换的数组
     * @param startIndex 开始下标
     * @param endIndex 结束下标
     * @return
     */
    public int partition(int[] array,int startIndex,int endIndex){
        // 取第一个元素作为基准元素（可以随机选择）
        int pivot = array[startIndex];
        //mark 标识小于基准元素的区域边界
        int mark = startIndex;
        /*
            如果元素大于基准元素，就继续遍历
            如果元素小于基准元素：
                1：mark指针右移一位，因为小于pivot的区域增大了一个。
                2：最新遍历到的元素和mark指针所指在的元素交换位置，因为最新遍历的元素归属于小于pivot的区域。
         */
        for (int i = startIndex+1; i<= endIndex ; i++) {
            //此时遍历到的元素小于基准元素
            if(array[i] < pivot){
                mark++;
                int temp = array[mark];
                array[mark] = array[i];
                array[i] = temp;
            }
        }

        //将pivot元素交换到mark指针所在的位置，这一轮交换结束
        array[startIndex] = array[mark];
        array[mark] = pivot;

        return mark;
    }