基础算法篇——快速排序

时间：2022-11-02 08:06:56

本次我们介绍基础算法中的快速排序，我们会从下面几个角度来介绍快速排序：

  • 快速排序介绍
  • 暴力求解算法
  • 快速排序算法
  • 快速排序代码
  • 快速排序问题
  • 快速查找算法

快速排序介绍

我们首先来简单介绍快速排序问题：

  1. 首先我们需要确定一个分界点
这个分界点我们可以任意选择
我们常用的分界点有q[l],q[(l+r)/2],q[r]这三个点位
关于q[l]和q[r]如果选择递归的参数不合适，可能会导致死循环，我们后面会讲解，所以最好选择q[(l+r)/2]
  1. 调整区间数大小
我们希望我们选择的分界点的数作为分界数，我们不需要保证分界点的数是这个数
我们只需要保证在分界点的左侧的数全部都小于等于该分界数，同时该分界点的右侧的数全部都大于等于该分界数
  1. 递归处理
我们需要在开头进行判断：l >= r ? 

如果l >= r，那么我们就没有递归的必要，直接return即可
但是如果l > r，我们需要对其内部进行快速排序，并且在末尾处对排序后分界点的两侧再次进行递归处理

暴力求解算法

我们首先来介绍暴力求解法：

  1. 最简单最直观的方法就是采用两个数组，我们直接遍历l~r之间的所有数

  2. 如果该数小于分界数，那么放在a数组中；如果该数大于分界数，那么放在b数组中

  3. 最后我们将两个数组分别放到分界点的两侧处，然后再对其两侧进行暴力求解，最终达到效果

快速排序算法

我们采用指针来进行快速排序，因为这样不会开辟新的内存空间

我们来仔细介绍快速排序：

  1. 首先我们创建两个指针，分别指向数组的最左侧和最右侧
我们创建i和j指针，分别放于l-1和r+1处
因为我们后面需要判断该数与分界数的关系，所以我们首先移动指针再进行判断，所以我们需要将指针放在边缘处
  1. 在指针未相遇之前，我们将i向右移动，将j向左移动
首先我们需要判断两个指针没有相遇 i < j ? 

没有相遇我们开始执行排序操作：
我们进行i++，如果当前数小于分界数，我们继续移动，直到当前数大于分界数，停止移动
我们进行j--，如果当前数大于分界数，我们继续移动，直到当前数小于分界数，停止移动

当两者都停止移动时，首先需要判断 i < j ? 

若i < j 说明我们左侧停留的值大，右侧停留的值小
我们将两个数进行交换，将小的数移动到左侧，将大的数移动到右侧
  1. 递归处理
同样，我们在处理完当前数组后，需要将左侧和分界点之间的数进行排序，将分界点和右侧之间的数进行排序

快速排序代码

我们来简单实现一下快速排序算法：

import java.util.Scanner;

public class quick_sort {
    public static void main(String[] args) {
        // 输入数组的数量和数组的值

        int n;

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();

        int[] ints = new int[n];

        for (int i = 0 ; i < n;i++){
            ints[i] = scanner.nextInt();
        }

        // 展示数组

        System.out.print("排序前：");
        for (int i = 0; i < n; i++) {
            System.out.print(ints[i]);
        }
        System.out.println(" ");

        // 进行快速排序
        quick_sort(ints,0,n-1);

        // 展示数组

        System.out.print("排序后：");
        for (int i = 0; i < n; i++) {
            System.out.print(ints[i]);
        }
        System.out.println(" ");
    }

    public static void quick_sort(int[] ints,int l,int r){

        // 判断数组是否存在
        if (l >= r) return;

        // 进行快速排序
        int x = ints[(l+r)/2];
        int i = l-1,j = r + 1;
        while (i < j){
            // 左指针
            while (ints[++i] < x);

            // 右指针
            while (ints[--j] > x);

            // 如果左右指针没有相遇进行交换
            if (i < j){
                int temp = ints[i];
                ints[i] = ints[j];
                ints[j] = temp;
            }
        }

        // 实现递归处理
        quick_sort(ints,l,j);
        quick_sort(ints,j+1,r);
    }
}

快速排序问题

我们前面说到我们选择分界点的时候尽量选择(r+l)/2，因为单l或单r可能会导致死循环

下面我们给出示例：

import java.util.Scanner;

public class quick_sort {
    public static void main(String[] args) {
        // 输入数组的数量和数组的值

        int n;

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();

        int[] ints = new int[n];

        for (int i = 0 ; i < n;i++){
            ints[i] = scanner.nextInt();
        }

        // 展示数组

        System.out.print("排序前：");
        for (int i = 0; i < n; i++) {
            System.out.print(ints[i]);
        }
        System.out.println(" ");

        // 进行快速排序
        quick_sort(ints,0,n-1);

        // 展示数组

        System.out.print("排序后：");
        for (int i = 0; i < n; i++) {
            System.out.print(ints[i]);
        }
        System.out.println(" ");
    }

    public static void quick_sort(int[] ints,int l,int r){

        // 判断数组是否存在
        if (l >= r) return;

        // 进行快速排序
        int x = ints[l];
        int i = l-1,j = r + 1;
        while (i < j){
            // 左指针
            while (ints[++i] < x);

            // 右指针
            while (ints[--j] > x);

            // 如果左右指针没有相遇进行交换
            if (i < j){
                int temp = ints[i];
                ints[i] = ints[j];
                ints[j] = temp;
            }
        }

        // 实现递归处理
        quick_sort(ints,l,i-1);
        quick_sort(ints,i,r);
    }
}

下面我们模拟操作：

我们传入数据： 2 1 2

我们的分界数为： 1
最开始数组为：1 2

我们的i指针停在0处，我们的j指针也停在0处
这时我们进行第二轮递归处理

quick_sort(ints,0,-1)左侧递归直接结束
quick_sort(ints,0,1)右侧递归和第一轮完全相同，所以我们会一直循环下去

快速查找算法

我们在快速排序的基础上研究出了快速查找算法

题目：

  • 给定一个长度为n的整数数列，以及一个整数k，请用最快选择算法求出数列的第k小的数是多少

求解方法：

  • 我们根据快速排序算法来将数组进行排序，舍弃掉左右两侧的一侧，对另一侧进行查找排序，递归即可

求解代码：

import java.util.Scanner;

public class eee {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        // 输入总数
        int n = scanner.nextInt();

        // 输入查找第k小的值
        int k = scanner.nextInt();

        // 输入数组
        int[] arr = new int[n];

        for (int i  = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }

        // 运行方法查找第k小的值
        int minK = findMinK(arr,0,n-1, k);

        // 输出
        System.out.println(arr[minK]);
    }

    public static int findMinK(int[] arr,int l,int r,int k){

        // 如果相等，说明找到了
        if (l >= r) return l;

        // 下面是标准的快速排序
        int x = arr[(l+r)/2];
        int i = l-1;
        int j = r+1;

        while (i < j){

            while (arr[++i] < x);
            while (arr[--j] > x);

            if (l < r){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 如果数在左侧，对左侧遍历；如果数在右侧，对右侧遍历并修改概述在右侧的k值
        if (j > k) return findMinK(arr,l,j,k);
        else return findMinK(arr,j+1,r,k-j+1);
    }

}

结束语

好的，关于基础算法篇的快速排序就介绍到这里，希望能为你带来帮助~

相关文章