lusiqi

排序算法-快速排序排序，java实现快速排序，算法图形化图解排序步骤。

排序思想

  1. 先从数列中取出一个数作为基准数（一般取数组的第一个元素）
  2. 取数组最低位和最高位分别为左右游标，左右同时扫描，找到左边>基准的数与右边<基准的数据交换
  3. 当右游标<=左游标，即扫描一遍后，将基准数与右游标<基准的数交换，此时基准数左边的数都小于基准数。基准数下标右移一位。
  4. 再对左右区间重复第二步，直到各区间只有一个数。

算法图形化

测试数据：data[]=${arr}

代码实现

排序代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/**
 * @description 快速排序算法实现
 * @author dxy
 * @date 2019-12-10
 */
@Service("quickSortService")
public class QuickSortServiceImpl implements IQuickSortService {

    //步骤-全
    private static Integer allStep = 0;
    //步骤-真实的交换，去除不交换的步骤
    private static Integer realStep = 0;

    /**
     * 快速排序算法：
     * 1. 先从数列中取出一个数作为基准数（一般取数组的第一个元素）
     * 2. 取数组最低位和最高位分别为左右游标，左右同时扫描，找到左边>基准的数与右边<基准的数据交换
     * 3. 当右游标<=左游标，即扫描一遍后，将基准数与右游标<基准的数交换，此时基准数左边的数都小于基准数。基准数下标右移一位。
     * 4. 再对左右区间重复第二步，直到各区间只有一个数。
     * @param
     * @throws Exception
     */
    @Override
    public List<QuickSortResult> sort(Comparable[] arrays) throws Exception {

        //将数组随机打乱
        //StdRandom.shuffle(arrays);

        allStep = 0;
        realStep = 0;

        //快速排序，将数组的第一个元素作为第一个
        sort(arrays, 0, arrays.length - 1);

        //验证是否有序
        assert SortUtil.isSorted(arrays);

        return resultList;

    }

    /**
     * 快速排序
     * @param arrays 需要排序的数组
     * @param var1 基准数的下标
     * @param var2 比较数的下标
     */
    private static void sort(Comparable[] arrays, int var1, int var2) {

        //如果比较数数组下标 > 基准数，当切分数组只剩一个元素停止递归
        if (var2 > var1) {
            //切分，将数组以基准数为分割点，左边都是小于基准的数，右边都是大于基准的数
            int var3 = partition(resultList,arrays, var1, var2);
            //递归，将左半部分排序
            sort(resultList,arrays, var1, var3 - 1);
            //递归，将右半部分排序
            sort(resultList,arrays, var3 + 1, var2);

            assert SortUtil.isSorted(arrays, var1, var2);

        }
    }

    /**
     * 切分
     * 将小于基准的数放在基准数的左边，大于基准的数放在基准数右边
     * 返回基准数的最后位置
     * @param arrays 数组
     * @param var1 基准数
     * @param var2 比较数
     * @return 基准数最后位置
     */
    private static int partition(Comparable[] arrays, int var1, int var2) {

        //基准数下标
        int var3 = var1;
        //比较数下标右移
        int var4 = var2 + 1;

        //基准数
        Comparable var5 = arrays[var1];

        while(true) {

            do {
                //比较数从左向右
                ++var3;

            } while(SortUtil.less(arrays[var3], var5) && var3 != var2);//从左向右扫描，碰到第一个大于等于基准的数跳出循环，全扫描一遍没有也跳出循环

            do {
                //比较数从右向左
                --var4;
            } while(SortUtil.less(var5, arrays[var4]) && var4 != var1);//从右向左扫描，碰到第一个小于等于基准的数跳出循环，全扫描一遍没有也跳出循环

            //当左右所有的数都与基准数比较完后
            if (var3 >= var4) {

                if(var1!=var4) {

                    //将基准数与右边最后一个小于基准的数交换位置
                    SortUtil.exch(arrays, var1, var4);

                    //打印数组
                    SortUtil.show(arrays);
                }
                //返回基准数新的位置，此时基准左边都是小于基准的数，右边都是大于基准的数
                return var4;
            }

            if(var3!=var4){

                //将左边大于基准和右边小于基准的数交换位置，然后继续扫描左右
                SortUtil.exch(arrays, var3, var4);
            }

            //打印数组
            SortUtil.show(arrays);
        }
    }


}

工具类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/**
 * @description 排序工具类
 * @author dxy
 * @date 2019-12-11
 */
public class SortUtil {

    /**
     * 元素比较
     * @param var0
     * @param var1
     * @return var0<var1 则返回true
     */
    public static boolean less(Comparable var0, Comparable var1) {
        return var0.compareTo(var1) < 0;
    }

    public static boolean less(Object v, Object w, Comparator comparator) {
        return comparator.compare(v, w) < 0;
    }

    /**
     * 元素比较
     * @param var0
     * @param var1
     * @param var2
     * @return
     */
    public static boolean less(Comparable[] var0, int var1, int var2) {
        return var0[var1 - 1].compareTo(var0[var2 - 1]) < 0;
    }


    /**
     * 元素交换
     * @param var0 数组
     * @param var1 下标1
     * @param var2 下标2
     */
    public static void exch(Object[] var0, int var1, int var2) {
        Object var3 = var0[var1];
        var0[var1] = var0[var2];
        var0[var2] = var3;
    }

    /**
     * 数组是否有序
     * @param var0
     * @return
     */
    public static boolean isSorted(Comparable[] var0) {
        return isSorted(var0, 0, var0.length - 1);
    }

    public static boolean isHsorted(Comparable[] var0, int var1) {
        for(int var2 = var1; var2 < var0.length; ++var2) {
            if (less(var0[var2], var0[var2 - var1])) {
                return false;
            }
        }

        return true;
    }

    /**
     * 判断数组中元素1到元素2是否有序
     * @param var0 数组
     * @param var1 元素1
     * @param var2 元素2
     * @return
     */
    public static boolean isSorted(Comparable[] var0, int var1, int var2) {
        for(int var3 = var1 + 1; var3 <= var2; ++var3) {
            if (less(var0[var3], var0[var3 - 1])) {
                return false;
            }
        }

        return true;
    }

    /**
     * 遍历打印数组换行
     * @param var0
     */
    public static void showLn(Comparable[] var0) {
        for(int var1 = 0; var1 < var0.length; ++var1) {
            System.out.println(var0[var1]);
        }

    }

    /**
     * 遍历打印数组不换行
     * @param var0
     */
    public static void show(Comparable[] var0) {
        for(int var1 = 0; var1 < var0.length; ++var1) {
            System.out.print(var0[var1]+"  ");
        }
        System.out.println();

    }
}

 上一篇

 评论