带你逐句代码实现快速排序算法 Java

写代码前先把逻辑思路写出来,循环的起始和结束判断标志写出来,需要输入和输出的参数都理清,一句一句翻译成代码就行

1.已知一个数组,我们需要选取一个轴,在一次排序后,让比轴小的数都排在轴前边,让比轴大的数都排到轴后面
2.经过上一步,我们可以把数组看成两个新的数组,一个是轴之前的那些数,一个是轴之后的那些,轴就放那了不用动了
3.然后对新的俩数组分别进行第一步操作,然后再第二步,循环套娃
4.套娃到什么时候结束呢,到新分出来的数组就只包含一个元素,用代码写判断条件就是 数组开头索引不小于结尾索引(就是开头和结尾的元素索引重合了,不就是只有一个数么)

这时还有个问题,上面的第一步,具体是如何操作使轴前边的都比轴小,轴后面的比轴大呢?下面理一下:

1.1 选取一个轴位,其实是任意选取的,不过为了代码好写,一般选头或者尾,我这里选头吧,就是第一个元素,假设数组是arr[arr.length],那轴就是arr[0]了。

1.2 在这个数组的首尾,分别设置指针,假设头指针是i,尾指针是j,那么首先指针j向前移动,一直动到比轴小的那个数,停下! 然后指针i再往后动,一直到发现指的数比轴大,停下,
此时数组是这样的:
[轴,x,x,x,x,x,比轴大的,x,x,x,x,x,比轴小的,x,x,x]

1.3将两个指针指的数交换位置
此时数组变成了这样:
[轴,x,x,x,x,x,比轴小的,x,x,x,x,x,比轴大的,x,x,x]

这不就排好了三个数?然后继续循环1.2操作直到指针i和j重合,使指针i前面的比轴小,指针i后面的比轴大,数组变成下面这样:
[轴,比轴小的一堆,比轴大的一堆]

1.4 将轴和比轴小的交换
数组变成这样:
[比轴小的一堆,轴,比轴大的一堆]
这不就初步排好了?然后就可以分数组继续把子数组里面的数排序了

以上就是第一大步的全部操作了,进行第二大步的时候又出现了一个问题:“新的俩数组我怎么划分的啊?新建两个临时数组吗?” 答:显然不是,我们设置两个索引,头和尾,来把新的两个数组从最开始的arr里面切出来进行下一步处理。 下面再理一下具体操作:

2.2 经过第一步数组变成了[比轴小的一堆,轴,比轴大的一堆]
2.3我们要处理的两个子数组其实是“比轴小的一堆”和“比轴大的一堆”,用arr的索引来划分就是
[0, 轴索引-1]和[轴索引+1,arr.length-1]

这里注意,这一层的轴,其实就是下一层子数组的头和尾,所以我们在设计递归函数的时候需要把轴的索引传出来,给下一轮处理用,就是传出指针i,因为指针i是轴最后被换到的位置。

以上就是所有步骤了,下面我们按步骤翻译成代码即可

先写个交换函数

    public static void swap(int[] arr, int a, int b) { 
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

下面正片开始
1.1-1.4步

public static int huafen(int[] arr, int low, int high) { 
        //设置一个轴,用来被比较,这里选第一个数,low就是子数组开头的那个索引,high是尾部
        int zhou = arr[low];
        int i = low;
        int j = high;

		//1.2步 选出来两个数
        while (i < j) { 
            while (arr[j] >= zhou&&i<j) { 
                j--;
            }
            while (arr[i] <= zhou&&i<j) { 
                i++;
            }
            // 1.3步在这交换选出来这俩
            swap(arr, i, j);
        }
        //1.4步 把轴换到中间,小的换到开头
        swap(arr, i, low);
        return i;
}

2-4步

    public static void sort(int[] arr, int low, int high) { 
        if (low < high) { 
            int index = huafen(arr, low, high);
            sort(arr, low, index - 1);
            sort(arr, index + 1, high);
        }
    }

我们最后再封装一层,不然输入时候还要输入数组的头和尾索引很麻烦,第一层就是0和数组长度-1。

    public static void kuaisu_method(int[] arr) { 

        sort(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr)); //这直接打印一下排序完的结果
    }

最后把完整的代码放出来

package SORTS;

import java.util.Arrays;

public class kuaisu extends tool_method { 

    public static void kuaisu_method(int[] arr) { 

        sort(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }


    public static void sort(int[] arr, int low, int high) { 
        if (low < high) { 

            int index = huafen(arr, low, high);
            sort(arr, low, index - 1);
            sort(arr, index + 1, high);
        }
    }

    // int[] array1 = {23, 43, 5, 67, 23, 32, 56, 87, 2};
    public static int huafen(int[] arr, int low, int high) { 
        //设置一个轴,用来被比较,这里选第一个数
        int zhou = arr[low];
        int i = low;
        int j = high;

        while (i < j) { 

            while (arr[j] >= zhou&&i<j) { 
                j--;
            }

            while (arr[i] <= zhou&&i<j) { 
                i++;
            }


            swap(arr, i, j);

        }
        swap(arr, i, low);


        return i;

    }

    public static void swap(int[] arr, int a, int b) { 
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

今天就到这,明天继续学mo习yu

    原文作者:RookieZc
    原文地址: https://blog.csdn.net/qq_41132565/article/details/107734923
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞