java实现快速排序
分治策略的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。
快速排序算法的基本思想
设当前待排序的无序区为R[low..high]，利用分治算法可将快速排序的基本思想描述为：
1.分解：
在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。注意：
划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos])：
R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中low≤pivotpos≤high。
2.求解：
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
3.组合：
因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。
<p><span><span style="font-family:Verdana, Arial, Helvetica, sans-serif;line-height:19px;text-indent:26px;"><span style="font-size:14px;"><span style="font-family:Arial;line-height:26px;"><br></span></span></span></span></p>
排序演示：
假设一开始序列{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，从前往后找，第一个比5大的数是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，从第3位往后找，第一个比5大的数是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)
java代码实现：
//快速排序 对冒泡排序的一种改进
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[800000];
for (int i = 0; i < 800000; i++) {
int random = (int) (Math.random() * 100);
arr[i] = random;
}
Date date = new Date(System.currentTimeMillis());
System.out.println(date);
quickSort(arr, 0, arr.length - 1);
date = new Date(System.currentTimeMillis());
System.out.println(date);
}
public static void quickSort(int[] arr, int left, int right) {
int l = left;//左下标
int r = right;//右下标
int temp = 0;
int pivot = arr[(left + right) / 2]; //中间值
while (l < r) {
//pivot找 直到找到比pivot小的数为止
while (arr[l] < pivot) {
l += 1;
}
//pivot找 直到招到比pivot大的数为止
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 (left < r) {
quickSort(arr, left, r);
}
//向右递归
if (right > l) {
quickSort(arr, l, right);
}
// System.out.println("排序后的数组：" + Arrays.toString(arr));
}
}执行时间展示：
随机排序800000个随机数耗时不到1s
