快速排序算法

51 阅读 0 评论 34 点赞

我是靠谱客的博主爱笑钢笔，最近开发中收集的这篇文章主要介绍快速排序算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

快排，顾名思义，就是很快的一种排序算法。

核心就是：每次排序的时候，设置一个基准点，将小于等于基准点的放左边，大于等于基准点的放右边，跳跃式交换。基于“二分”的一种思想。

但快排也有最坏情况，就是基准值选到最大或最小，导致数据跑到一边，最差时间复杂度是O(N²)，平均时间复杂度为O(NlogN)。

思路：
选最左作为基准，
用 j 从右往左遍历，如果比基准大，继续，比基准小，停，
用 i 从左网游遍历，如果比基准小，继续，比基准大，停，
然后交换 i 和就 j 处的值，交换之后接着走，直到 i = j；
将基准和 i 处值交换，一轮就结束了，
然后在通过递归，左边和右边继续上诉步骤，
直至左边不小右边，排序就结束了。

自己在本子上手动模拟一下就明白了。

注意：因为选择左边作为基准，所以要从右往左遍历，这样可以保证左边全最小，右边全最大。

代码：

public class QuickSort {

    //快排，基于二分思想的算法
    public static void quickSort(int arr[], int left, int right) {
        int i, j, t, temp;

        //如果左边大于右边，直接返回
        if (left > right)
            return;

        //用temp保存一下left位置的数,temp作为基准
        temp = arr[left];
        i = left;
        j = right;

        //当左和右没有碰头时候
        while (i != j) {
            //顺序很重要，要先从右往左
            while (arr[j] >= temp && i < j)
                j--;
            while (arr[i] <= temp && i < j)
                i++;
            //当上边两个while跑出来，如果i<j,交换i和j处的值
            if (i < j) {
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }

        //此时交换left和i处值
        arr[left] = arr[i];
        arr[i] = temp;

        //从上边跑到这里，说明一轮交换完成了，
        //i处左边小于i处的值和右边大于i处的值

        //递归，处理左边的
        quickSort(arr, left, i - 1);
        //递归，处理右边的
        quickSort(arr, i + 1, right);
    }

    public static void main(String[] args) {
        int [] arr = {6,1,2,7,9,5};

        quickSort(arr, 0, arr.length - 1);

        //输出
        int len = arr.length;
        for (int i = 0; i <len; i++) {
            System.out.println(arr[i]);
        }
    }
}