数据结构之排序算法——快速排序（Java实现）-蒲公英云

数据结构之排序算法——快速排序（Java实现）

桃扇骨 2023-03-13 05:55 97阅读 0赞

➢ 基本介绍

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

➢ 思路分析图解
使用一个简单特殊的测试数组作为基本。
在这里插入图片描述
代码实现：

public static void fast(int[] arr, int left, int right) { 
        int L = left; // 左下标
        int R = right; // 右下标
        int middle = arr[(left + right) / 2]; // 中间值
        int temp = 0;
        // 把数据大小放于左右俩边
        while (L < R) { 
            while (arr[L] < middle) { 
                L += 1;
            }
            while (arr[R] > middle) { 
                R -= 1;
            }
            // L >= R条件满足，表示左右两边的值都满足
            if (L >= R) { 
                break;
            }
            // 交换,
            temp = arr[R];
            arr[R] = arr[L];
            arr[L] = temp;
            // 交换之后，arr[L] == middle R-- 前移
            if (arr[L] == middle) { 
                R--;
            }
            // 交换之后，arr[L] == middle L++ 后移
            if (arr[R] == middle) { 
                L++;
            }
        }
        // 递归排序，如果L==R L++ R--
        if (L == R) { 
            L++;
            R--;
        }
        // 向左递归
        if (left < R) { 
            fast(arr, left, R);
        }
        // 向右递归
        if (right > L) { 
            fast(arr, L, right);
        }
    }

测试代码：调用函数传递数组即可：

int[] arr = {  -9, 78, 0, 23, -567, 70 };
        fast(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

在这里插入图片描述
测试快速排序的效率：使用先前的代码进行测试：

int[] arr1 = new int[100000];
        for (int i = 0; i < 100000; i++) { 
            arr1[i] = (int) (Math.random() * 1000000); // 生成一个[0,1000000) 的随机数
        }
        Date a = new Date();
        SimpleDateFormat SimpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String a1 = SimpleDateFormat.format(a);
        System.out.println("排序前：" + a1);
        fast(arr1, 0, arr1.length - 1);
        Date b = new Date();
        String b1 = SimpleDateFormat.format(b);
        System.out.println("排序后：" + b1);