快速排序详解

基本思想

1.先从数列中取出一个数作为基准数。

2.将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边(分区过程)。

3.再对左右区间重复第二步,直到各区间只有一个数。

算法实现

    private static void quickSort(int a[], int left, int right) {
        if (left > right) {
            return;
        }
        int border = partition(a, left, right);
        quickSort(a, left, border - 1);
        quickSort(a, border + 1, right);
    }

    /**
     * 循环分区过程:
     * 1. 从左到右找到一个比基准数大的位置i
     * 2. 从右到左找到一个比基准数小的位置j
     * 3. 交互i,j的数值位置
     * <p>
     * 退出条件:
     * i==right(到最右边都没找到比基准数大的位置)
     * j==left(到最左边都没找到比基准数小的位置)
     * i>j j之后的都比基准数大,不用再继续
     * <p>
     * 退出后的操作:
     * 交换left(即基准数的位置)和j的位置,交换之后,j左边的都小于基准数,j右边的都大于基准数,j为下次分区的边界
     * 返回j的位置
     */
    private static int partition(int[] a, int left, int right) {
        int i = left, j = right + 1;
        int v = a[left];
        while (true) {
            while (a[++i] <= v) {
                if (i == right) {
                    break;
                }
            }
            while (a[--j] >= v) {
                if (j == left) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            exchange(a, i, j);
        }
        exchange(a, left, j);
        return j;

    }

    private static void exchange(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

测试

    public static void main(String[] args) {
        int a[] = {314, 1234, 34, 1, 234, 2341, 23, 434};
        quickSort(a, 0, a.length - 1);
        Arrays.stream(a).forEachOrdered(k -> {
            System.out.print(k);
            System.out.print(",");
        });
    }
//output:
1,23,34,234,314,434,1234,2341,

总结

快速排序在平均状况下,排序N个项目要Ο(N*logN)次比较。在最坏状况下则需要Ο(N2)次比较,但这种况并不常见。快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率比较高,因此经常被采用,快速排序的分治法思想也很常用。

优化

1.基准数的选择(随机选择或取数列中间数)

2.区间内数据较少时直接用另的方法排序以减小递归深度

 

这里有很详细的动画,可以查看快排详细过程:

https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

 

# 算法 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×