09、数据结构与算法 - 实战：排序算法之快速排序

1、基本思想

快速排序是对冒泡排序的改进。通过一趟排序，将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个序列可以递归进行，以此达到整个数据变得有序序列。

2、图解

首先，随便从数组选一个值（比如选最中间的值），然后把比这个值小的元素放在这个值的左边，比这个值大的元素放在这个值的右边。

然后，把这个值的左右两边序列看成独立序列，分别再次进行上面操作。直到分成的独立序列只剩下一个元素位置。

3、代码实现

package cn.klb.datastructures.sort;

/**
 * @author DDKK.COM 弟弟快看，程序员编程资料站
 * @Description: 实现数组的快速排序
 * @Date: Create in 2023/4/4 19:42
 * @Modified By:
 */
public class Quick {
   
     
    public static void sort(int[] arr) {
   
     
        int left = 0;   // 初始left是最左边
        int right = arr.length - 1; // 初始right是最右边
        doSort(arr, left, right);
    }

    private static void doSort(int[] arr, int left, int right) {
   
     
        int l = left;
        int r = right;
        // 这里定义一个中间值
        // 注意：
        //      这里所谓的中间值不一定就得是数组最中间的那个值
        //      它可以是数组中任意的一个值，这里为了方便，才取了数组最中间的值
        //      核心思想就是使得数组整体上小的在前面，大的在后面
        int mediumValue = arr[(left + right) / 2];
        int temp = 0;

        // 把左边大于mediumValue的元素和右边小于mediumValue的元素进行交换
        while (l < r) {
   
     
            // 遍历左边元素，如果元素小于mediumValue，则索引往右走继续找
            while (arr[l] < mediumValue) {
   
     
                l++;
            }

            // 遍历右边元素，如果元素大于mediumValue，则索引继续往左走
            while (mediumValue < arr[r]) {
   
     
                r--;
            }

            // 检查一下l和r是不是超出边界了
            if (l >= r) {
   
       
                break;
            }

            // 如果没有退出当前while，则进行交换元素
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完后，发现这个arr[l] == mediumValue 相等 r--， 左移
            if (arr[l] == mediumValue) {
   
     
                r--;
            }
            //如果交换完后，发现这个arr[r] == mediumValue 相等 l++， 右移
            if (arr[r] == mediumValue) {
   
     
                l++;
            }
        }

        // 跳出最外层while后，要么 l > r,要么 l == r，不会出现 l < r 的情况
        // 什么时候会出现 l < r呢
        // 比如有个数组：{3，3，3，3，4，4，4}
        // 我们取了最中间的3作为中间值
        // l指针会跑到下标4的地方才跳出while
        // r指针会跑到下标3的地方才跳出while
        // 然后触发 l >= r 条件而跳出最外层的while循环。
        if (r == l) {
   
     
            r--;
            l++;
        }

        // 左边递归
        if (left < r) {
   
     
            doSort(arr, left, r);
        }
        // 右边递归
        if (right > l) {
   
     
            doSort(arr, l, right);
        }
    }
}

4、时间复杂度

其实，在执行小的放前边，大的放后边之前，选取哪个值哪来当枢纽元（就是拿来比较的那个值）会影响算法的性能。最不好的就是每轮都选取第一个元素，因为当一个序列是预排序或者反序的，会导致所有的元素都划分在小值那边或者大值那边。比较安全的做法是随机选取，但会明显减慢快速排序的速度。一般做法是使用三数中值分割法，即先拿出最左边、最右边和最中间三个值，以这三个值的中值作为枢纽元，数学证明这样做能减少14%的比较次数。
假设比较次数为C，交换次数为S。
快速排序的时间复杂度受枢纽元选取策略影响，最差情况下的时间复杂度为O(n²)。

5、稳定性

通过原理可以判断：在左右两步进行交换的时候，是不会考虑左指针和右指针中间的重复值，因此快速排序是不稳定的。

6、测试

package cn.klb.test.datastructurestest;

import cn.klb.datastructures.sort.*;
import org.junit.Test;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author DDKK.COM 弟弟快看，程序员编程资料站
 * @Description: 排序测试
 * @Date: Create in 2023/4/3 21:32
 * @Modified By:
 */
public class SotrTest {
   
     
    @Test
    public void testQuick(){
   
     
        int[] arr = new int[80000000];
        for (int i = 0; i < 80000000; i++) {
   
     
            arr[i] = (int) (Math.random() * 80000000);
        }
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        Date date1 = new Date();
        System.out.println("-----" + sdf.format(date1) + "-----");
        System.out.println(Arrays.toString(arr));

        Quick.sort(arr);

        Date date2 = new Date();
        System.out.println("-----" + sdf.format(date2) + "-----");
        System.out.println(Arrays.toString(arr));

        // 8000万的随机数据进行快速排序，我的电脑花了大约13秒(更质的飞跃)
    }
}