亲宝软件园·资讯

展开

排序算法图解之Java快速排序的分步刨析

兴趣使然黄小黄 人气:0

1.快速排序简介

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

2.思路简介及图解

快速排序算法通过多次比较和交换来实现排序,其排序流程如下:

(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。

(3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。

(4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

光看思路简介其实还不是很好理解,下面来举例说明

一般情况下,我们会把数组中的一个数当作基准数(方便起见,会将数组最左边的当作基准数),然后从两边进行检索。按照如下步骤进行:

思路图解:

该图出自网络,方便起见就以序列:{6,1,8,0,0,9,5,3,7} 为例子

具体分析一下第一趟排序:以6为基准数的步骤

1.红色块标识基准数,left、right初始位置如图所示:

2.right不断向左移动,寻找比基准数小的数,如图所示,找到了3

3.此时left开始移动,不断向右移动,寻找比基准数大的数,找到了8,这时,left、right都找到了对应的数,进行交换:

4.right继续向左寻找比基准数6小的数,找到后,left继续向右寻找比基准数大的数,当left与right都找到对应的数后,再次进行交换。

5.重复上述步骤,right继续向左走,但是此时,left与right相遇,指向了5的位置,则将基准数与该位置的数进行交换,这样就可以观察到,6的左边都是比6小的,右边都是比6大的。

6.该过程需要递归进行,直到序列有序。即以5为基准数,递归6左边的区间,再递归右边的,反复进行,直到left >right退出。

3.实现代码及运行结果

import java.util.Arrays;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 快速排序
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {6,1,8,0,0,9,5,3,7};
        quickSort(arr, 0, arr.length-1);
        System.out.println("排序后: " + Arrays.toString(arr));
    }

    //快速排序
    public static void quickSort(int[] arr, int left, int right) {
        //边界条件
        if (left > right){
            return;
        }

        //定义基准数和左右指针
        int l = left;
        int r = right;
        int base = arr[left];

        //循环,将比基准数小的放在左边,比基准数大的放在右边
        while (l != r){
            //先从右边找比基准数小的,停下
            while (arr[r] >= base && l < r){
                r--;
            }
            //从左边找比基准数大的,停下
            while (arr[l] <= base && l < r){
                l++;
            }
            //此时已经找到对应的l 和 r,进行交换
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        //至此,基准数两边都按照需要排好了,只需要将基准数与lr相遇的位置进行交换
        arr[left] = arr[l];
        arr[l] = base;
        //打印中间结果
        System.out.println(Arrays.toString(arr));
        //先向左找
        quickSort(arr, left, r-1);
        //向右递归
        quickSort(arr, l+1, right);
    }
}

实现结果:

加载全部内容

相关教程
猜你喜欢
用户评论