java实现快速排序
分治策略的基本思想是将规模n的问题分解为k个规模小的子问题，这些子问题相互独立，且具有与原问题相同的性质。 求子问题的解的话，就能得到原问题的解。 也就是按目标完成程序的算法，简单的问题可以用二分法完成。
快速排序算法的基本思想
将当前排序的无序区域设为R[low…high]，通过利用分割统治算法，可以如下记述快速排序的基本思想
以R[low…pivotpos-1的任一记录为基准[pivot]，按照该基准将当前的无序分区分为左、右两个子区间R[low…pivotpos-1和R[pivotpos 1…high] 使左侧子区间的所有记录的关键字在基准记录R[pivotpos 1…high]以下右侧子区间的所有记录的关键字在pivot.key以上，基准记录的pivot位于正确的位置(pivotpos )1.分解：
区分的关键是要求有基准记录的位置pivotpos。 的结果可以很容易地表示(注意pivot=R[pivotpos] )。
r [ low…pivotpos-1 ].keysr [ pivotpos ].keyr [ pivotpos 1…high ].keys
其中，lowpivotposhigh。
注意：
在递归调用快速排序中快速排序左、右子区间R[low…pivotpos-1]和R[pivotpos 1…high]。
2.求解：
因为在“求解”步骤中的两个递归调用结束后，其左、右两个子区间已经有序。 对于快速排序，“组合”步骤不需要执行任何操作，可以将其视为空操作。
3.组合：
假设第一个序列{xi}是5、3、7、6、4、1、0、2、9、10和8。
此时，pivotpos=5、i=1、j=11，如果从后面查找，小于前5的数为x8=2，因此数组为2、3、7、6、4、1、0、5、9、10、8
此时，i=1，j=8，如果去了再找，大于前五的数是x3=7，所以序列为2、3、5、6、4、1、0、7、9、10、8。
此时，如果i=3，j=8，从第8个开始查找，则小于前5的数为x7=0，因此为2、3、0、6、4、1、5、7、9、10、8。
此时，如果i=3，j=7，从第三个开始查找后面，则大于前五个的数量为x4=6，因此为2、3、0、5、4、1、6、7、9、10、8。
此时，如果从第i=4、j=7、7开始查找，则小于前5的数为x6=1，因此为2、3、0、1、4、5、6、7、9、10、8。
此时，i=4，j=6从第4位开始寻找后面，到第6位为止有比5大的数。 此时，i=j=6，pivotpos成为边界，以前的数量比其小，以后的数量比其大。 前后两个部分的数量也可以用同样的方法进行排序。
排序演示：
时间复杂度：O (nlogn)
//改进快速排序冒泡排序公共类快速排序(公共语音(字符串) args ) ) arr=new int (800000 )； for(intI=0； i 800000； I ) intrandom=(int ) (Math.random ) ) * 100 )； ARR[I]=随机； } datedate=new date (system.current time millis ()； 系统. out.println (date； 快速排序(arr，0，arr.length - 1 )； date=new date (system.current time millis ()； 系统. out.println (date； } publicstaticvoidquicksort (int [ ] arr，int left，int right ) int left； //左下标int r=right； //右下标int temp=0； int pivot=arr [ (左光线)/2]； while(ARR[L]pivot ) ) L=1，直到找到小于//pivotpivot的数量； while(arr[r]pivot ) ({ r -=1； 如果l=r，则pivot的左边全部是比pivot小的数，右边全部是比povot大的数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(leftr )快速排序(arr，left，r )； (//右递归if(rightL ) quicksort ) ARR，l，right )； }//System.out.println ('已排序数组： ' Arrays.tostring () ARR ) )； }} java代码实现：
随机排序800000个随机数用不了1s