package cn.com.zfc.lesson21.sort;

 /**

  *

  * @title QuickSort

  * @describe 快速排序

  * @author 张富昌

  * @date 2016年10月2日下午2:45:37

  */

 public class QuickSort {

     // 快速排序是平均时间最快的排序算法。

     // 基本思想：任选待排序列中的一个数据元素（通常选取第一个数据元素）作为枢轴，用它和所有的剩余元素进行比较，将所有较它小的元素排在它的前面；

     // 将所有较它大的元素排在它的后面，经过一趟排序后，可按次数据元素所在位置为界，将可序列化分成两个部分；

     // 再对这两个部分重复上述过程直至每一个部分中只剩下一个数据元素为止。

     public static void main(String[] args) {

         // 声明整型数组

         int[] array = new int[10];

         // 使用循环和随机数初始化数组

         for (int i = 0; i < array.length; i++) {

             array[i] = (int) Math.round(Math.random() * 100);

         }

         System.out.println("原始数组为：");

         for (int i : array) {

             System.out.print(i + " ");

         }

         System.out.println();

         System.out.println("排序后的数组为：");

         for (int i : quickSort(array)) {

             System.out.print(i + " ");

         }

     }

     /**

      *

      * 功能：对数组进行快速排序，并且返回该数组

      *

      * 参数：int[] arr

      *

      * 返回类型：int[]

      */

     public static int[] quickSort(int[] arr) {

         quickSortHelp(arr, 0, arr.length - 1);

         return arr;

     }

     /**

      *

      * 功能：对数组 arr[low...high] 中的记录进行快速排序

      *

      * 参数：int[] arr, int low, int high

      *

      * 返回类型：void

      */

     public static void quickSortHelp(int[] arr, int low, int high) {

         if (low < high) {

             // 子序列 elem[low...high] 的长度大于 1

             int pivotLoc = partition(arr, low, high);

             // 对子序列 arr[low...pivotLoc-1] 递归排序

             quickSortHelp(arr, low, pivotLoc - 1);

             // 对子序列 arr[pivotLoc+1...high] 递归排序

             quickSortHelp(arr, pivotLoc + 1, high);

         }

     }

     /**

      *

      * 功能：使枢轴元移到正确的位置，要求枢轴左边的元素不大于枢轴，枢轴右边的元素不小于枢轴，并返回枢轴的位置

      *

      * 参数：int[] arr, int low,int high

      *

      * 返回类型：int

      */

     public static int partition(int[] arr, int low, int high) {

         while (low < high) {

             // arr[low] 为枢轴，使 low左边的元素不大于 elem[high]

             while (low < high && arr[low] <= arr[high]) {

                 high--;

             }

             // 交换 arr[low] 和 arr[high]的值

             swap(arr, low, high);

             // arr[high] 为枢轴，使 low 左边的元素不大于 arr[high]

             while (low < high && arr[low] <= arr[high]) {

                 low++;

             }

             // 交换 arr[low]和 arr[high]的值

             swap(arr, low, high);

         }

         // 返回枢轴的位置

         return low;

     }

     /**

      *

      * 功能：交换两个数的值

      *

      * 参数：int x,int y

      *

      * 返回类型：void

      */

     public static void swap(int[] arr, int i, int j) {

         int temp = arr[i];

         arr[i] = arr[j];

         arr[j] = temp;

     }

 }