快速理解快速排序（附java模板）

爱被打了一巴掌 2023-10-04 15:41 14阅读 0赞

前言：

很多人认为排序直接用sort函数它不香吗，emmm确实平时刷题如果需要先进行排序我们基本都会直接使用sort函数（不太了解sort的可以自行上网搜索）。但其实排序算法是算法中最基础的部分，即使我们不使用它但也应该理解它的原理及能够手写出来，这对于我们刷题的思路是有很大的帮助的。

**言归正传：**

**1.什么是快速排序？**

首先我们要知道快速排序使用的是分治思想(顾名思义就是要将数据分开讨论),它相对于归并排序和堆排序的有点在于它不需要使用的空间，它可以在原地实现排序，从而节省内存

**2.快速排序的过程**

**1.确定分界点的值x：nums\[i\]，nums\[（i+r）/2\],nums\[r\],随机值均可**

**分界点的值x的作用就是依照x的值来把数组分为左右两个子数组，其中左数组的值均小于等于x，而右数组的值均大于等于x。**

**2.调整区间。**

**3.递归处理两端数组。**

**原理讲解：**假设我们有一组长度n=5的数组【3,1,2,4,5】我们需要将它变成升序。

1.我们先设置一个左指针l和又指针r。初始下标为-1和n。当然数组中其实是无法索引这两个下标的，但我们每次进行判断时先将l和r值加一就不会出现数组越界的情况。再选一个分界点值x**（最好使用****nums\[（i+r）/2\]，因为这样更容易将两个子数组长度划分的更接近，时间会消耗更少****）**

2.判断nums【i】是否大于值x，若大于则指针i加一指向下一个数，直到指到的数大于x时停下来**（此时也要保证i指针在j指针的左边）,**此时轮到j指针行动，它判断nums【j】是否大于x，若大于则j指针向左移动判断前一位是不是仍然大于x，也是直到判断到一个小于x的值时停下来**(此时也要保证j指针仍然在i指针的右边)**

3.那么此时是不是左边得到了一个大于x的值，右边得到一个小于x的值，这不符合我们要的左子数组都不能大于x，右子数组都不能小于x的目的。那么我们就将**nums【i】的值和nums【j】调换**，这是我们的核心步骤。然后继续重复相同的步骤，i走停以后j走，两个指针停住后交换值，然后继续走，**直到两个指针或者经过时结束。**那么此时以两指针相遇的点来看，是不是左边的值都一定不大与x，右边的值都一定不小于x。**那如果此时将左边的子数组排序后再加上排序的右子数组，是不是这整个数组就是排好序的。**

4.最后一步就是运用递归思想，我们把左子数组也用同上的方法，右子数组也如此，最后判断一直分到子数组的长度为1为止。

附上代码（**可当做模板**）

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    import java.util.Arrays;
    
    public class test {
        public static void quckly_sort(int[] nums,int l,int r){
            int i=l-1;
            int j=r+1;
            int x=nums[l];
            if(l>=r){
                return;
            }
            while(i<j){
                do{
                    i++;
                }while(nums[i]<x);
                do{
                    j--;
                }while(nums[j]>x);
                if(i<j){
                    int tem=nums[i];
                    nums[i]=nums[j];
                    nums[j]=tem;
                }
            }
            quckly_sort(nums,l,j);
            quckly_sort(nums,j+1,r);
        }
    
        public static void main(String[] args)throws IOException{
            InputStreamReader in = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(in);
            int n=Integer.parseInt(br.readLine());
            int[] nums=new int[n];
            for(int i=0;i<n;i++){
                nums[i]=Integer.parseInt(br.readLine());
            }
            quckly_sort(nums,0,n-1);
            System.out.println(Arrays.toString(nums));
        }
    }

**注意事项：1.要用dowhile循环，比while循环节省时间（while可能会超时，而且我们是先移动指针再判断，所以要用dowhile）**

**2.注意递归时放入的下标，一不小心就数组越界，最好记住背下来**

**3.使用BufferedReader比Scanner更省时间不容易超时，不理解的照着用即可，当然Scanner也行，BufferedReader的使用比较复杂可以上网查询**