快速排序详解包含图片演示步骤

brent-leon 2020-01-15 原文

最近从网上看了很多快排的博客,发现有的不是那么容易理解,有的存在些许的错误.

无奈自己研究了下快排,现在做一下记录,可能也会有些许的漏洞,如果有的话请大家提出我再做修改.

下面是需要排序的原始数据：

首先我们要了解快排的基本逻辑,

　　1. 获取一个基准数,该基准数位置为坑位.定义两个角标,起始,终点,坑位为基准数,不用比较.

　　2. 从右往左跟基准数比较,当当前数小于基准数时, (1).把当前数放到坑位. (2).当前数位置变为坑位.

　　3. 接下来从左往右跟基准数比较,当当前数大于基准数时, (1).把当前数放到坑位. (2).当前数位置变为坑位.

　　4. 接着循环执行2,3步,直到起始角标不小于终点角标.这时把基准数赋值到坑位,结果如下

接下来就是循环调用了,怎么循环呢,把基准数前后分别进行调用

到这儿就算是结束了.
下面贴一下代码.

public static void main(String[] args) {
        //需要排序的数组中包含重复数字
        int[] arr = {4,3,34,12,3,8,6,9,12,2,1,4};
        System.out.print("排序前:");
        for (int i: arr){
            System.out.print(i + ",");
        }
        System.out.println();
        new QuickSort().quickSortMethod(arr,0,arr.length-1);
        System.out.print("排序后:");
        for (int i: arr){
            System.out.print(i + ",");
        }
    }

    public void quickSortMethod(int[] arr,int left,int right){
        if(left >= right){
            return;
        }
        int zhouxin = arr[left];
        //定义i是为了不用重复排序已知排好的结果
        int i = left;
        //定义j是记录需要排序的最大角标
        int j = right;
        while (left < right){
            while (zhouxin < arr[right] && left < right){
                right--;
            }
            if(left < right){
                //这儿使用left++,是为了赋值后下次比较时直接比较下一个角标的值.下面的right--同理
                arr[left++] = arr[right];
                while (arr[left] < zhouxin && left < right){
                    left++;
                }
                arr[right--] = arr[left];
            }
        }
        if(i == left){
            i++;
            left = j+1;
        }else{
            arr[left] = zhouxin;
        }
        quickSortMethod(arr,i,left-1);
        quickSortMethod(arr,left+1,j);
    }