快速排序（Quick Sorting）
介绍
快速排序是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
代码演示
package com.crisp.Sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;public class QuickSort {public static void main(String[] args) {// int[] arr = {2,10,8,22,34,5,12,28,21,11};// print(arr);// Quick(arr,0,9);// print(arr);//创建有100000个数据的数组int[] arr = new int[100000];for(int i = 0; i < arr.length; ++i){arr[i] = (int)(Math.random() * 100000);//生成一个[0,100000)的随机数}System.out.printf("原始数组为：");print(arr);Date data1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String data1Str = simpleDateFormat.format(data1);Quick(arr,0,arr.length-1);Date data2 = new Date();String data2Str = simpleDateFormat.format(data2);System.out.printf("排序过后数组为：");print(arr);System.out.printf("排序前的时间是：%s\n",data1Str);System.out.printf("排序后的时间是：%s\n",data2Str);}//打印public static void print(int[] arr){System.out.println(Arrays.toString(arr));}/*** 快速排序法* @param arr 传入需要排序的数组* @param left 左下标（需要排序的起始位置）* @param right 右下标（需要排序的终止位置）*/public static void Quick(int[] arr, int left, int right){int l = left;int r = right;//以中点值为基准，也可选取其他基准int pivot = arr[(l + r) / 2];int tmp = 0;while(l < r){//比 pivot 值小的放左边 大的放右边while(arr[l] < pivot){//找到一个大于 pivot 的值l += 1;}while(arr[r] > pivot){//找到一个小于 pivot 的值r -= 1;}if (l >= r){break;}//交换tmp = arr[l];arr[l] = arr[r];arr[r] = tmp;//如果交换完后，发现 arr[l] == pivot ,right前移if(arr[l] == pivot){r --;}//如果交换完后，发现 arr[r] == pivot ,left后移if(arr[r] == pivot){l ++;}}//如果 l == r 必须 l++，r-- 否则出现栈溢出if( l == r){l ++;r --;}//左边递归if(left < r){Quick(arr, left, r);}//右边递归if(right > l){Quick(arr, l, right);}}}
