1、浅析快速排序

适合数据量大的数据集进行排序，采用二分递归法把数组按升序或降序进行排序。
一、升序算法步骤【正序】：
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、浅析冒泡排序