算法排序-快速排序

算法排序-快速排序快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排…

简介

快速排序(Quicksort)是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

时间复杂度

O(n^2)

思路分析

算法排序-快速排序 算法排序-快速排序

接下来把中轴左端的元素继续取中轴,跟上面过程一样,继续找比中轴小的元素放中轴左边,比中轴大的元素放中轴右边。中轴右边元素同理。

直到中轴的左边、右边只剩一个元素则排序完成。 因为只剩一个元素中轴前面的元素一定是比中轴小 ,只剩一个元素中轴后面的元素一定比中轴大。

代码实现

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {2, 6, 5, 7, 9, 1, 3, 4};
        //int[] arr = {2, 1, 1, 1, 1, 2};
// int[] arr = new int[80];
// Random random = new Random();
//
// for (int i = 0; i < 80; i++) {
// arr[i] = random.nextInt(80000);
// }
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /** * 快速排序 * * @param arr 待排序数组 * @param left 数组最左端 * @param right 数组最右端 */
    public static void quickSort(int[] arr, int left, int right) {
        // 保证两端索引不会交叉越过 同时保证递归能够结束避免死循环
        // 当pivot左边没有元素 left=0 right=-1 
        // 当pivot左边只有一个元素 left=0 right=0
        if (left >= right) {
            return;
        }
        // 保存最左端在过程中left不被修改 修改l
        int l = left;
        // 保存最右端在过程中right不被修改 修改r
        int r = right;
        // 取中轴 (取第一个数为中轴)
        int pivot = arr[left];
        // 如果左边和右边索引没碰撞 或者没交叉越界 说明元素还没找完 继续找
        while (left < right) {
            // 循环里的比较方向如下
            // left → ← right
            // ↓ ↓
            // 2 6 5 7 9 1 3 4

            // 下面两个循环必须是从right--这个循环开始 因为我们开始取中轴取的是第一个数 并且间接性的把他给保存起来了
            // 又因为left停留在第一个位置 所以就先从右边开始找,找到比pivot小的数就往left位置放

            // left < right 是为了保证right不会小于0而导致索引越界,极端情况下12345 该循环会一直--到-1然后导致越界
            // arr[right] >= pivot 如果=true证明当前元素比pivot大 那么继续right--往前一个找
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            // 循环退出证明arr[right]比pivot小 就把arr[right]往left放
            arr[left] = arr[right];
            // 同理 arr[left] <= pivot 如果=true证明当前元素比pivot小 那么继续right--往前一个找
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            // 同理 循环退出证明arr[left]比pivot大 就把arr[left]往right放
            arr[right] = arr[left];
        }
        // 循环结束的时候也就是left和right碰撞的时候
        // 碰撞时:碰撞的左边全是比pivot小的元素 碰撞的右边都是比pivot大的元素 所以碰撞时的位置就是中轴要放的位置
        // 因为碰撞时left==right 所以这里使用left或者right都行
        arr[left] = pivot;
        // 把中轴左边的元素 再次取中轴找左右边的元素
        quickSort(arr, l, left - 1);
        // 把中轴右边的元素 再次取中轴找左右边的元素
        quickSort(arr, left + 1, r);
        //递归到中轴的左边、右边只剩一个元素则排序完成 因为只剩一个元素中轴前面的元素一定是比中轴小 ,只剩一个元素中轴后面的元素一定比中轴大
    }
}

运行输出:

[1, 2, 3, 4, 5, 6, 7, 9]

总结

快速排序快是因为空间换取了时间。快速排序是不稳定的排序算法,当一个数组是有序或者基本有序,则退化成冒泡排序,这种情况可以考虑使用随机pivot来处理。在数组无序时快速排序速度极快。

算法一定要明白思路,明白思路,代码实现都是大同小异。

今天的文章算法排序-快速排序分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/22475.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注