Java实现快速排序

快速排序：在每一轮挑选一个基准元素，并让其它比它大的元素移动到一边，小于等于它的元素移动到另一边；
思想：分治法
基准元素选择：随机选择与选择第一个等
元素交换：双边交换与单边交换

一、双边遍历交换实现：

import java.util.Arrays;

/**
 * 快速排序
 */
public class FastSortDemo {

    /**
     * 双边循环递归
     *
     * @param arr
     */
    public static void sort(int arr[], int startIdx, int endIdx) {
        if (startIdx >= endIdx) {
            return;
        }
        int baseIdx = getBaseIdxForDoubleLoop(arr, startIdx, endIdx);
        sort(arr, startIdx, baseIdx - 1);
        sort(arr, baseIdx + 1, endIdx);
    }

    /**
     * 获取下一次到基准下标
     * @param arr
     * @param startIdx
     * @param endIdx
     * @return
     */
    private static int getBaseIdxForDoubleLoop(int[] arr, int startIdx, int endIdx) {
        int base = arr[startIdx];
        int leftIdx = startIdx;
        int rightIdx = endIdx;
        //指针重合停止
        while (leftIdx != rightIdx) {
            //如果右边指针指向到值大于基准值且下标小于左下标，则往左移
            while (arr[rightIdx] > base && rightIdx > leftIdx) {
                rightIdx--;
            }
            //与右指针相反，小于等于基准值则往右移动一次
            while (arr[leftIdx] <= base && leftIdx < rightIdx) {
                leftIdx++;
            }
            //交换左右指针指向动值
            if (rightIdx > leftIdx) {
                int tmp = arr[leftIdx];
                arr[leftIdx] = arr[rightIdx];
                arr[rightIdx] = tmp;
            }
        }
        //与基准值交换
        arr[startIdx] = arr[leftIdx];
        arr[leftIdx] = base;
        return leftIdx;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{8, 23, 22, 1, 9, 0, 26, 98, 100, 3, 6};
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

结果：

[0, 1, 3, 6, 8, 9, 22, 23, 26, 98, 100]

二、单边循环实现：

首先与双边循环法则一样，选择一个基准值，然后一个指针指向起始位置，接下来从基准元素下一个位置开始遍历；
如果遍历元素小于基准元素，则指针右移一位，指针所在位置元素与最新遍历元素交换位置；

/**
     * 单边循环获取基准值
     * @param arr
     * @param startIdx
     * @param endIdx
     * @return
     */
    public static int getBaseIdxForSingleLoop(int[] arr, int startIdx, int endIdx) {
        int base = arr[startIdx];
        int mark = startIdx;
        for (int i = startIdx + 1; i <= endIdx && mark < endIdx; i++) {
            if (arr[i] < base) {
                mark++;
                int tmp = arr[i];
                arr[i] = arr[mark];
                arr[mark] = tmp;
            }
        }
        arr[startIdx] = arr[mark];
        arr[mark] = base;
        return mark;
    }

单边与双边循环主要区别在于获取循环获取基准值；

关于源码，已上传到github（https://github.com/DexterMao/DataStructureDemo）；