快排Java实现

作者: 爱学习的代代 | 来源:发表于2022-02-24 20:49 被阅读0次

快排Java实现
常见排序的java实现
排序
快排-Java
Java 快排
Java快排
转载：快排实现
js实现快排
快排递归实现
三种快排优化Java实现

1、快排的核心思想：

1、从无序的数组中找到一个枢轴元素M，将数组一分为二：如将数组的第一个元素设置为枢轴元素。
2、然后从数组的左右开始找元素：
满足的规则是

a、从右侧开始找比枢轴元素M小的元素，如果找到将该元素X（right）跟枢轴元素M交换位置，即更小的数字换到了数组前面。
b、再从左侧开始找比枢轴元素M大的元素，如果找到将该元素Y（left）跟枢轴元素M交换位置，即更大的数字换到了数组后面。
c、对a,b步骤交替进行。
d、最终的时候，right和left会重合，且该位置放置M元素。`

3、此时将数组，在M的前面都是比M小的元素，在M的后面都是比M大的元素。
4、然后分别对M前面元素组成的数组，M元素后的元素组成的数组递归调用2步骤封装的方法即可

java版本代码实现如下：



package com.example.demo.chapter06.controller;

import java.util.Arrays;

public class Solution {

    public static void main(String[] args) {
        quickSort(new int[] {39,28,55,87,66,3,17,40});
    }


    public static void quickSort(int[] arr) {
//      快排传入的内容： 数组，数组开始的位置，数组的末尾。
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    // arr 代表目标数组
    public static void quickSort(int[] arr, int left, int right) {
//      保存每次排序后，分界点的在数组中的位置
        int middle;
        if (left < right) {
//          返回每次排序后，分界点在数组中的位置。比如返回的3， 则是代表分界值在数组的第4个位置。
            middle = partition(arr, left, right);
            System.out.println(middle);
//          分别对于分界值两侧的数组，进行递归调用。
//          对于左侧数组：left 第一次是传入的初始位置， right则是分界值的位置-1。
//          对于右侧数组，left 是分界值的位置+1， right是最后的位置。
            quickSort(arr, left, middle-1);
            quickSort(arr, middle+1, right);
        }

    }

    /**
     *
     * @param arr
     * @param left
     * @param right
     * @return  最终分界值的索引位置。
     */
    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        while (left < right) {
//          当右边的元素如果比标志位一直大的话，就不断执行该循环。
//          当从右侧找到了比其小的元素，就将该元素与标志位置交换位置。
            while (left < right && arr[right] >= pivot) {
                right--;
            }
//          将找到的数，放置到设置的目标值上。  此时arr[right]相当于置为空了
            arr[left] = arr[right];

            // 左边查找的方式.  当遍历元素小于标识位的时候，进行移动。
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //          将找到的数，放置到设置的目标值上。 此时arr[left]相当于置为空了
            arr[right] = arr[left];

        }
//      将最终的目标值（分界线值），放置到arr[left] 上
        arr[left] = pivot;
        return left;
    }


}

测试结果：