java实现快速排序算法

快速排序算法

快速排序算法：快速排序算法是对冒泡排序算法的一种改进，没有冒泡排序两两相邻之间的比较换位，主要采用的思想是通过递归+独立排序的形式将无序的数列进行分割成可以独立排序的2部分数列，其中一部分数列比另外一部书数列小，每次排序两个独立的数列，直到排序完毕，即可完成最终的排序。通俗讲就是每次定义一个临界值，将大值放在临界值的右边，小值放到临界值的左边。

/***
 * java现实快速排序算法
 **/
public class QuickSort {
    /** * left  左值
     * right 右值**/
    public static int getSortNum(int[] ary, int left, int right) {
        /**定义一个中枢值pivot，让其等于数组的左值，枢轴选定后永远不变，最终在中间，前小后大**/
        int pivot = ary[left];
        while (left < right) {
            /**看后面ary[right] > pivot比较，如果右边数组值大于中枢值，说明不需要调整位置，则让右值（right）自减1**/
            while (left < right && ary[right] >= pivot) {
                right--;  /**执行自减操作**/
            }
            /**如果上面循环不符合条件的，则说明右边数组的一个值，小于中枢值（pivot），则将其替换到左边数组中**/
            ary[left] = ary[right];
            /**看后面ary[left] < pivot比较，如果左边数组值小于中枢值，说明不需要调整位置，则让左值（left）自增1**/
            while (left < right && ary[left] <= pivot) {
                left++;  /**执行自增操作**/
            }
            /**如果上面循环不符合条件，则说明左边数组的一个值，大于中枢值（pivot），则将其替换到右边数组中**/
            ary[right] = ary[left];
        }
        /**最后将中枢值给自增后的左边数组的一个值中**/
        ary[left] = pivot;
        /**返回左边数组下标**/
        return left;
    }

    /***
     * 快速排序递归方法
     */
    public static void quickSort(int[] ary, int left, int right) {
        /**定义中枢值**/
        int pivot;
        if (left < right) {
            /**根据方法得到了每次中枢值的位置**/
            pivot = getSortNum(ary, left, right);
            /**根据中枢值（pivot），来对左边数组进行递归调用快速排序**/
            quickSort(ary, left, pivot - 1);
            /**根据中枢值（pivot），来对右边数组进行递归调用快速排序**/
            quickSort(ary, pivot + 1, right);
        }
    }

    /**测试**/
    public static void main(String[] args) {
        int[] ary = {97, 58, 3, 12, 88, 77, 101, 7, 22, 33, 44, 8, 66, 22};
        quickSort(ary, 0, ary.length - 1);
        for (int i = 0; i < ary.length; i++) {
            if (i != ary.length - 1)
                System.out.print(ary[i] + ", ");
            else
                System.out.println(ary[i]);
        }
    }

}

代码纯享版 ↓↓↓↓↓↓↓

/***
 * java现实快速排序算法
 **/
public class QuickSort {
    public static int getSortNum(int[] ary, int left, int right) {
        int pivot = ary[left];
        while (left < right) {
            while (left < right && ary[right] >= pivot) {
                right--;  
            }
            ary[left] = ary[right];
            while (left < right && ary[left] <= pivot) {
                left++; 
            }
            ary[right] = ary[left];
        }
        ary[left] = pivot;
        return left;
    }


    public static void quickSort(int[] ary, int left, int right) {
        int pivot;
        if (left < right) {
            pivot = getSortNum(ary, left, right);
            quickSort(ary, left, pivot - 1);
            quickSort(ary, pivot + 1, right);
        }
    }

    public static void main(String[] args) {
        int[] ary = {97, 58, 3, 12, 88, 77, 101, 7, 22, 33, 44, 8, 66, 22};
        quickSort(ary, 0, ary.length - 1);
        for (int i = 0; i < ary.length; i++) {
            if (i != ary.length - 1)
                System.out.print(ary[i] + ", ");
            else
                System.out.println(ary[i]);
        }
    }

}

运行结果: