排序算法之三：快速排序

&＃160;算法分析：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。

一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。接着分别比较左右两边的序列，重复上述的循环。

复杂度：理想为O(nlogn)，最差为O(n^2)

public void quicksort(int[] arr,int start,int end){

&＃160; &＃160; &＃160; &＃160; if(start>=end){

&＃160; &＃160; &＃160; &＃160; &＃160; &＃160; return;

&＃160; &＃160; &＃160; &＃160; }

&＃160; &＃160; &＃160; &＃160; //把数组中的第0个数作为基数

&＃160; &＃160; &＃160; &＃160; int stard=arr[start];

&＃160; &＃160; &＃160; &＃160; int low=start;

&＃160; &＃160; &＃160; &＃160; int high=end;

&＃160; &＃160; &＃160; &＃160; while(low
&＃160; &＃160; &＃160; &＃160; &＃160; &＃160; //右边的数比标准数大

&＃160; &＃160; &＃160; &＃160; &＃160; &＃160; while(low
&＃160; &＃160; &＃160; &＃160; &＃160; &＃160; &＃160; &＃160; high--;

&＃160; &＃160; &＃160; &＃160; &＃160; &＃160; &＃160; &＃160;&＃160;

&＃160; &＃160; &＃160; &＃160; &＃160; &＃160; }

&＃160; &＃160; &＃160; &＃160; &＃160; &＃160; //右边的数替换左边

&＃160; &＃160; &＃160; &＃160; &＃160; &＃160; arr[low]=arr[high];

&＃160; &＃160; &＃160; &＃160; &＃160; &＃160; while(low=arr[low]){

&＃160; &＃160; &＃160; &＃160; &＃160; &＃160; &＃160; &＃160; low++;

&＃160; &＃160; &＃160; &＃160; &＃160; &＃160; }

&＃160; &＃160; &＃160; &＃160; &＃160; &＃160; arr[high]=arr[low];

&＃160; &＃160; &＃160; &＃160; }

&＃160; &＃160; &＃160; &＃160; arr[low]=stard;

&＃160; &＃160; &＃160; &＃160; //处理所有小的数

&＃160; &＃160; &＃160; &＃160; quicksort(arr,start,low);

&＃160; &＃160; &＃160; &＃160; //处理所有大的数

&＃160; &＃160; &＃160; &＃160; quicksort(arr,low+1,end);

&＃160; &＃160; }