快速排序

56 阅读 0 评论 37 点赞

我是靠谱客的博主真实超短裙，最近开发中收集的这篇文章主要介绍快速排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

package demo;
/**
 * 快速排序；
 * @author Lynn
 *
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };
        System.out.println("排序前：");
        printArr(arr);
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后：");
        printArr(arr);
    }

    /**
     * 递归调用；
     * 
     * @param arr
     * @param low
     * @param height
     */
    private static void quickSort(int[] arr, int low, int height) {
        if (low < height) {
            int pivot = partition(arr, low, height);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, height);
        }
    }

    /**
     * 将枢纽放置正确的位置；
     * 
     * @param arr
     * @param low
     * @param height
     * @return
     */
    private static int partition(int[] arr, int low, int height) {
        int pivot = arr[low];// 枢纽；
        while (low < height) {
            while (low < height && arr[height] >= pivot) {
                height--;
            }

            arr[low] = arr[height];// 直接覆盖；

            while (low < height && arr[low] <= pivot) {
                low++;
            }

            arr[height] = arr[low];// 直接覆盖；

        }

        arr[low] = pivot;
        printArr(arr);
        return low;// 返回枢纽的位置，此时枢纽的左边不比其大，右边不比其小；
    }

    /**
     * 打印数组；
     * 
     * @param arr
     */
    private static void printArr(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (i != arr.length - 1) {
                System.out.print(arr[i] + " ");
            } else {
                System.out.print(arr[i]);
            }
        }
        System.out.println();
    }
}

运行结果