FastCollinearPoints的实现中，个人认为最关键的一步是使用Merge Sort对以每个点为出发点的线段进行排序而不能用QuickSort，其原因在与排序的Stability稳定性。MergeSort不会打乱之前因为对Points排序后形成的有序线段组，才能保证后面循环检查线段斜率操作的有效性。

关于排序算法Stability的说明，见《算法（第四版）》第217页的2.5.1.8稳定性一节的讲述

Points.java

/******************************************************************************
 *  Compilation:  javac Point.java
 *  Execution:    java Point
 *  Dependencies: none
 *
 *  An immutable data type for points in the plane.
 *  For use on Coursera, Algorithms Part I programming assignment.
 *
 ******************************************************************************/

import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;

import java.util.Comparator;

public class Point implements Comparable<Point> {

    private final int x;     // x-coordinate of this point
    private final int y;     // y-coordinate of this point

    /**
     * Initializes a new point.
     *
     * @param x the <em>x</em>-coordinate of the point
     * @param y the <em>y</em>-coordinate of the point
     */
    public Point(int x, int y) {
        /* DO NOT MODIFY */
        this.x = x;
        this.y = y;
    }

    /**
     * Draws this point to standard draw.
     */
    public void draw() {
        /* DO NOT MODIFY */
        StdDraw.point(x, y);
    }

    /**
     * Draws the line segment between this point and the specified point
     * to standard draw.
     *
     * @param that the other point
     */
    public void drawTo(Point that) {
        /* DO NOT MODIFY */
        StdDraw.line(this.x, this.y, that.x, that.y);
    }

    /**
     * Returns the slope between this point and the specified point.
     * Formally, if the two points are (x0, y0) and (x1, y1), then the slope
     * is (y1 - y0) / (x1 - x0). For completeness, the slope is defined to be
     * +0.0 if the line segment connecting the two points is horizontal;
     * Double.POSITIVE_INFINITY if the line segment is vertical;
     * and Double.NEGATIVE_INFINITY if (x0, y0) and (x1, y1) are equal.
     *
     * @param that the other point
     * @return the slope between this point and the specified point
     */
    public double slopeTo(Point that) {
        if (this.equal(that))
            return Double.NEGATIVE_INFINITY;
        if (this.x == that.x)
            return Double.POSITIVE_INFINITY;
        if (this.y == that.y)
            return +0.0;
        return (double) (that.y - this.y) / (that.x - this.x);
    }

    /**
     * Compares two points by y-coordinate, breaking ties by x-coordinate.
     * Formally, the invoking point (x0, y0) is less than the argument point
     * (x1, y1) if and only if either y0 < y1 or if y0 = y1 and x0 < x1.
     *
     * @param that the other point
     * @return the value <tt>0</tt> if this point is equal to the argument
     * point (x0 = x1 and y0 = y1);
     * a negative integer if this point is less than the argument
     * point; and a positive integer if this point is greater than the
     * argument point
     */
    public int compareTo(Point that) {
        /* YOUR CODE HERE */
        int result = 1;
        if ((this.y < that.y) || ((this.y == that.y) && (this.x < that.x)))
            result = -1;
        if (this.equal(that))
            result = 0;
        return result;
    }

    /**
     * Compares two points by the slope they make with this point.
     * The slope is defined as in the slopeTo() method.
     *
     * @return the Comparator that defines this ordering on points
     */
    public Comparator<Point> slopeOrder() {
        /* YOUR CODE HERE */
        return new slopeComparator();
    }

    private class slopeComparator implements Comparator<Point> {
        public int compare(Point p, Point q) {
            return Double.compare(slopeTo(p), slopeTo(q));
        }
    }

    private boolean equal(Point that) {
        return (this.x == that.x) && (this.y == that.y);
    }


    /**
     * Returns a string representation of this point.
     * This method is provide for debugging;
     * your program should not rely on the format of the string representation.
     *
     * @return a string representation of this point
     */
    public String toString() {
        /* DO NOT MODIFY */
        return "(" + x + ", " + y + ")";
    }

    /**
     * Unit tests the Point data type.
     */
    public static void main(String[] args) {
        /* YOUR CODE HERE */
        Point p = new Point(1, 1);
        Point p2 = new Point(2, 2);
        Point p3 = new Point(2, 3);

        StdOut.println(p.slopeTo(p2));
        StdOut.println(p.slopeTo(p3));


    }
}

BruteCollinearPoints.java

import java.util.ArrayList;
import java.util.Arrays;

public class BruteCollinearPoints {
    private final ArrayList<LineSegment> lineSegments;
    private int count_line;

    public BruteCollinearPoints(Point[] pointsIn) {
        //three exceptions
        if (pointsIn == null)
            throw new IllegalArgumentException();
        int n = pointsIn.length;
        for (Point point : pointsIn)
            if (point == null)
                throw new IllegalArgumentException();
        Point[] points = new Point[n];
        //copy points in pointsIn into private array points
        System.arraycopy(pointsIn, 0, points, 0, n);
        Arrays.sort(points);
        for (int i = 1; i < n; i++)
            if (points[i - 1].compareTo(points[i]) == 0)
                throw new IllegalArgumentException();
        lineSegments = new ArrayList<LineSegment>();

        for (int a = 0; a < n - 3; a++) {
            for (int b = a + 1; b < n - 2; b++) {
                double Kab = points[a].slopeTo(points[b]);
                for (int c = b + 1; c < n - 1; c++) {
                    double Kac = points[a].slopeTo(points[c]);
                    if (Kac != Kab) continue;
                    assert Kac == Kab;
                    for (int d = c + 1; d < n; d++) {
                        double Kad = points[a].slopeTo(points[d]);
                        if (Kad != Kab) continue;
                        assert Kad == Kab && Kac == Kab;
                        LineSegment addLine = new LineSegment(points[a], points[d]);
                        lineSegments.add(addLine);
                    }
                }
            }
        }

        count_line = lineSegments.size();

    }

    // the number of line segments
    public int numberOfSegments() {
        return count_line;
    }

    // the line segments
    public LineSegment[] segments() {
        LineSegment[] segments = new LineSegment[count_line];
        int i = 0;
        for (LineSegment Line : lineSegments) {
            segments[i++] = Line;
        }
        return segments;
    }


    //main
    public static void main(String[] args) {

    }

}

FastCollinearPoints.java

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Merge;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;

import java.util.ArrayList;
import java.util.Arrays;

public class FastCollinearPoints {
    private ArrayList<LineSegment> lineSegments;
    private ArrayList<line> linesArraylist;
    private int count_line;

    public FastCollinearPoints(Point[] pointsIn) {
        linesArraylist = new ArrayList<line>();
        //three exceptions
        if (pointsIn == null)
            throw new IllegalArgumentException();
        int n = pointsIn.length;
        for (Point point : pointsIn)
            if (point == null)
                throw new IllegalArgumentException();
        Point[] points = new Point[n];

        //copy points in pointsIn into private array points
        System.arraycopy(pointsIn, 0, points, 0, n);
        Arrays.sort(points);
        for (int i = 1; i < n; i++) {
            if (points[i - 1].compareTo(points[i]) == 0) {
                throw new IllegalArgumentException();
            }
        }

        for (int i = 0; i < n - 1; i++) {
            line[] lines = new line[n - 1 - i];
            int sz = 0;
            for (int j = i + 1; j < n; j++) {
                line tempLine = new line(points[i], points[j]);
                lines[sz++] = tempLine;
            }

            if (lines.length < 3)
                continue;
            Merge.sort(lines);
//            StdOut.println("以点" + points[i] + "为起点的线总共有" + lines.length + "条");
//            for (line temp : lines) {
//                StdOut.println(temp + "，其斜率为：" + temp.slope);
//            }
//
//            StdOut.println();
//            StdOut.println();


            int pa = 0, pb = 1;
            while (pa < sz && pb < sz) {
                if (lines[pa].slope == lines[pb].slope) {
                    pb++;
                    if (pb == sz && pb - pa >= 3) {
                        line temp_Line = new line(lines[pa].startPoint, lines[pb - 1].endPoint);
                        if (!isExisted(lines[pb - 1].endPoint, temp_Line.slope)) {
                            linesArraylist.add(temp_Line);
                            //StdOut.println("添加了线段" + temp_Line);
                        }
                    }

                    continue;
                }
                if ((pb - pa) < 3) {
                    pa = pb;
                    pb++;
                } else {
                    line temp_Line = new line(lines[pa].startPoint, lines[pb - 1].endPoint);
                    if (!isExisted(lines[pb - 1].endPoint, temp_Line.slope)) {
                        linesArraylist.add(temp_Line);
                        //StdOut.println("添加了线段" + temp_Line);
                    }

                    pa = pb;
                    pb++;
                }
            }

//
//            StdOut.println();
//            StdOut.println();
//            StdOut.println();

        }

        lineSegments = new ArrayList<LineSegment>();
        for (line l : linesArraylist) {
            LineSegment lineSegment = new LineSegment(l.startPoint, l.endPoint);
            lineSegments.add(lineSegment);

        }

        count_line = lineSegments.size();
//               int lineNum = (N * (N - 1)) / 2;
//        int index = 0;
//        //把所有的两点线段全都加到lines中，lines用于存储所有的线段
//        for (int i = 0; i < N - 1; i++) {
//            for (int j = i + 1; j < N; j++) {
//                line tempLine = new line(points[i], points[j]);
//                lines[index++] = tempLine;
//            }
//        }
//        assert index == lineNum - 1;

//        //将所有线段按照斜率进行快排(不需要考虑稳定性)
//        assert lines != null;
//        Quick.sort(lines);
//        //将所有线段按照名称进行归并排序
    }

    private boolean isExisted(Point end, double slope) {
        boolean result = false;
        for (line l : linesArraylist) {
            if ((end.compareTo(l.endPoint) == 0) && (Double.compare(slope, l.slope) == 0)) {
                result = true;
                break;
            }
        }
        return result;
    }


    //由两个点组成的线段，提供按照斜率和按照起始点两种排序方式
    private static class line implements Comparable<line> {

        public final Point startPoint;
        public final Point endPoint;
        public double slope;

        public line(Point s, Point e) {
            startPoint = s;
            endPoint = e;
            slope = s.slopeTo(e);
        }

        @Override
        public int compareTo(line o) {
            return Double.compare(this.slope, o.slope);
        }

        @Override
        public String toString() {
            return startPoint + " -> " + endPoint;
        }
    }


    public int numberOfSegments() {
        return count_line;
    }

    public LineSegment[] segments() {
        LineSegment[] segments = new LineSegment[count_line];
        int i = 0;
        for (LineSegment Line : lineSegments) {
            segments[i++] = Line;
        }
        return segments;
    }

    //main
    public static void main(String[] args) {
        In in = new In("src/input8.txt");
        int n = in.readInt();
        StdOut.println("total " + n + " points");
        Point[] points = new Point[n];
        for (int i = 0; i < n; i++) {
            int x = in.readInt();
            int y = in.readInt();
            StdOut.println("(" + x + "," + y + ")");
            points[i] = new Point(x, y);
        }
        //draw the points
        StdDraw.enableDoubleBuffering();
        StdDraw.setXscale(0, 32768);
        StdDraw.setYscale(0, 32768);
        StdDraw.setPenColor(StdDraw.RED);
        StdDraw.setPenRadius(0.01);
        for (Point p : points) {
            p.draw();
        }
        StdDraw.show();
        // print and draw the line segments
        FastCollinearPoints collinear = new FastCollinearPoints(points);
        StdOut.println(collinear.numberOfSegments());
        for (LineSegment segment : collinear.segments()) {
            StdOut.println(segment);
            segment.draw();
        }
        StdDraw.show();

//        Point test1 = new Point(1000, 21);
//        Point test2 = new Point(1000, 2000);
//        Point test3 = new Point(1000, 3000);
//        StdOut.println(test1.slopeTo(test2) == test1.slopeTo(test3));
        //上面几行的输出是true
    }
}