1. 首页
  2. 文章中心
  3. 快速排序

快速掌握java排序算法-快速排序（图文）

48 阅读 0 评论

概念

快速排序属于交换排序，主要步骤是使用基准元素进行比较，把小于基准元素的移动到一边，大于基准元素的移动到另一边。从而把数组分成两部分，然后再从这两部分中选取出基准元素，重复上面的步骤。过程如下：

（推荐视频：java视频教程）

file

这种思路叫做分治法。

基准元素

基准元素的选取可随机选取。下面使用中我会使用第一位的元素作为基准元素。

排序过程

排序拆分过程如下图：

第一轮
file

第二轮
file

第三轮
file

如上图所示：

若元素个数为n，因为排序过程中需要和全部元素都比较一遍，所以时间复杂度为O(n)，
而平均情况下排序轮次需要logn轮，因此快速排序的平均时间复杂度为O(nlogn)。

排序的实现方法

实现方法有双边循环法和单边循环法

双边循环法

首选选取基准元素(pivot)4，并设置指针left和right，指向数组最左和最右两个元素，如下：
file

第一轮指针移动完后，得到如下结构：

file

然后 left和right指向的元素进行交换：

file

第一轮循环结束，重新切换到right指针，重复上述步骤。

第二轮循环后，得：

file

第三轮循环后，得：

file

第四轮循环后，得：

file

判断到left和right指针指向同一个元素，指针停止移动，使pivot和指针元素进行交换，得：

file

宣告该轮循环结束，并根据Pivot元素切分为两部分，这两部分的数组再根据上述步骤进行操作。

实现代码

public class DoubleSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {

        //递归结束条件
        if (startIndex >= endIndex) {
            return;
        }

        // 基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);

        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    public static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个元素为基准元素，也可以随机抽取
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            // 控制right指针比较并左移
            while (left < right && arr[right] >= pivot) {
                right--;
            }

            // 控制left指针比较并右移
            while (left < right && arr[left] <= pivot) {
                left++;
            }

            // 交换left和right指针所指向的元素
            if (left < right) {
                int temp = arr[right];
                arr[right] = arr[left];
                arr[left] = temp;
            }
        }

        arr[startIndex] = arr[left];
        arr[left] = pivot;
        return left;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
登录后复制

单边循环法

双边循环法从数组的两边比较并交换元素，而单边循环法则从数组的一边遍历，一直往后比较和交换，实现起来更加的简单。
过程如下：

原始数组如下：

file

遍历到元素3时，因为3 < 4，所以mark右移

file

然后交换元素

file

然后就继续遍历，根据上面的步骤进行判断，后面的过程就不写了。

实现代码

public class SingleSort {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {

        //递归结束条件
        if (startIndex >= endIndex) {
            return;
        }

        // 基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);

        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    /**
     * 分治（单边循环法）
     * @param arr
     * @param startIndex
     * @param endIndex
     * @return
     */
    public static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个元素为基准元素，也可以随机抽取
        int pivot = arr[startIndex];
        int mark = startIndex;

        for(int i = startIndex + 1; i< arr.length; i++) {
            if (pivot < arr[i]) {
                continue;
            }

            mark ++;
            int temp = arr[mark];
            arr[mark] = arr[i];
            arr[i] = temp;
        }
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
登录后复制

总结

本人也是初次接触算法，慢慢的去理解算法的思路和实现过程后，真是为自己以往写的算法感到羞愧。该文章也是为了加深自己对快排算法的印象，若文章有不足之处，恳请各位在下方留言补充。感谢各位的阅读。Thanks♪(･ω･)ﾉ。

参考资料：《小灰的算法之旅》 第四章。

本文来自悠悠之家，java教程栏目，欢迎学习！

以上就是快速掌握java排序算法-快速排序（图文）的详细内容，更多请关注悠悠之家其它相关文章！

点赞(32)

评论列表共有 0 条评论

立即
投稿
返回
顶部