算法

快速排序

Posted by Pismery Liu on Tuesday, October 30, 2018

TOC

快速排序

介绍

  快速排序思想解决O(n)时间内求第N大数字 。

递归快速排序 版本一

思想

  1. 每次递归将基准移动到适合的位置，使得左边的均小于基准，右边的均大于基准。ps:基准默认选择第一个。
  2. 从左往右找到大于基准的索引(left)，从右往左找小于基准的索引(right)
  3. 交换索引(left)与索引(right)位置
  4. 直到left < right
  5. 将基准与所找到的中间大小位置交换

代码

public static void quickSortRecursion(int[] source, int beginIndex, int endIndex) {
    if (beginIndex > endIndex) {
        return;
    }

    int standard = source[beginIndex];
    int left = beginIndex;
    int right = endIndex;

    while (left < right) {
        while (source[right] > standard && left < right) { //从右往左找比基准小的索引
            right--;
        }
        while (source[left] <= standard && left < right) { //从左往右找比基准大的索引 必须<= 否则第一个就一直不动
            left++;
        }
        exchage(source, left, right);
    }
    //将基准与最终位置交换；使得左边均小于基准，右边均大于基准
    source[beginIndex] = source[left];
    source[left] = standard;

    quickSortRecursion(source, beginIndex, left - 1);
    quickSortRecursion(source, left + 1, endIndex);
}

非递归快速排序 版本一

思想

  1. 将递归通过java栈的特点来实践，当栈空则排序结束。
  2. 其余与版本一递归快速排序一致

代码

public static void quickSortNoRecursion(int[] source) {
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    stack.push(source.length - 1);

    int left;
    int right;
    int benchmark; //基准
    int beginIndex;
    int endIndex;
    while (!stack.isEmpty()) {
        right = stack.pop();
        left = stack.pop();
        if (right == left)
            continue;
        benchmark = source[left];
        beginIndex = left;
        endIndex = right;
        while (left < right) {
            //寻找需要交换的地址
            while (benchmark < source[right] && left < right) {
                right--;
            }
            while (benchmark >= source[left] && left < right) {
                left++;
            }
            if (right == left)
                continue;
            exchage(source, left, right);
        }
        source[beginIndex] = source[left];
        source[left] = benchmark;
        //压栈
        if (endIndex > left) {
            stack.push(left + 1);
            stack.push(endIndex);
        }
        if (beginIndex < left) {
            stack.push(beginIndex);
            stack.push(left - 1);
        }
    }

}

递归快速排序 版本二

思想

  1. 基准在左边，从右边开始扫描到小于基准值(right–)，交换位置。基准变成右边；
  2. 基准在右边，从左边开始扫描到大于基准值(left++)，交换位置。基准变成左边；
  3. 直到(left < right)

代码

public static void quickSortRecursionVersion2(int[] source, int left, int right) {
    if (left >= right) {
        return;
    }

    int benchmark = source[left];
    int begin = left;
    int end = right;

    boolean flag = true; //true:benchmark is left;false:benchmark is right
    while (left < right) {
        if (flag) {//基准在左边
            if (source[left] < source[right]) {
                //如果基准在左边，右边哨兵大于基准，右哨兵左移;
                right--;
                continue;
            }
            exchage(source, left, right);
            left++;
            flag = false; //交换后基准在右边
        } else { //基准在右边
            if (source[left] < source[right]) {
                //如果基准在右边，左边哨兵小于基准，左哨兵右移;
                left++;
                continue;
            }
            exchage(source, left, right);
            right--;
            flag = true; //交换后基准在左边
        }
    }
    quickSortRecursionVersion2(source, begin, left - 1);
    quickSortRecursionVersion2(source, left + 1, end);

}

非递归快速排序 版本二

思想

  1. 将递归通过java栈的特点来实践，当栈空则排序结束。
  2. 其余与版本二递归快速排序一致

代码

public static void quickSortNoRecursionVersion2(int[] source) {
    Stack<Integer> stack = new Stack();
    stack.push(0);
    stack.push(source.length - 1);

    int left;
    int right;
    int beginIndex;
    int endIndex;
    boolean flag = true;

    while (!stack.empty()) {
        right = stack.pop();
        left = stack.pop();

        if (left >= right)
            continue;

        beginIndex = left;
        endIndex = right;

        while (left < right) {
            if (flag) { //基准在左边
                if (source[left] < source[right]) {//右边哨兵大于基准，右哨兵左移;
                    right--;
                    continue;
                }
                exchage(source, left, right);
                left++;
                flag = false;
            } else { //基准在右边
                if (source[left] < source[right]) {//左边哨兵小于基准，左哨兵右移;
                    left++;
                    continue;
                }
                exchage(source, left, right);
                right--;
                flag = true;
            }
        }

        stack.push(left + 1);
        stack.push(endIndex);
        stack.push(beginIndex);
        stack.push(left - 1);
    }
}

三路快速排序

思想

  1. 将数组分为三段：小于基准；等于基准；大于基准
  2. 每次在小于基准和大于基准中循环

代码

public static void quickSortThreeWay(int[] source, int beginIndex, int endIndex) {
    if (beginIndex >= endIndex) {
        return;
    }

    int ltIndex = beginIndex;//小于基准的最右指针;初始化保证为空
    int gtIndex = endIndex + 1;//大于基准的最左指针;初始化保证为空
    int benchmark = source[beginIndex];
    int currentIndex = beginIndex + 1;

    while (currentIndex < gtIndex) { //注意不可相等。因为gtIndex会一直小于enIndex 无法退出递归
        if (source[currentIndex] < benchmark) {
            // ltIndex 先++ 后交换。 交换后currntIndex++;
            exchage(source, ++ltIndex, currentIndex++);
        } else if (source[currentIndex] > benchmark) {
            // gtIndex 先-- 后交换。 交换后currntIndex不用++;
            // 因为后面的元素还是未检查的元素;
            exchage(source, currentIndex, --gtIndex);
        } else {
            currentIndex++;
        }
    }
    exchage(source, beginIndex, ltIndex--);
    quickSortThreeWay(source, beginIndex, ltIndex);
    quickSortThreeWay(source, gtIndex, endIndex);

}

注意： currentIndex < gtIndex 不能是currentIndex <= gtIndex。 例如.调用quickSortThreeWay(source, 4, 5);soure[10,11,12,13,14,15] benginIndex = 4,endIndex = 5,gtIndex = 6,benchmark = 14; 第一轮 source[currentIndex] = 15 > 14执行exchage(source, currentIndex, –gtIndex); 此时currentIndex == gtIndex == 5；再次执行了exchage(source, currentIndex, –gtIndex); 此时gtIndex = 4;再次递归调用了quickSortThreeWay(source, 4, 5); 最终栈溢出；

测试

@Slf4j
public class QuickSortTest {
    @Test
    public void quickSortThreeWay() {
        int[] actual = RandomUtils.randomArrayNoRepeat(1, 10, 5);
        log.info("Array: " + Arrays.toString(actual));
        int[] expect = Arrays.copyOf(actual, actual.length);
        Arrays.sort(expect);

        QuickSort.quickSortThreeWay(actual, 0, actual.length - 1);
        assertArrayEquals(expect, actual);
    }

    @Test
    public void quickSortRecursion() {
        int[] actual = RandomUtils.randomArrayNoRepeat(1, 2000, 100);
        log.info("Array: " + Arrays.toString(actual));
        int[] expect = Arrays.copyOf(actual, actual.length);
        Arrays.sort(expect);

        QuickSort.quickSortRecursion(actual, 0, actual.length - 1);

        assertArrayEquals(expect, actual);
    }
    @Test
    public void quickSortRecursionVersion2() {
        int[] actual = RandomUtils.randomArrayNoRepeat(1, 10, 5);
        log.info("Array: " + Arrays.toString(actual));
        int[] expect = Arrays.copyOf(actual, actual.length);
        Arrays.sort(expect);

        QuickSort.quickSortRecursionVersion2(actual, 0, actual.length - 1);

        assertArrayEquals(expect, actual);
    }

    @Test
    public void quickSortNoRecursion() {
        int[] actual = RandomUtils.randomArrayNoRepeat(1, 2000, 100);
        log.info("Array: " + Arrays.toString(actual));
        int[] expect = Arrays.copyOf(actual, actual.length);
        Arrays.sort(expect);

        QuickSort.quickSortNoRecursion(actual);

        assertArrayEquals(expect, actual);
    }
    @Test
    public void quickSortNoRecursionVersion2() {
        int[] actual = RandomUtils.randomArrayNoRepeat(1, 2000, 1000);
        log.info("Array: " + Arrays.toString(actual));
        int[] expect = Arrays.copyOf(actual, actual.length);
        Arrays.sort(expect);

        QuickSort.quickSortNoRecursionVersion2(actual);

        assertArrayEquals(expect, actual);
    }
}
FEATURED TAGS
JVM Java MySQL NIO Netty Python Redis Spring Transaction basic concurrent database log 工具类 数据结构 极客时间笔记 测试 算法 设计思想 设计模式