【我的Java学习笔记】排序算法：快速排序

清疚 2023-09-24 13:36 109阅读 0赞

九层之台，起于垒土，你我皆是垒土人  
欢迎关注点赞，共同学习进步！

> 前言：七大排序之快速算法，总的来说并不算容易理解，需要自己去亲手实践和思考。

#### 文章目录 ####

*  1、快速排序
 *   *  1.1排序算法
 *  2、快速排序原理
 *   *  2.1 排序原理解析
 *  3、快速排序的实现
 *   *  3.1 一组无序数据：
     *  3.2 实现结果
 *  4、完整代码

--------------------

## 1、快速排序 ##

### 1.1排序算法 ###

> 首先要明白快速排序算法其实也是交换排序的一种  
> ![在这里插入图片描述][3618d1ad16eb4987b5ccb3b43881da93.png]

--------------------

## 2、快速排序原理 ##

### 2.1 排序原理解析 ###

> 快速排序原理是在数据头部或尾部设立一个Key，然后分别左边left以及最右边right反向遍历，如果right指针找到比Key小的数则暂停，当left指针找到比Key值大的数时暂停，交换left和right的值，直到它们相遇，那么交换left和Key的值，并且返回left，这个Key索引就是数据中的中间值，Key的左边都比其小，右边比其大。  
> 动图演示如下：
> 
> ![在这里插入图片描述][79b811222ec7462f98ad8b81b49ce019.gif_pic_center]

public static int  PartSort(int Arrys[],int left,int right)
        {
        
            int Key=left;//设置最左边为Key
    
            while (left<right){
        
    
                while (left<right && Arrys[right]>=Arrys[Key] ) //先右向左开始找小于Key的值
                {
        
                    right--;
                }
    
                while (left<right && Arrys[left]<=Arrys[Key] )//从左向右边开始找大于Key的值
                {
        
                    left++;
                }
    
                //如果满足条件就交换left和right的值
                int Middle=Arrys[left];
                Arrys[left]=Arrys[right];
                Arrys[right]=Middle;
            }
            //最后left和right相遇，交换left和Key值，并返回left，即找到数据中的中间值位置
            int Middle=Arrys[left];
            Arrys[left]=Arrys[Key];
            Arrys[Key]=Middle;
            return left;
        }

## 3、快速排序的实现 ##

> 通过局部的单词快速排序获得Key的位置，再将数据分割成Key左右两个部分，通过递归实现多次排序，当begin和end值相等时退出，实现最后的排序。

### 3.1 一组无序数据： ###

![给出一组数据][b7654e0701b54dc087e9c05f54387aee.png]

--------------------

public  static void QuickSort(int Arrys[],int begin,int end)
        {
        
            if (begin>=end)
                return;
            int Key=PartSort(Arrys,begin,end);
            QuickSort(Arrys,begin,Key-1);
            QuickSort(Arrys,Key+1,end);

### 3.2 实现结果 ###

![在这里插入图片描述][7892d18cdf5f4f42a9e05df5861f9fd5.png]

***请问你学会了吗？？  
欢迎点赞关注！！***

## 4、完整代码 ##

public class QuickSort {
        
        public static void main(String args[])
        {
        
            int Arrys[]={
        32,18,23,45,79,88,20,84,97,6};
    
            QuickSort(Arrys,0,Arrys.length-1);
            for(int i:Arrys)
            {
        
                System.out.print(i+",");
            }
        }
        public static int  PartSort(int Arrys[],int left,int right)
        {
        
            int Key=left;//设置最左边为Key
    
            while (left<right){
        
    
                while (left<right && Arrys[right]>=Arrys[Key] ) //先右向左开始找小于Key的值
                {
        
                    right--;
                }
    
                while (left<right && Arrys[left]<=Arrys[Key] )//从左向右边开始找大于Key的值
                {
        
                    left++;
                }
    
                //如果满足条件就交换left和right的值
                int Middle=Arrys[left];
                Arrys[left]=Arrys[right];
                Arrys[right]=Middle;
            }
            //最后left和right相遇，交换left和Key值，并返回left，即找到数据中的中间值位置
            int Middle=Arrys[left];
            Arrys[left]=Arrys[Key];
            Arrys[Key]=Middle;
            return left;
        }
        public  static void QuickSort(int Arrys[],int begin,int end)
        {
        
            if (begin>=end)
                return;
            int Key=PartSort(Arrys,begin,end);
            QuickSort(Arrys,begin,Key-1);
            QuickSort(Arrys,Key+1,end);
    
    
        }
    
    
    }

[3618d1ad16eb4987b5ccb3b43881da93.png]: https://img-blog.csdnimg.cn/3618d1ad16eb4987b5ccb3b43881da93.png
[79b811222ec7462f98ad8b81b49ce019.gif_pic_center]: https://img-blog.csdnimg.cn/79b811222ec7462f98ad8b81b49ce019.gif#pic_center
[b7654e0701b54dc087e9c05f54387aee.png]: https://img-blog.csdnimg.cn/b7654e0701b54dc087e9c05f54387aee.png
[7892d18cdf5f4f42a9e05df5861f9fd5.png]: https://img-blog.csdnimg.cn/7892d18cdf5f4f42a9e05df5861f9fd5.png