Java算法-快速排序-Java培训

首先看一下实现思路:

然后贴上代码:

package com.czs04;

import java.util.Arrays;

public class AbSortQuick {

    // 快速排序
    // 示例如图: s2.png
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
//            System.out.println(Arrays.toString(arr));
//            System.out.println(pivot);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }


    public static int partition(int[] array, int start, int end) {
        int i = start;//这里存开始时基准的下标，为了循环结束后，相遇值和基准值交换时能找到基准值的下标
        int key = array[start];//这是基准 pivot
        while (start < end) {
            while (start < end && array[end] >= key) {
                end--;
            }
            while (start < end && array[start] <= key) {
                start++;
            }
            swap(array, start, end);
        }
        // 基准点 与 指针重合点交换 (这里双指针相遇, 把基准点放在low最终的位置)
        swap(array, start, i);
        return start;//返回基准下标
    }

    private static void swap(int[] nums, int idx1, int idx2) {
        int temp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = temp;
    }


    public static void main(String[] args) {

        int[] arr = {7, 5, 3, 2, 4, 1, 8, 9, 6};

        //快速排序
        int low = 0;
        int high = arr.length - 1;
        quickSort(arr, low, high);


        System.out.println(Arrays.toString(arr));

    }

}