排序算法之快速排序-java篇

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

/**
 * @Author: 张
 * @Date: 2019/1/30 10:46
 * @Version: 1.0
 * @Description: 1.0
 */
public class QuickSortTest {

    public static int partion(int[] arr, int left, int right) {
        int partition = arr[right];
        int j = left;
        for (int i = left; i < right;i++) {
            if (arr[i] <= partition) {
                swap(arr, i, j++);
            }
        }
        swap(arr, j, right);
        for(int ai : arr){
            System.out.print(ai + ",");
        }
        System.out.println("j:" + j);
        return j;
    }

    public static int[] quickSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = partion(array, left, right);
            quickSort(array, left, mid - 1);
            quickSort(array, mid + 1, right);
        }
        return array;
    }

    public static void swap(int[] arr, int i, int j) {
        int ai = arr[i];
        arr[i] = arr[j];
        arr[j] = ai;
    }

    public static void main(String[] args){
        int[] array = new int[]{1, 2, 0, 4, 9, 6, 5, 3};
        int left = 0;
        int right = array.length - 1;
        int[] arr = array.clone();
        int[] arr2 = quickSort(arr,left,right);

        for(int ai : arr2){
            System.out.print("最终结果：" +ai + ",");
        }
    }
}