适合数据量大的数据集进行排序，采用二分递归法把数组按升序或降序进行排序。
一、升序算法步骤【正序】：
1、选定一个基准数arr[start]
2、选定两个标兵left、right
3、right标兵从右向左移动，遇到比基准数小的数则停下来
4、left标兵从左向右移动，遇到比基准数大的数则停下来
5、交换right和left数
6、若left和right重合，则把重合数与基准数进行交换
7、一轮结束，基准数在中间
8、对基准数左右两边的数组重复上述步骤，直至left和right重合。
备注：降序只需要调整步骤3、4。
二、java代码：
public class FastSort {
public static void main(String[] args) {
int[] arr = {6, 2, 4, 6, 7, 8, 9, 2, 3, 4, 1};
fastSort(arr, 0, arr.length - 1);
for (int a : arr) {
System.out.print(","+a);
}
}
public static void fastSort(int[] arr, int start,int end){
// 开始索引大于等于结束索引则停止排序
if (start >= end) {
return;
}
// 1、选定一个基准数arr[start]
int flag = arr[start];
// 2、选定两个标兵left、right
int left = start;
int right = end;
// 当两位标兵未重合则继续探索
while (left < right) {
// 3、right标兵从右向左移动，遇到比基准数小的数则停下来
while (left < right && arr[right] >= flag) {
right--;
}
// 4、left标兵从左向右移动，遇到大于基准数的数则停下来
while (left < right && arr[left] <= flag) {
left++;
}
//5、交换right和left数
if (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
// 6、若left和right重合，则把重合数与基准数进行交换
arr[start] = arr[left];
arr[left] = flag;
// 8、对基准数左右两边的数组重复上述步骤，直至left和right重合。
fastSort(arr, start, left - 1);
fastSort(arr, left + 1, end);
}
}
三、时间复杂度
1、最好情况：每次划分都很均匀。
趟数 复杂度
1 n
2 n + 2(1/2n)=2n
3 n + 2(1/2n) + 4(1/4n) = 3n
k kn
又因为：
n = 2^k（ n是数列长度，k是能划分的最大趟数）
所以：
k = logn
F = O(nlogn)
2、当待排序的序列为正序或逆序排列时，且每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。
趟数 复杂度
1 n
2 n+(n - 1)
3 n+(n-1)+(n-2)
n n+(n-1)+(n-2)...+1 = n(n-1)/2=n^2
所以F=0(n^2)
下一篇：2、浅析冒泡排序
