啊哈算法读书笔记

Finlabtech

这部书作者是想用诙谐通俗的语言讲解算法，前半段可以说理解得特别流畅，确实看起来很轻松，但到了后半段，对于比较复杂的算法讲解能感觉到很吃力。这里我主要提一下我觉得以通俗的语言讲解得非常到位的快排[1]。
总结一下快排：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
当然，描述起来很简单但是实现的话还是有一些需要注意的地方的。

import java.util.stream.Collectors;
import java.util.stream.Stream;
/**
 * @author: tianxie
 * @Description: 快排,基于《啊哈算法》
 * 输入:6  1  2  7  9  3  4  5  10  8
 * 则递归过程为:
 * 6  1  2  5  9  3  4  7  10  8
 * 6  1  2  5  4  3  9  7  10  8
 * 3  1  2  5  4  6  9  7  10  8
 * 2  1  3  5  4  6  9  7  10  8
 * 1  2  3  5  4  6  9  7  10  8
 * 1  2  3  4  5  6  9  7  10  8
 * 1  2  3  4  5  6  9  7  8  10
 * 1  2  3  4  5  6  8  7  9  10
 * 1  2  3  4  5  6  7  8  9  10
 * @Date: 2018/3/28下午2:19
 */
public class QuickSort {
    public static void main(String[] args) {
        Integer[] source = new Integer[]{91, 23, 12, 34, 7, 10, 23, 14, 64};
        String begin = Stream.of(source).map(Object::toString).collect(Collectors.joining(", "));
        quickSort(0, source.length-1, source);
        String end = Stream.of(source).map(Object::toString).collect(Collectors.joining(", "));
        System.out.println("排序前序列为: " + begin);
        System.out.println("排序后序列为: " + end);
    }
    private static void quickSort(int start, int end, Integer[] source) {
        //递归退出条件
        if(start >= end) {
            return;
        }
        //基准值默认取第一个
        int base = source[start];
        //分别从首尾开始迭代&交换
        int i = start;
        int j = end;
        while(i!=j) {
            while(i<j && source[j]>=base) {
                j--;
            }
            while(i<j && source[i]<=base) {
                i++;
            }
            if(i<j) {
                int temp = source[i];
                source[i] = source[j];
                source[j] = temp;
            }
        }
        //迭代完毕后更新基准值与i&j相会的index值
        source[start] = source[i];
        source[i] = base;
        //本次按照跟基准值的大小分割完毕,开始递归左右两个子序列
        quickSort(start, i-1, source);
        quickSort(j+1, source.length-1, source);
    }
}

多提一句，从Java7开始，集合默认的排序底层实现由普通的快排变成了双中心快排，见：java.util.DualPivotQuicksort。