快速排序法（java版,分治法,递归）

短命女 2023-10-01 21:18 3阅读 0赞

#### **快速排序法介绍:** ####

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

#### 快速排序 法示意图:   ![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_13_color_FFFFFF_t_70_g_se_x_16][] ####

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_7_color_FFFFFF_t_70_g_se_x_16][]

#### 快速排序法代码实现: ####

import java.util.Arrays;
    import java.util.Random;
    
    public class QuickSort {
    
        public static void main(String[] args) {
    
    
            //产生一个随机数组
            Random r = new Random();
            int arr[] = new int[20];
            for(int i=0;i<arr.length;i++){
                //让随机数有正有负
                if(r.nextInt()%2==0){
                    arr[i] =-r.nextInt(300);
                }
                else {
                    arr[i] =r.nextInt(300);
                }
            }
            System.out.println("排序前:"+Arrays.toString(arr));
            quickSort(arr, 0, arr.length - 1);
            System.out.println("排序后:"+Arrays.toString(arr));
        }
    
    
    
    
        public static void quickSort(int[] arr, int left, int right) {
            int l = left;//左下标
            int r = right;//右下标
            int pivot = arr[(left + right) / 2];//中轴值
            int temp=0; //临时存储变量
            while (l <= r) {
                while (arr[l]<pivot){
                    l++;
                }
                while (arr[r]>pivot){
                    r--;
                }
                if (l>=r){
                    break;
                }
                //交换
                temp=arr[r];
                arr[r]=arr[l];
                arr[l]=temp;
    
    
                if (arr[l]==pivot){
                    r--;
                }
                if (arr[r]==pivot){
                    l++;
                }
    
            }
    
            if (l==r){
                l++;
                r--;
            }
            //向左递归
            if (left<r){
                quickSort(arr,left,r);
            }
    
            //向右递归
            if (right>l){
                quickSort(arr,l,right);
            }
    
        }
    
    }

运行结果：

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_20_color_FFFFFF_t_70_g_se_x_16][]

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_13_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/90088645284d4e228aa8b6800f590d2e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_13,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_7_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/d7fcbe1030d743628694880a6618e804.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_7,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/733b70937baa46edbab41241153673b3.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiA5Liq54Ot54ix57yW56iL55qE5bCP55m955m9,size_20,color_FFFFFF,t_70,g_se,x_16