数据结构之八大排序——快速排序

一、排序过程

在待排序表L[1...n]中任取一个元素pivot作为枢轴（通常情况下取第一个元素为枢轴），通过一趟排序将待排序表划分为独立的两部分L[1...k-1]和L[k+1...n]，使得L[1...k-1]元素都小于pivot，L[k+1...n]元素都大于或等于pivot。

选取第一个元素为枢轴。
j指针负责从右往左依次比较直到找到比基准点小的元素，此时i开始从左往右依次比较直到找到比基准点大的元素，一旦找到二者进行交换，直到i，j重合。
最后枢轴元素与i或j交换(此时i和j重合)。

快速排序

二、代码


public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {3, 6, 4, 1, 9, 6, 5, 8, 7, 2};
        System.out.print("排序前为：");
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
        quick(arr, 0, arr.length - 1);
        System.out.print("排序后为：");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
 
    public static void quick(int[] arr, int low, int high) {
        if (low > high) {
            return;
        }
        //排序完枢轴的下标（将数组分为两部分）
        int k = quicksort(arr, low, high);
        //对第前面小于枢轴的元素进行递归排序
        quick(arr, low, k - 1);
        //对第后面大于枢轴的元素进行递归排序
        quick(arr, k + 1, high);
    }
 
    public static int quicksort(int[] arr, int low, int high) {
        int i = low;
        int j = high;
        //中间变量
        int temp;
        int pivot = arr[low];
        while (i < j) {
            //j从后往前找比枢轴小的元素
            while (i < j && arr[j] > pivot) {
                j--;
            }
            //i从前往后找比枢轴大的元素
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
        //将枢轴元素和i或者j互换
        temp = arr[i];
        arr[i] = arr[low];
        arr[low] = temp;
        return j;
    }
 
}