java快速排序算法的原理是什么?快速排序算法的实现_java自学_java相关资讯_成都java培训机构

java快速排序算法的原理是什么?快速排序算法的实现

  • 作者:创始人
  • 发表时间:2021-12-17 09:46:42

Java排序中有一个算法叫做快速排序,你知道Java快速排序算法的原理是什么?快速排序算法的实现。

快速排序是冒泡排序的升级,它们都属于交换类,都是通过不断地比较和移动来实现排序。快序是一种非常高效的排序算法,它的实现,增加了记录的比较和移动的距离,将关键字较大的记录从前面直接移到后面,关键字较小的记录从后面移到前面,这样就减少了总的比较和移动次数。

与此同时,我们也采取了分而治之的思想,将大的拆分为小的、小的,原则是:对给定的一组记录,选择一个基准元素,一般情况下,第一个或最后一个元素被选中,通过一次扫描,将这个待排序列分割为一部分小于基准元素的两部分,现在,基准元素排列顺序完成之后,再使用相同的方法对这两部分进行递归排序,直到序列中的所有记录都按顺序排列。

java快速排序算法的原理是什么

快速排序算法的实现

import java.util.Arrays;

public class TestQuickSort {

        private static int partition(int[] arr, int low, int high) {

                //指定左指针i和右指针j

                int i = low;

                int j= high;

                //将第一个数作为基准值。挖坑

                int x = arr[low];

                //使用循环实现分区操作

                while(i<j){//5  8

                        //1.从右向左移动j,找到第一个小于基准值的值 arr[j]

                        while(arr[j]>=x && i<j){

                                j--;

                        }

                        //2.将右侧找到小于基准数的值加入到左边的(坑)位置, 左指针想中间移动一个位置i++

                        if(i<j){

                                arr[i] = arr[j];

                                i++;

                        }

                        //3.从左向右移动i,找到第一个大于等于基准值的值 arr[i]

                        while(arr[i]<x && i<j){

                                i++;

                        }

                        //4.将左侧找到的打印等于基准值的值加入到右边的坑中,右指针向中间移动一个位置 j--

                        if(i<j){

                                arr[j] = arr[i];

                                j--;

                        }

                }

                //使用基准值填坑,这就是基准值的最终位置

                arr[i] = x;//arr[j] = y;

                //返回基准值的位置索引

                return i; //return j;

        }

        private static void quickSort(int[] arr, int low, int high) {//???递归何时结束

                if(low < high){

                        //分区操作,将一个数组分成两个分区,返回分区界限索引

                        int index = partition(arr,low,high);

                        //对左分区进行快排

                        quickSort(arr,low,index-1);

                        //对右分区进行快排

                        quickSort(arr,index+1,high);

                }

        

        }

        public static void quickSort(int[] arr) {

                int low = 0;

                int high = arr.length-1;

                quickSort(arr,low,high);

        }

        public static void main(String[] args) {

                //给出无序数组

                int arr[] = {72,6,57,88,60,42,83,73,48,85};

        //输出无序数组

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

        //快速排序

        quickSort(arr);

        //partition(arr,0,arr.length-1);

        //输出有序数组

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

        }    

}

java快速排序算法的原理是什么?快速排序算法的实现。关注成都Java培训机构,带你了解更多相关问题。