快速排序法

package com.company;

public class QuickSort {
    /**
     * 这是快速排序的非递归算法
     * 是用栈来实现的
     * 用栈来存储分组下标解决此问题
     * @param sourceArray
     */
    static public void quickSort0(int[] sourceArray) {
        int arrayLength = sourceArray.length;
        //创建一个栈用来存储下标
        //其实不用着整个数组那么长的
        int[] indexStack = new int[arrayLength];
        //栈顶指针
        int indexStackTop = -1;
        //因为整个数组是一个分组
        //所以先把整个数组的首尾下标存入栈中
        indexStack[++indexStackTop] = 0;
        indexStack[++indexStackTop] = arrayLength - 1;
        //只要栈顶没有到栈底
        //或者说
        //栈中有元素存在就说明排序没完成
        //用于记录趟数
        int counter = 0;
        while (indexStackTop > -1) {
            int endIndex = indexStack[indexStackTop--];
            int headIndex = indexStack[indexStackTop--];
            if (endIndex > headIndex) {
                //每个分组里面最起码也得有2个元素
                //1个元素那必然是有序的
                //参照元素
                //还是取每个分组最左边那个
                int referenceElement = sourceArray[headIndex];
                int headPointer = headIndex;
                int endPointer = endIndex;
                while (headPointer < endPointer) {
                    //从后往前找比参考元素小的元素
                    while (sourceArray[endPointer] > referenceElement && headPointer < endPointer)
                        endPointer--;
                    //从前往后找比参考元素大的元素
                    //这个地方一定要带等号，否则会
                    // 发生参照元素不正确替换的问题。
                    while (sourceArray[headPointer] <= referenceElement && headPointer < endPointer)
                        headPointer++;
                    //找到了
                    //这个时候也得判断一下
                    if (headPointer < endPointer) {
                        int tempElement = sourceArray[endPointer];
                        sourceArray[endPointer] = sourceArray[headPointer];
                        sourceArray[headPointer] = tempElement;
                    }
                }
                //这个时候参考元素的最终位置就已经找到了
                //即headPointer == endPointer，但是
                // 这个地方的值不一定比参照值小，比如说
                // 参照值比它后面所有的值都小的话。所以
                // 这里还要判断一下
                sourceArray[headIndex] = sourceArray[headPointer];
                sourceArray[headPointer] = referenceElement;
                for (int element:sourceArray) {
                    System.out.print(element + " ");
                }
                System.out.println("--第" + ++counter + "趟完成");
                //然后向栈里面塞入新分组的首尾下标
                //前一个分组
                if (headIndex < headPointer - 1) {
                    indexStack[++indexStackTop] = headIndex;
                    indexStack[++indexStackTop] = headPointer - 1;
                }
                //后一个分组
                if (headPointer + 1 < endIndex) {
                    indexStack[++indexStackTop] = headPointer + 1;
                    indexStack[++indexStackTop] = endIndex;
                }
            }
        }
    }

    /**
     * 下面实现的是快速排序的递归算法
     * 短小精悍，但是它能够清晰地体现
     * 出快速排序法的思想。
     * @param sourceArray
     */
    static public void quickSort1(int[] sourceArray) {
        int arrayLength = sourceArray.length;
        QuickSort.divideGroup(sourceArray,0,arrayLength - 1);
    }

    /**
     * 这就是递归体了
     * @param sourceArray
     * @param headIndex
     * @param endIndex
     */
    static private void divideGroup(int[] sourceArray,int headIndex,int endIndex) {
        //需要排序的序列至少得有俩，
        // 否则没有意义。
        if (endIndex > headIndex) {
            int referenceElement = sourceArray[headIndex];
            int headPointer = headIndex;
            int endPointer = endIndex;
            while (headPointer < endPointer) {
                while (sourceArray[endPointer] > referenceElement && headPointer < endPointer)
                    endPointer--;
                while (sourceArray[headPointer] <= referenceElement && headPointer < endPointer)
                    headPointer++;
                if (headPointer < endPointer) {
                    int tempElement = sourceArray[endPointer];
                    sourceArray[endPointer] = sourceArray[headPointer];
                    sourceArray[headPointer] = tempElement;
                }
            }
            sourceArray[headIndex] = sourceArray[headPointer];
            sourceArray[headPointer] = referenceElement;
            QuickSort.divideGroup(sourceArray,headIndex,headPointer - 1);
            QuickSort.divideGroup(sourceArray,headPointer + 1,endIndex);
        }
    }
}