java 实现快速排序算法

java 实现快速排序算法

java 实现快速排序算法

1.基本原理2.代码实现

1.基本原理

2.代码实现

package com.yl.algorithm;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {9, 7, 3, 30, 20, 50, 10, 5};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));

    }

    private static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            int pos = getDestPosition(arr,startIndex,endIndex);
            quickSort(arr,startIndex,pos-1);
            quickSort(arr,pos+1,endIndex);
        }
    }

    private static int getDestPosition(int[] arr, int startIndex, int endIndex) {
        //9,7,30,20,50,10,5
        //以数组最后一个元素为基准元素
        int basic = arr[endIndex];
        //指针，指向比基准元素小的元素
        int target = startIndex;
        for (int i = startIndex; i < endIndex; i++) {
            //如果发现某个元素比基准元素小，那么就交换指针指向的元素和当前元素的位置
            if (arr[i] <= basic) {
                int temp = arr[i];
                arr[i] = arr[target];
                arr[target] = temp;
                target++;
            }
        }
        //交换基准元素和指针最后指向的的元素的位置
        // ==> 这样以基准元素就可以分割出来两个数组，左边的所有元素都比基准元素小，右边的所有元素都比基准元素大
        // 不断递归，切分，直到最后每个数组仅剩下一个元素的时候
        int temp = arr[target];
        arr[target] = arr[endIndex];
        arr[endIndex] = temp;
        System.out.println(Arrays.toString(arr));
        return target;
    }
}