快排

Github
单边循环法

public class 快排 {
    public static void main(String[] args) {

        int[] arrays = {8, 0, 9, 10, 8, 4, 11, 34, 1};
        sort(arrays, 0, arrays.length - 1);
        System.out.println(Arrays.toString(arrays));
    }

    public static void sort(int[] arrays, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        //基准数指针位置
        int prvotIndex = partition(arrays, startIndex, endIndex);

        //除基准数外  左右两边再次进行 交换排序
        sort(arrays, startIndex, prvotIndex - 1);

        sort(arrays, prvotIndex + 1, endIndex);
    }

    public static int partition(int[] arrays, int startIndex, int endIndex) {
        //基准数
        int pivot = arrays[startIndex];
        //基准数指针位置
        int mark = startIndex;
        //先不交换基准数位置 ，只记录基准数指针位置  结束循环后再交换
        for (int i = startIndex + 1; i <= endIndex; i++) {

            //如果下一个数小于基准数
            if (pivot > arrays[i]) {
                //指针右移并交换数据
                mark++;
                System.out.println("交换前" + Arrays.toString(arrays));
                //如果 两数不相等 在进行交换
                if (arrays[mark] != arrays[i]) {
                    int temp = arrays[mark];
                    arrays[mark] = arrays[i];
                    arrays[i] = temp;
                    System.out.println("交换后" + Arrays.toString(arrays));
                }

            }
        }
        //基准数交换到基准数指针位置
        arrays[startIndex] = arrays[mark];
        arrays[mark] = pivot;
        System.out.println();
        System.out.println("交换基准数" + Arrays.toString(arrays));
        System.out.println();
        return mark;

    }
}

双边循环

    /**
     * 双边循环
     *
     * @param array
     * @param startIndex
     * @param endIndex
     */
    public static void DoubleSort(int[] array, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }

        //找到基准数位置
        int pivotIndex = DoublePartition(array, startIndex, endIndex);
        //除基准数外  左右两边再次进行 交换排序
        DoubleSort(array, startIndex, pivotIndex - 1);
        DoubleSort(array, pivotIndex + 1, endIndex);

    }

    public static int DoublePartition(int[] array, int startIndex, int endIndex) {
        //基准元素位置
        int pivot = array[startIndex];
        //左边指针位置
        int leftIndex = startIndex;
        //右边指针位置
        int rightIndex = endIndex;
        //两边指针重合结束循环
        while (leftIndex != rightIndex) {
            //若果左边比右边小   并且  右指针数大于基准数 右指针左移一位继续比较左边数  否则停止
            while (leftIndex < rightIndex && array[rightIndex] > pivot) {
                rightIndex--;

            }
            //同上 只不过是左指针右移
            while (leftIndex < rightIndex && array[leftIndex] <= pivot) {
                leftIndex++;
            }
            //如果左比有小 交换俩指针数位置
            if (leftIndex < rightIndex) {
                int p = array[leftIndex];
                array[leftIndex] = array[rightIndex];
                array[rightIndex] = p;
//                System.out.println("array = [" + Arrays.toString(array) + "], startIndex = [" + leftIndex + "], endIndex = [" + rightIndex + "]");
            }
        }
        //指针重合  和起始位置基准数交换重合位置
        array[startIndex] = array[leftIndex];
        array[leftIndex] = pivot;
        return leftIndex;
        
    }