快速排序-java版本

一、原理

1. 选择待排数组区间内最后一个元素作为基准
2. 小于此基准的放在此元素的左边
3. 大于此基准的放在此元素的右边
4. 最后把此基准交换到此数组的应该位置
5. 最后分别针对基准左区间和右区间分别做递归排序

package org.example;

import java.util.Arrays;

public class SortTest {
    void quickSort(int[] arr, int s, int e) {
        if (s<e) {
            int i = quickSortCore(arr, s, e);
            quickSortCore(arr,s, i-1);
            quickSortCore(arr,i+1, e);
        }
    }

    int quickSortCore(int[] arr, int s, int e) {
       int p = arr[e];
       int lp = s-1; // 小于基准的位置
        for (int i = s; i < e; i++) {
            if (arr[i]<p) {
                lp++;

                int tmp = arr[lp];
                arr[lp] = arr[i];
                arr[i] = tmp;
            }
        }

        // 把基准转移到正确的位置
        int tmp = arr[lp+1];
        arr[lp+1] = arr[e];
        arr[e] = tmp;

        return lp+1;
    }

    public void main(String[] args) {
        int[] arr = {1,3,8,7,5};

        this.quickSort(arr,0, arr.length-1);

        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}