常见排序算法之快速排序

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

文章目录

1、概述
2、代码实现
3、测试案例

1、概述

快速排序（Quicksort）是对冒泡排序的一种改进。

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

2、代码实现

快速排序的方式有两种，主要的区别就是选择基准值的不同，但是他们的核心思想都是一样的，只是说我们在代码的是线上有一些区别

梳理核心思想：

选择一个基准值（我们这里选择的是 (头+尾)/2 的值）
然后将基准值左边的数据和右边的数据进行位置的交换（不符合规范的数字）
在基准值的右边，用同样的方式再选择出一个基准值，然后重复2步骤。同理左边也重复2
然后不断地递归循环，直到剩下的数字不能再分为止

个人觉得，道理虽然简单，但是代码实现还是有一定的困难的，需要注意很多其他的点

public class QuickSortTest01 {
    public static void main(String[] args) {
        int[] arr = {1, 23, 5, 6,3, 3, 52, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }

    public static void quickSort(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        //1.将中间的那个值设置为基准值
        int pivot = arr[(left + right) / 2];
        int temp;

        while (l < r) {

            //2.如果右边的数字比我们的基准值大，说明符合要求，那么我们就将下标前移
            while (arr[r] > pivot) {
                r--;
            }
            //3.如果左边的数字比我们的基准值小，说明符合要求，那么我们就将下标后移
            while (arr[l] < pivot) {
                l++;
            }
            //4.因为前面在移动下标，为了避免移动过头，需要设置对应的跳出while循环
            if (l >= r) {
                break;
            }
            //5.拿到我们两个不符合的数字，并且完成交换
            temp = arr[r];
            arr[r] = arr[l];
            arr[l] = temp;

            //6.这两条语句，目的是为了让与基准值相同的数据，不断地向中间靠拢
            //一旦这两条if语句中有一条被执行了，那么上面地while循环就会有一个不会被执行到
            // 每一次的交换数字都是为一个不符合规范的数字，一个与基准值相同的数字，继而达到了基准值向中间靠拢的目的
            if(arr[l] == pivot) {
                r--;
            }
            if(arr[r] == pivot) {
                l++;
            }
        }

        //7.防止栈溢出
        //添加此句的目的是为了，递归排序的时候，将我们的基准值抛开，不然会进入死循环
        if(l == r) {
            l++;
            r--;
        }

        //8.左边进行递归排序
        if (left < r) {
            quickSort(arr, left, r);
        }
        //9.右边进行递归排序
        if (right > l) {
            quickSort(arr, l, right);
        }
    }
}

3、测试案例

利用我们以有的条件，进行一个小案例的测试：计算将数组长度为80000的乱序数组排序所花费的时间

public class QuickSortTest02 {
    public static void main(String[] args) {
        int[] arr = new int[80000];

        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }

        long start = System.currentTimeMillis();
        quickSort(arr, 0, arr.length - 1);
        long end = System.currentTimeMillis();

        System.out.println("快速排序花费的时间是:" + (end - start));

    }

    public static void quickSort(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        //将中间的那个值设置为基准值
        int pivot = arr[(left + right) / 2];
        int temp;

        while (l < r) {
            while (arr[r] > pivot) {
                r--;
            }

            while (arr[l] < pivot) {
                l++;
            }

            if (l >= r) {
                break;
            }

            temp = arr[r];
            arr[r] = arr[l];
            arr[l] = temp;

            if (arr[l] == pivot) {
                r--;
            }
            if (arr[r] == pivot) {
                l++;
            }

        }

        if (l == r) {
            l++;
            r--;
        }

        if (left < r) {
            quickSort(arr, left, r);
        }
        if (right > l) {
            quickSort(arr, l, right);
        }
    }
}