快速排序

快速排序

快速排序的基本思想是从数组中取一个值作为轴，然后遍历数组将比该值小或与该值相等的元素移动到数组的左部分，将比该值大的元素移动到数组的右部分，然后对左右部分使用递归进行相同操作，下面通过一个示例演示下快排的操作流程
假定初始数组为：{2,5,7,1,3,4}，每次都以数组的末尾元素作为轴

那么初始时轴为4，进行一轮快速排序的规则后得到的数组为{2,1,3,4,5,7}，对应得到的左子数组为{2,1,3}，右子数组为{5,7}

然后对左子数组{2,1,3}进行快排操作(对右子数组{5,7}做的操作类似)，取3作为轴，得到的左子数组为{2,1}，右子数组为空集

然后对左子数组{2,1}进行快排操作，取1作为轴，得到的右子数组为{2}，单元素数组本身就是有序的，触发递归base case，结束方法的执行

对应的算法代码为：

static void quick(int[] arr, int start, int end) {
    if (start >= end) return;//base case
    int pivort = arr[end];//取数组末尾元素作为轴
    int left = start, right = end - 1;//初始化头尾索引
    while (left < right) {
        //寻找比轴大的元素所在索引，括号内的两条件的前后位置不可交换(会导致有些情况排序不正确)
        while (left <= right && arr[left] <= pivort) left++;
        while (left <= right && arr[right] > pivort) right--;//寻找小于等于轴的元素所在的索引
        if (left < right) Utils.swap(arr, left++, right--);//交换值并对索引移动到下一个位置
    }
    //最后如果left指向的值比轴大，则将轴移动到left索引处，加个判断是为了避免从数组中取到的轴为数组最大值时无条件交换导致结果出错
    if (arr[left] > pivort)
        Utils.swap(arr, left, end);
    quickSort(arr, start, left - 1);//左部递归操作
    quickSort(arr, left + 1, end);//右部递归操作
}

测试排序结果

通过对数器的方式进行排序结果的验证

public static void main(String[] args) {
    int size = 30;
    int[] arr1 = Utils.generateRandomArray(size, 100);
    int[] arr2 = new int[arr1.length];
    System.arraycopy(arr1, 0, arr2, 0, arr1.length);
    System.out.println("原数组：		" + Arrays.toString(arr1));
    Arrays.sort(arr1);
    System.out.println("内置排序后：	" + Arrays.toString(arr1));
    quick(arr2, 0, arr2.length - 1);
    System.out.println("快速排序后：	" + Arrays.toString(arr2));
}

原数组：	[93, 46, 71, 98, 11, 89, 26, 28, 96, 93, 15, 1, 19, 21, 90, 25, 66, 3, 53, 57, 87, 90, 74, 81, 64, 87, 65, 87, 14, 6]
内置排序后：	[1, 3, 6, 11, 14, 15, 19, 21, 25, 26, 28, 46, 53, 57, 64, 65, 66, 71, 74, 81, 87, 87, 87, 89, 90, 90, 93, 93, 96, 98]
快速排序后：	[1, 3, 6, 11, 14, 15, 19, 21, 25, 26, 28, 46, 53, 57, 64, 65, 66, 71, 74, 81, 87, 87, 87, 89, 90, 90, 93, 93, 96, 98]

如果对你有帮助，点个赞，或者打个赏吧，嘿嘿
整理不易，请尊重博主的劳动成果