【每日算法】快速排序
今日题目：以中间数为基准，对某数列进行快速排序。
点题：快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
-
1．先从数列中取出一个数作为基准数。 -
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 -
3．再对左右区间重复第二步，直到各区间只有一个数。 -
大家可以先自行思考，并自己使用算法实现
以下为具体程序（Java）：
import java.util.ArrayList;import java.util.Arrays;import java.util.LinkedList;public class Quicksort {public static void main(String[] args) {int arr[]=new int[]{15,52,0,-3,222,36,-18,90,-5556,7};System.out.println("排序前的数组是："+Arrays.toString(arr));System.out.println("***************");Qs(arr,0,arr.length-1);System.out.println("排序后的数组是："+Arrays.toString(arr));}public static void Qs(int []arr,int left,int right){int l=left; //左索引int r=right; //右索引int pivot=arr[(l+r)/2];int temp=0; //临时变量//while循环的目的是每一次都把比pivot小的放他左边，比pivot大的放他右边while (l<r){while (arr[l]<pivot){l+=1;}while ((arr[r]>pivot)){r-=1;}//如果是这样，说明pivot的左右两的值，已经按照左边全是小等于pivot、右边全是大等于pivot值if(l>=r){break;}//交换temp=arr[l];arr[l]=arr[r];arr[r]=temp;//如果交换完后，发现这个arr【l】==pivot值相等 r-- 前移一下if(arr[l]==pivot){r-=1;}//如果交换完后，发现这个arr【r】==pivot值相等 l++ 后移一下if(arr[r]==pivot){l+=1;}}//如果l==r，必须l++ r-- 否则为出现栈溢出if(l==r){l+=1;r-=1;}//向左递归if (left<r) {Qs(arr,left,r);}//向右递归if(right>l){Qs(arr,l,right);}}}