java实现快速排序

分别采用双边循环法和单边循环法实现快速排序

public class QuickSort {

    /**
     * 双边循环法实现快速排序
     * @param arrays 待排序数组
     * @param left 需要排序数据左指针下标
     * @param right 需要排序数据右指针下标
     */
    public static void quickSort(int[] arrays,int left,int right){
        if (left >= right){
            return;
        }
        //交换数据，返回排序后，基数pivot所在下标，并以此下标的边界将数组分成左右两部分
        int pivotIndex = partition(arrays,left,right);
        //递归排序左侧数据，以上一次基数pivot下标pivotIndex-1为边界
        quickSort(arrays,left,pivotIndex - 1);
        //递归排序右侧数据，以上一次基数pivot下标pivotIndex+1为边界
        quickSort(arrays,pivotIndex + 1,right);
    }

    /**
     *双边循环法实现快速排序数据交换方法
     * @param arrays 待排序数组
     * @param left 需要排序数据左指针下标
     * @param right 需要排序数据右指针下标
     * @return 返回数组左侧需要排序数据的右边界
     */
    private static int partition(int[] arrays,int left,int right){
        //基数下标
        int pivot = left;
        //遍历需要排序数据，并交换数据
        while (left < right){
            //右指针right大于等于基数pivot时，右指针right左移。
            while (left != right && arrays[right] >=arrays[pivot]){
                --right;
            }
            //左指针left小于等于基数pivot时，左指针left右移。
            while (left != right && arrays[left] <= arrays[pivot]){
                ++left;
            }
            //左右指针后，且左指针left下标不等于右指针right下标时，交换左右指针所在位置的值
            if (left != right){
                int temp = arrays[right];
                arrays[right] = arrays[left];
                arrays[left] = temp;
            }
        }
        //将左指针指向的值与基数pivot交换
        int temp = arrays[left];
        arrays[left] = arrays[pivot];
        arrays[pivot] = temp;

        return left;
    }

    /**
     * 单边循环阀实现快速排序
     * @param arrays 待排序数组
     * @param leftBorder 左边界下标，同时也是基准元素的下标
     * @param rightBorder 右边界下标
     */
    public static void quickSortV2(int[] arrays,int leftBorder,int rightBorder){
        if (leftBorder >= rightBorder){
            return;
        }
        //调用数据交换方法并返回mark下标
        int mark = partitionV2(arrays,leftBorder,rightBorder);

        //递归排序mark左侧数据，以上一次小于基准元素的区域边界下标mark-1为右边界
        quickSortV2(arrays,leftBorder,mark-1);
        //递归排序mark右侧数据，以上一次小于基准元素的区域边界下标mark+1为左边界
        quickSortV2(arrays,mark+1,rightBorder);
    }

    /**
     * 单边循环阀实现快速排序的数据交换方法
     * @param arrays 待排序数组
     * @param leftBorder 左边界下标，同时也是基准元素的下标
     * @param rightBorder 右边界下标
     * @return 返回小于基准元素的区域边界下标mark
     */
    private static int partitionV2(int[] arrays,int leftBorder,int rightBorder){

        //小于基准元素的区域边界下标
        int mark = leftBorder;
        //从需要排序数据的左边界leftBorder+1开始遍历
        for (int i = leftBorder+1;i <= rightBorder;i++){
            if (arrays[i] < arrays[leftBorder] ){
                //mark右移，然后交换mark和当前遍历访问的值
                int temp = arrays[i];
                arrays[i] = arrays[++mark];
                arrays[mark] = temp;
            }
        }
        //交换基准元素和mark下标指向的值
        int temp = arrays[leftBorder];
        arrays[leftBorder] = arrays[mark];
        arrays[mark] = temp;
        //返回mark下标
        return mark;
    }

   

    public static void main(String[] args) {
        int[] arrays1 = new int[]{4,4,11,6,5,3,2,8,1,9,7,13};
        quickSort(arrays1,0,arrays1.length-1);
        System.out.println(Arrays.toString(arrays1));
        System.out.println("--------------------------------------------------------------------");
        int[] arrays2 = new int[]{4,4,11,6,5,3,2,8,1,9,7,13};
        quickSortV2(arrays2,0,arrays2.length-1);
        System.out.println(Arrays.toString(arrays2));
        /*
         * [1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 11, 13]
         * --------------------------------------------------------------------
         * [1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 11, 13]
         */
    }
}