快速排序------一种优雅的排序算法

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱

ʕ̯•͡˔•̯᷅ʔ大家好，我是xiaoxie.希望你看完之后,有不足之处请多多谅解，让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ ა

本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶

个人主页：xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客

系列专栏：xiaoxie的算法系列专栏——CSDN博客●'ᴗ'σσணღ*

我的目标:"团团等我💪( ◡̀_◡́ ҂)"

感谢您的阅读！

( ⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞👍 + 收藏⭐️ + 留言📝+关注（互三必回）!

一.分而治之的思想

1.学习分而治之

当你遇到一题很难的编程题，可能你使用任何你已经掌握和以知的算法都解决不了的问题时，你可以尝试着使用已知的解决问题的解决方案来找出解决问题的方法，而快速排序就是一种常用的通用的解决方法，当你面对问题时，你可以问自己：“用分而治之可以解决吗?”是不是觉得很神奇，好接下来博主将通过举一到两个例子，来帮助你更好的理解分而治之-----D&C这一思路。

2.例子说明

1.D&C（分治法，Divide and Conquer）的工作原理

1.找出简单的基线条件；

2.确定如何缩小问题的规模，使其符合基线条件

博主首先强调一下D&C并不是算法，而是一种解决问题的思路。

2.例子

博主相信大部分读者应该小学初中时都遇到过类似这样的题目吧

把一个长168宽64的长方形均匀的分成小方块,且分成的方块要尽可能的大

1.我们以前上学时可能会这样来求解：

1. 设小方块的边长为x。
   
2. 根据题目中给出的长方形的尺寸，列出方程：

• 长方形的长除以x等于一个整数n：长/x = n
• 长方形的宽除以x等于一个整数m：宽/x = m

3. 将方程进行简化：

• 将长方形的长和宽都除以2，得到新的方程：长/2x = a 和 宽/2x = b

4. 将a和b表示为整数：

• 长/2x = a 可以简化为 长/x = 2a，其中2a为整数。
• 宽/2x = b 可以简化为 宽/x = 2b，其中2b为整数。

5. 解这两个方程，得到a和b的值：

• 根据题目中给出的具体长方形的尺寸，计算出a和b的值。

6. 将a和b代入方程长/x = 2a和宽/x = 2b，得到：

• 长/x = 2a，解这个方程，得到长/x的值。
• 宽/x = 2b，解这个方程，得到宽/x的值。

7. 找到长/x和宽/x的最小公倍数，即长/x和宽/x的乘积除以它们的最大公约数。
   
8. 最小公倍数即为x的值，即小方块的边长。
   

通过这个步骤，可以使用未知数解决问题，并得到尽可能大的小方块尺寸。

而让我们用这个思路显然在代码中很难实现，这时候我们就需要使用D&C的思路来解决问题了，

2.D&C的解题思路

在上文标题2.1中博主为大家简单的介绍了D&C的工作原理，下面我们就来使用D&C找出解决问题的方法。

首先我们要先找出这个例子的基数条件。最容易理解的情况就是：一条边的长度是另一条长度的整数倍

假如长方形的一边长25cm,而另一边长为50cm,就可以分成两个边长为25cm的小方形。

同理我们解决长168cm,宽64cm的长方形，根据D&C的定义，每次递归调用都必须缩小问题的规模。我们首先可以先找出这个长方形可以容纳最大方型

这样我们就可以把一个大长方形分解成两部分，一部分为两个方块，另一部分为一个小长方形，这样我们一把数据范围缩小了，我们通过这个思路把长为168cm宽为64cm的大长方形的问题给简化成长64cm宽为40cm的小长方形了。

同理我们也可以对这个小长方形使用一样的方法：

我们再同样对更小的长方形进行一样的方法：

直到最后的长方形满足基线条件即——一边为另一边的整数倍然后将这个长方形分成两个方形将不会余下任何面积

由此，我们就可以得出该长168cm宽64cm的长方形可以被最长为8cm的方块给容纳

根据D&C提供的思路，我们可以很轻松的使用Java来解决这一类为题，大家可以尝试去打一下代码看一下根据这个思路是否可以做出来

下面是博主用JAVA实现这一问题的代码实现

​​
ublic class study {
        public static void main(String[] args) {
            int length = 168; // 长方形的长度
            int width = 64; // 长方形的宽度
            int maxSquareSize = divideRectangle(length, width); // 调用分割长方形的方法
 
            System.out.println("最大正方形的边长为: " + maxSquareSize);
        }
        // 分割长方形的方法
        public static int divideRectangle(int length, int width) {
            // 如果长度和宽度相等，则直接返回边长
            if (length == width) {
                return length;
            }
 
            // 找到较大的一边和较小的一边
            int maxSide = Math.max(length, width);
            int minSide = Math.min(length, width);
 
            // 计算较大一边除以较小一边的商和余数
            int quotient = maxSide / minSide;
            int remainder = maxSide % minSide;
 
            // 如果余数为0，则表示可以整除，最大正方形边长为较小一边
            if (remainder == 0) {
                return minSide;
            }
            // 递归调用分割长方形的方法，对剩余部分进行分割
            return divideRectangle(minSide, remainder);
        }

当然这一题其实用求最大公约数使用欧几里得算法更快，如果使用递归做不出来也不用太纠结，博主也仅是举个例子，像这样类题目还是使用其他方法更优。

二.快速排序

1.说明

快速排序是我们经常使用的一种排序算法，比选择排序的效率要快上不少，它也是D&C的拓展的典型算法

2.快速排序的思路

1.选取基线条件

首先上文中提到了快速排序法是D&C的一种拓展，所以一样和D&C的思路一样，我们首先要选定好基线条件，而数组最简单不需要排序的是时候什么情况呢，很简单就是当数组为空或者就只有一个元素的时候，在这种情况下我们只需要返回数组就好。

2.数组中有两个元素时

我们要把两个元素的数组排序只需要比较两个元素的大小后调换位置就好。这很简单，博主就不过多的叙述了。

3.数组中有三个元素时

这个时候你就可以使用D&C了，因此我们需要将数组给“缩小”，直到满足基线条件，首先我们先选定一个基准值-----这个值你可以随便选。

随后我们把数组的每一个元素和基准值比较，把小于基准值的元素分在一边，把大于基准值的元素分在一边，假设我们选定25为基准值

这样你就有三个部分

1.小于基准值的子数组------15和5

2.大于基准值的另一个子数组---------空数组

3基准值

进行了分区后，如果你的两个子数组是有序的，那对整个数组的排序就非常简单了，假如说不是呢，那就再对两个子数组进行快速排序就好直到它们达到基准条件的时候再合并起来这可以把整个数组排序了。

就像这题我们对小于基准值的子数组进行快速排序，随便选一个作为基准值

现在两个数组都符合基准条件了----数组为空或者一个元素，然后合并就可以得到整个数组的排序了

再假如我们选15为基准值

可以看出我们两个子数组都符合基准条件，直接合并即好，所以说我们无论选择那个作为基准值都可以，当然选择一个好的基准值可以提升一点效率，当然也只是对于元素数量少的时候。

4..数组中有四个元素时

假设我们选择35为基准值

左边数组有三个元素而既然知道了三个元素这么快速排序，只要对其递归地用快速排序即可

5.五个以及五个以上元素时

既然我们以及知道了两个元素，三个元素，以及四个元素的快速排序，那我们要如何解决五个以及更多元素的情况呢，很简单只要我们选定好基准值，然后把整个数组分为三个部分，如果满足有序或者满足基准条件，那就返回合并。

3.Java代码实现

现在博主假设数组 arr={5，13，9，27，16，4，8}要使用快速排序法的Java代码如何实现，你看完快速排序法的思路后是否可以做出来呢，可以自己下去试一试。

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 13, 9, 27, 16, 4, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
 
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            // 选取一个基准数
            int pivot = partition(arr, left, right);
            // 对基准数左边的子数组进行快速排序
            quickSort(arr, left, pivot - 1);
            // 对基准数右边的子数组进行快速排序
            quickSort(arr, pivot + 1, right);
        }
    }
 
    public static int partition(int[] arr, int left, int right) {
        // 选取最右边的数作为基准数
        int pivot = arr[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                // 如果当前数比基准数小，将它和i+1位置的数交换
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 将基准数放到i+1位置
        int temp = arr[i + 1];
        arr[i + 1] = arr[right];
        arr[right] = temp;
        // 返回基准数的位置
        return i + 1;
    }
}

三.说明

以上就是博主对快速排序法的一点点小看法，可能有些地方又没说明白，还请多多谅解，感谢你的阅读，让我们一起学习共同进步。