Week1 作业总结
代码实现
import edu.princeton.cs.algs4.WeightedQuickUnionUF;public class Percolation {private final WeightedQuickUnionUF uf;private int[][] grid; // 网格，若为OPEN则为其在网格中的位置编号，若为CLOSE则为0，初始化为0private int openedNum = 0;// 已经open的site数目private final int top, bottom; // 虚节点 扣分点：没加final修饰符：it is initialized only in the declaration or constructor.private final int n; // size of grid// creates n-by-n grid, with all sites initially blockedpublic Percolation(int n){if (n <= 0){throw new IllegalArgumentException("grid size should be greater than one !");}this.top = 0; // 初始化top虚节点的编号this.bottom = n * n + 1; // 初始化bottom虚节点的编号，其他正常节点1 ~ n * nthis.n = n;grid = new int[n][n];uf = new WeightedQuickUnionUF(n * n + 2); // 多了top, bottom虚节点，分别和第一层和最后一层的每一个OPEN节点相连// 初始化grid，均为BLOCKfor (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {grid[i][j] = 0;}}}// check the validation of inputsprivate void validate(int row, int col) {if (row < 1 || col < 1 || row > this.n || col > this.n) {throw new IllegalArgumentException("invalid input!");}}// opens the site (row, col) if it is not open alreadypublic void open(int row, int col) {validate(row, col);// 已经OPENif (grid[row-1][col-1] != 0) {return;}// OPEN了，设置为其在网格中的位置编号grid[row-1][col-1] = (row - 1) * n + col;openedNum++;// 以下更新连通情况// 第一层的OPEN节点和top虚节点连通if (row == 1 && grid[row-1][col-1] != 0) {uf.union(top, grid[row-1][col-1]);}// 最后一层的OPEN节点和bottom虚节点连通if (row == n && grid[row-1][col-1] != 0) {uf.union(bottom, grid[row-1][col-1]);}// 一个节点的四面八方（注意在边界上的节点不要越界查询）// row-1-1分开写是区分第一个减是坐标对应，第二个则是表示它在上一行，后续-2，-1+1同理。if (row > 1 && grid[row - 1 - 1][col-1] != 0) {uf.union(grid[row - 2][col - 1], grid[row - 1][col - 1]);}if (col > 1 && grid[row-1][col-2] != 0) {uf.union(grid[row-1][col-2], grid[row-1][col-1]);}if (row < n && grid[row-1+1][col-1] != 0) {uf.union(grid[row][col-1], grid[row-1][col-1]);}if (col < n && grid[row-1][col] != 0) {uf.union(grid[row-1][col], grid[row-1][col-1]);}}// is the site (row, col) open?public boolean isOpen(int row, int col){validate(row, col);return grid[row-1][col-1] != 0;}// is the site (row, col) full? （full理解为是否能被水填满，也就是和top虚节点是不是连通）public boolean isFull(int row, int col){validate(row, col);return uf.find(top) == uf.find(grid[row-1][col-1]) && isOpen(row, col); // 扣分点：没加&&isOpen}// returns the number of open sitespublic int numberOfOpenSites(){return openedNum;}// does the system percolate?public boolean percolates(){return uf.find(top) == uf.find(bottom);}public static void main(String[] args) {Percolation p = new Percolation(3);// for(int i=0;i<10;i++){// p.open(StdRandom.uniform(1, 6), StdRandom.uniform(1, 6));// }p.open(1, 2);p.open(2, 1);p.open(3, 2);p.open(3, 3);if (p.isOpen(3, 3)) System.out.println(p.isFull(3, 3));if (p.percolates()) System.out.println("percolates");else System.out.println("does not percolate");System.out.println(p.numberOfOpenSites());}}
import edu.princeton.cs.algs4.StdRandom;import edu.princeton.cs.algs4.StdStats;public class PercolationStats {private final int trials; // 尝试次数private final double[] openProportions; // 扣分点：要加final，引用类型的final可以改里面的值，只是不能改指向的对象// private Percolation p; // 扣分点：改成local，只有一个方法用到private double meanOfOpenProp;private double stddevOfOpenProp;// perform independent trials on an n-by-n gridpublic PercolationStats(int n, int trials){if (n <= 0 || trials <= 0) throw new IllegalArgumentException("invalid input!");this.trials = trials;openProportions = new double[trials];for (int i = 0; i < trials; ++i) {Percolation p = new Percolation(n);while (!p.percolates()) {p.open(StdRandom.uniform(1, n+1), StdRandom.uniform(1, n+1));}openProportions[i] = 1.0 * p.numberOfOpenSites() / (n * n);// 扣分点：要在构造函数中计算meanOfOpenProp = StdStats.mean(openProportions);stddevOfOpenProp = StdStats.stddev(openProportions);}}// sample mean of percolation thresholdpublic double mean(){return meanOfOpenProp;}// sample standard deviation of percolation thresholdpublic double stddev(){return stddevOfOpenProp;}// low endpoint of 95% confidence intervalpublic double confidenceLo(){return meanOfOpenProp - 1.96 * stddevOfOpenProp / Math.sqrt(trials);}// high endpoint of 95% confidence intervalpublic double confidenceHi(){return meanOfOpenProp + 1.96 * stddevOfOpenProp / Math.sqrt(trials);}public static void main(String[] args) {PercolationStats per = new PercolationStats(Integer.parseInt(args[0]),Integer.parseInt(args[1]));// PercolationStats per = new PercolationStats(5, 100);System.out.printf("%-23s"+" = "+per.mean()+"\n","mean");System.out.printf("%-23s"+" = "+per.stddev()+"\n","stddev");System.out.printf("%-23s"+" = ["+per.confidenceLo()+","+per.confidenceHi()+"]","95% confidence interval");}}
小结
真是痛苦，磕磕绊绊写完代码，发现还有一堆小问题和bug，小问题包括
- 变量定义的位置（全局还是局部？），还有未添加final修饰符（对于基本数据类型，只要是在构造函数中初始化后就不会修改的全部要加final修饰，对于引用数据类型，如grid，不改变指向的对象的情况下也要加final），
- 还有一些格式问题，例如if, while加括号前要加空格，右括号加大括号前要加空格。
- 还有一个问题是PercolationStats中要求mean和std要在构造函数中就被计算出来，确保每次调用方法取这两个值的时候总是一致的，而且如果多次调用也会提高效率。
- 还有connected这个方法已经被指定为deprecated，调用会扣分，在源码注释中让我用find相等代替，我不知道这么做的目的是什么，可能只是让我们以后注意避免使用deprecated的方法吧
bug是在isFull()的实现中，以为这个节点和top虚节点是通（uf.find(top) == uf.find(grid[row-1][col-1])）的就说明是isFull，但是还需要判断这个节点本身是不是isOpen，因为我定义CLOSE的节点的值为0，其根节点为自己也为0，而虚节点也为0，所以当没有open任何节点的时候，所有的节点都是isFull == true的。
Union-Find 模板
带按秩合并和路径压缩
private class UnionFind { private int[] parent; // parent[i] = parent of i private int count; // number of components private int[] size; // size[i] = number of elements in subtree rooted at i 只保证根节点的size有意义 public int getCount() { return count; } public UnionFind(int n) { this.count = n; this.parent = new int[n]; this.size = new int[n]; for (int i = 0; i < n; ++i) { parent[i] = i; size[i] = 1; } } public int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; // 路径压缩 x = parent[x]; } return x; } // 或者递归写法，将路径上每个节点的父节点都设为根节点 public int find1(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } public void union(int x, int y) { int xRoot = find(x); int yRoot = find(y); if (xRoot == yRoot) return; // make smaller root point to larger one if (size[xRoot] < size[yRoot]) { parent[xRoot] = yRoot; size[yRoot] += size[xRoot]; } else { parent[yRoot] = xRoot; size[xRoot] += size[yRoot]; } count--; } }
Week2 总结
课堂笔记
用数组和链表实现stack都比较容易，唯一需要注意的是数组的扩容和缩容问题。
我们选择每次扩容都扩大一倍，然后将原始数组的内容copy到新数组，再让s = copy即可。如果每次都扩大一个单位，假设初始容量为1，那么当插入N个元素时，元素移动了1+2+…+N ~N^2 次，而每次扩大一倍则变为1+2+4+8+…+N ~ 3N次。
缩容不是简单的和扩容一样，将数组大小减半，因为这样会造成抖动thrashing，例如用户在刚好要扩容的时候疯狂push pop push pop，就会导致不断扩容减容，降低效率。所以我们在栈1/4满的时候，将容量减小一半，变成半满，这个状态下可以继续pop或push而不会导致扩容或缩容，避免抖动。
java官方现在推荐使用Deque(double ended queue双端队列)来同时实现stack和queue，而ArrayDeque和LinkedList都实现了Deque。
Java 栈(Stack)和队列(Queue)的首选 - ArrayDeque
链表or数组？
链表的运行时间更加稳定，但总的来看数组的总运行效率更好。如果追求稳定就用链表，否则数组。
Generics
实现stack和queue时使用泛型Generics，相比于强制类型转换在编译时，而不是运行时，就发现错误。因为Java不支持泛型数组，所以在用数组实现的时候，初始化时还是需要强制类型转换（会收到warning，但是没办法）。
Iterator
将实现的stack和queue类实现Iterable接口，实现其中的Iterator方法返回Iterator对象，Iterator类中有hasNext和next方法，实现了Iterable的类可以用foreach语法。
代码
package week2;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class Deque<Item> implements Iterable<Item> {
private int size;
private Node first;
private Node last;
// 用链表实现双端队列
private class Node {
private Item val;
private Node next;
private Node past;
public Node(Item val) {
this.val = val;
}
}
// construct an empty deque
public Deque() {
this.size = 0;
this.first = null;
this.last = null;
}
// is the deque empty?
public boolean isEmpty(){
return this.size == 0;
}
// return the number of items on the deque
public int size() {
return size;
}
// add the item to the front
public void addFirst(Item item) {
if (item == null) throw new IllegalArgumentException("you must add a valid item!");
Node oldFirst = this.first;
this.first = new Node(item);
this.first.next = oldFirst;
// 如果oldFirst不是null，才能往回指，否则这个新节点是唯一的节点，自然也是last。addLast同理。
if (isEmpty()) this.last = this.first;
else oldFirst.past = this.first;
++this.size;
}
// add the item to the back
public void addLast(Item item) {
if (item == null) throw new IllegalArgumentException("you must add a valid item!");
Node oldLast = this.last;
this.last = new Node(item);
this.last.past = oldLast;
if(isEmpty()) this.first = this.last;
else oldLast.next = this.last;
++this.size;
}
// remove and return the item from the front
public Item removeFirst() {
if (isEmpty()) throw new NoSuchElementException("deque is empty!");
Item item = this.first.val;
this.first = this.first.next;
--this.size;
// 删除了以后，考虑当前deque为空的情况
if (isEmpty()) this.last = null;
else this.first.past = null;
return item;
}
// remove and return the item from the back
public Item removeLast() {
if (isEmpty()) throw new NoSuchElementException("deque is empty!");
Item item = this.last.val;
this.last = this.last.past;
--this.size;
if (isEmpty()) this.first = null;
else this.last.next = null;
return item;
}
// return an iterator over items in order from front to back
// 实现Iterable接口就要实现Iterator()
@Override
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item> {
private Node cur = first;
public boolean hasNext() {
return this.cur != null;
}
public void remove() {
throw new java.lang.UnsupportedOperationException();
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException("next is null");
Item item = cur.val;
cur = cur.next;
return item;
}
}
public static void main(String[] args) {
Deque<String> deque = new Deque<String> ();
while(!StdIn.isEmpty()) {
String s = StdIn.readString();
if(!s.equals("-")) {
StdOut.println("1->deque.size()=" +deque.size());
deque.addFirst(s);
StdOut.println("2->deque.size()=" +deque.size());
}
else if(!deque.isEmpty()) {
StdOut.println(deque.removeFirst() + " ");
StdOut.println("3->deque.size()=" +deque.size());
}
}
StdOut.println("(" + deque.size() +" left on the deque)");
}
}
package week2;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import java.util.Iterator;
import java.util.NoSuchElementException;
// the item removed is chosen uniformly at random among items in the data structure.
public class RandomizedQueue<Item> implements Iterable<Item> {
private Item[] queue;
private int size;
// construct an empty randomized queue
public RandomizedQueue() {
// 不允许直接创建泛型数组，只能强制类型转换
queue = (Item[]) new Object[1];
size = 0;
}
// is the randomized queue empty?
public boolean isEmpty() {
return size == 0;
}
// return the number of items on the randomized queue
public int size() {
return size;
}
// 数组实现queue，需要考虑扩容和缩容
private void resize(int capacity) {
Item[] newQueue = (Item[]) new Object[capacity];
for (int i = 0; i < size; ++i) newQueue[i] = queue[i];
queue = newQueue;
}
// add the item
public void enqueue(Item item) {
if (item == null) throw new IllegalArgumentException();
// 考虑扩容
if (queue.length == size) resize(queue.length * 2);
queue[size++] = item;
}
// remove and return a random item
// 实现思路：随机选一个元素，和最后一个元素交换位置，再将最后一个元素出队，避免整体移动
public Item dequeue() {
if (isEmpty()) throw new NoSuchElementException();
// random()返回[0, 1)的浮点数，随机选取一个目标被尾元素替换
int index = (int) Math.random() * size;
Item item = queue[index];
queue[index] = queue[size-1];
queue[--size] = null;
// 考虑缩容，并且避免抖动（上课讲的缩容方式）
if (size > 0 && size == queue.length / 4) resize(queue.length / 2);
return item;
}
// return a random item (but do not remove it)
public Item sample() {
if (isEmpty()) throw new NoSuchElementException();
int index = (int) Math.random() * size;
Item item = queue[index];
return item;
}
// return an independent iterator over items in random order
public Iterator<Item> iterator() {
return new queueIterator();
}
// 注意：不要在内部类中声明泛型！哪怕名称相同编译器都会理解为不同类型
private class queueIterator implements Iterator<Item> {
// 需要random order返回，考虑到不改变原数组，创个新的，然后shuffle打乱
private Item[] randomQ;
private int index = 0;
public queueIterator() {
randomQ = (Item[]) new Object[size]; // 无法初始化Generics数组，所以用到类型转换
for (int i = 0; i < size; ++i) randomQ[i] = queue[i];
StdRandom.shuffle(randomQ);
}
public boolean hasNext() {
return index < randomQ.length;
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
return randomQ[index++];
}
public void remove() {
throw new UnsupportedOperationException();
}
}
// unit testing (required)
public static void main(String[] args) {
RandomizedQueue<String> deque = new RandomizedQueue<>();
while(!StdIn.isEmpty()) {
String s = StdIn.readString();
if(!s.equals("-")) {
StdOut.println("1->deque.size()=" +deque.size());
deque.enqueue(s);
StdOut.println("2->deque.size()=" +deque.size());
}
else if(!deque.isEmpty()) {
StdOut.println(deque.dequeue() + " ");
StdOut.println("3->deque.size()=" +deque.size());
}
}
StdOut.println("(" + deque.size() +" left on the deque)");
}
}
小结
要实现Deque类和RandomQueue类。要点如下
- 熟悉迭代器的实现。
- 注意内部类不要再声明一样的泛型，否则会被编译器当作不一样的泛型对待。
实现了链表和数组的方式实现队列，其中数组需要考虑扩容和缩容，链表则是要周全考虑last和first指针的更新。
Week3 作业总结
Point实现了两种排序方式，一种是根据在坐标中的位置排序，是通过implement Comparable
实现的，需要实现compareTo()；
另一种是我没见过的，在Point类中实现了一个返回Comparator的方法，比较的是另外两个point与自己的斜率slope，当Point列表sort的时候加入这个Comparator参数就能使用这个排序规则。具体看Point中方法的实现和FastCollinearPoints的51行的调用。注意实现方法的时候让IDEA自动改成了lambda表达式的形式，括号中的两个参数即为Comparator类compare()的参数。Arrays.sort()实现时使用归并排序和插入排序，均为稳定排序。稳定的好处是，在后续根据斜率排序时，同一条segment上的point在坐标上依旧有序。
代码
Point
```java public class Point implements Comparable
{ 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 x-coordinate of the point
@param y the y-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) { / YOUR CODE HERE */ if (this.x == that.x) {
if (this.y == that.y) { return Double.NEGATIVE_INFINITY; } return Double.POSITIVE_INFINITY;} else if (this.y == that.y) return 0.0; return (this.x - that.x) / (this.y - that.y); }
/**
- 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 0 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 */ if (this.y == that.y) return this.x - that.x; return this.y - that.y; }
/**
- 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
slopeOrder() { / YOUR CODE HERE */ // use lambda return (p1, p2) -> {
}; }double slope1 = slopeTo(p1); double slope2 = slopeTo(p2); if (slope1 < slope2) return -1; else if (slope1 > slope2) return 1; else return 0;
/**
* 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 + ")";
}
}
<a name="5ylNE"></a>
### LineSegment
```java
public class LineSegment {
private final Point p; // one endpoint of this line segment
private final Point q; // the other endpoint of this line segment
/**
* Initializes a new line segment.
*
* @param p one endpoint
* @param q the other endpoint
* @throws NullPointerException if either <tt>p</tt> or <tt>q</tt>
* is <tt>null</tt>
*/
public LineSegment(Point p, Point q) {
if (p == null || q == null) {
throw new NullPointerException("argument is null");
}
this.p = p;
this.q = q;
}
/**
* Draws this line segment to standard draw.
*/
public void draw() {
p.drawTo(q);
}
/**
* Returns a string representation of this line segment
* This method is provide for debugging;
* your program should not rely on the format of the string representation.
*
* @return a string representation of this line segment
*/
public String toString() {
return p + " -> " + q;
}
/**
* Throws an exception if called. The hashCode() method is not supported because
* hashing has not yet been introduced in this course. Moreover, hashing does not
* typically lead to good *worst-case* performance guarantees, as required on this
* assignment.
*
* @throws UnsupportedOperationException if called
*/
public int hashCode() {
throw new UnsupportedOperationException();
}
}
FastCollinearPoints
public class FastCollinearPoints {
private int numberOfSeg;
private LineSegment[] lineSegmentsArr;
// finds all line segments containing 4 or more points
public FastCollinearPoints(Point[] points) {
this.numberOfSeg = 0;
List<LineSegment> lineSegments = new ArrayList<>();
// Throw an IllegalArgumentException if the argument to the constructor is null
if (points == null) throw new IllegalArgumentException();
// Throw an IllegalArgumentException if any point in the array is null,
// or if the argument to the constructor contains a repeated point.
for(int i=0; i < points.length; i++) {
if(points[i] == null) throw new IllegalArgumentException();
for(int j = i+1; j < points.length; j++) {
if(points[j] == null) throw new IllegalArgumentException();
if(points[i].compareTo(points[j]) == 0) throw new IllegalArgumentException();
}
}
if (points.length < 4) {
numberOfSeg = 0;
lineSegmentsArr = new LineSegment[0];
return;
}
Point[] clonePoints = Arrays.copyOf(points, points.length);
int N = clonePoints.length;
Arrays.sort(clonePoints);
// for (Point point : clonePoints) StdOut.println(point);
Point currentCheck;
Point[] otherPoints = new Point[N - 1];
for (int i = 0; i < N; ++i) {
currentCheck = clonePoints[i];
for (int j = 0; j < N; ++j) {
if (j < i) otherPoints[j] = clonePoints[j];
else if (j > i) otherPoints[j - 1] = clonePoints[j];
}
// Sort other points by the slope to current check point.
Arrays.sort(otherPoints, currentCheck.slopeOrder());
int count = 2;
for (int j = 1; j < otherPoints.length; ++j) {
double slope1 = currentCheck.slopeTo(otherPoints[j - 1]);
double slope2 = currentCheck.slopeTo(otherPoints[j]);
if (floatEqual(slope1, slope2, 1E-8)) {
count++;
// Situation1: the last point of the segment reach to the end of otherPoints.
// The second point(otherPoints[j-count+2]) should be larger than the first one.
// It helps us to avoid duplicated segments.
if (j == otherPoints.length - 1 && count >= 4 &&
currentCheck.compareTo(otherPoints[j - count + 2]) < 0) {
Point start = currentCheck;
Point end = otherPoints[j];
lineSegments.add(new LineSegment(start, end));
// StdOut.println(lineSegments);
}
}
// Situation2: the last point of the segment is otherPoints[-1]
else {
// The second point(otherPoints[j-count+1]) should be larger than the first one.
if (count >= 4 && currentCheck.compareTo(otherPoints[j - count + 1]) < 0) {
Point start = currentCheck;
Point end = otherPoints[j - 1];
lineSegments.add(new LineSegment(start, end));
// StdOut.println(lineSegments);
}
count = 2; // continue to find other segments
}
// StdOut.println("count = " + count);
}
}
lineSegmentsArr = new LineSegment[lineSegments.size()];
for (int i = 0; i < lineSegmentsArr.length; ++i)
lineSegmentsArr[i] = lineSegments.get(i);
}
// the number of line segments
public int numberOfSegments() {
return numberOfSeg;
}
// the line segments
public LineSegment[] segments() {
return lineSegmentsArr;
}
// compare two floats, we should not use ==
private boolean floatEqual(double a, double b, double threshold) {
if (a == Double.NEGATIVE_INFINITY)
return b == Double.NEGATIVE_INFINITY;
if (a == Double.POSITIVE_INFINITY)
return b == Double.POSITIVE_INFINITY;
return Math.abs(a - b) < threshold;
}
public static void main(String[] args) {
In in = new In("input9.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("line number: " + collinear.numberOfSegments());
for (LineSegment segment : collinear.segments()) {
StdOut.println(segment);
segment.draw();
}
StdDraw.show();
}
}
排序算法整理
Quick sort
和归并排序的比较
都是用分治的思想解决问题，不同的是，归并排序的递归调用发生在处理数组之前，而快速排序的递归调用发生在处理数组之后，也就是说，当两个子数组都有序的时候，整个数组也就有序了。快速排序不是稳定的(not stable)，因为移动pivot会跳跃多个元素。
算法过程
- 从数列中挑出一个元素，称为 “基准（切分元素）”（pivot）；一般是打乱后随意取第一个元素。也可以用更好的办法选到中间大小的元素作为pivot(patitioning item)
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；具体实现看代码。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列按照以上算法排序。
改进
数组较小的时候改用insertion sort
- sample一下pivot，最好是一个中间值median，常用的方法是median of 3. (取low, mid, hi然后取第二大的作为partitioning item)
3-way partition，为了解决重复元素的问题。三路大概是指三个指针在操作数组。
代码
class Solution { public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length-1); return nums; } public void quickSort(int[] nums, int low, int high){ if(high <= low){ return; } int pivot = partition(nums, low, high); quickSort(nums, low, pivot-1); quickSort(nums, pivot+1, high); } public int partition(int[] nums, int low, int high){ // 左右扫描指针 int i = low, j = high+1; int v = nums[low]; // 从左端扫，直到找到大于等于v的元素，从右端扫，直到找到小于等于v的元素， // 交换这两个元素，事他们的位置正确。 while(true){ while(nums[++i] < v && i < high); while(nums[--j] > v); // j > low是冗余的，v不可能比自己小 if(i >= j){ break; } exch(nums, i, j); } // 将下标0的元素v交换到j的位置（后面就是大于等于v的元素） exch(nums, low, j); return j; } public void exch(int[] nums, int i, int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } }其他应用：find top k
思想比较像找partition和binary search的结合，具体实现如下。
O(N)
Merge sort
算法流程
分治思想，将大问题分成小问题解决，再用所有小问题的答案来解决大问题。
把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
插曲：引用拷贝，对象拷贝：深拷贝浅拷贝
【Java深入】深拷贝与浅拷贝详解_白夜行-CSDN博客插曲：comparator和comparable（看例子）
Java基础系列-Comparable和Comparator代码（递归，自顶向下）
改进1：当数组大小较小的时候使用简单排序。class Solution { private static int[] aux; public int[] sortArray(int[] nums) { this.aux = new int[nums.length]; mergeSort(nums, 0, nums.length-1); return nums; } public void mergeSort(int[] nums, int low, int high){ if(low >= high){ return; } int mid = (low+high) / 2; mergeSort(nums, low, mid); mergeSort(nums, mid+1, high); merge(nums, low, mid, high); } // 简单的两排序数组合并，需要用到额外O(n) public void merge(int[] nums, int low, int mid, int high){ int length = nums.length; int i = low, j = mid + 1; for(int k = low; k <= high; ++k){ aux[k] = nums[k]; } for(int k = low; k <= high; ++k){ if(i > mid){ nums[k] = aux[j++]; } else if(j > high){ nums[k] = aux[i++]; } else if(aux[i] > aux[j]){ nums[k] = aux[j++]; } else{ nums[k] = aux[i++]; } } } }
改进2：在merge之前，检查是否有nums[mid+1] > nums[mid]，如果有说明不需要merge了，直接return。（只需要线性时间）代码（自底向上，迭代）
public int[] sortArray(int[] nums) { this.aux = new int[nums.length]; int length = nums.length; for(int sz = 1; sz < length; sz *= 2){ // low < length-sz 保证有low~mid for(int low = 0; low < length-sz; low += 2*sz){ merge(nums, low, low+sz-1, Math.min(low+2*sz-1, length-1)); } } return nums; }选择排序
执行流程
- 找到最大的数字，和最后一个数字交换，此时最后一个数字是排序部分，其他是未排序部分。
- 找到未排序部分最大的数，和未排序部分的最后一个数字交换。
- 未排序部分只剩一个数字，排序完成。
时间O(n^2)，原地算法没有额外空间，跳跃性的交换，可以举例子说明不稳定性。
// 简单选择排序（不稳定，时间On^2，空间O1）
public int[] selectionSort(int[] nums){
int length = nums.length;
int maxIndex = 0;
// 和冒泡思想类似，也是每轮挑选未排序部分中最大的元素到未排序部分的尾部，成为
// 已排序部分的第一个元素，只是挑选最大元素的方式稍有不同，这个不同也使他不稳定。
// 不稳定：[1,3,2(a),2(b)] -> [1,2(b),2(a),3]
// 此时i代表未排序部分的最后一个元素位置
for(int i = length-1; i >= 1; --i){
maxIndex = 0;
for(int j = 0; j <=i; ++j){
if(nums[j] > nums[maxIndex]){
swap(nums, j, maxIndex);
}
}
}
}
改良策略
在遍历未排序部分时，可以同时找出最大值和最小值，分别将他们放到未排序部分的尾部和头部，减少一半的遍历次数。
// 改良选择排序（每次遍历同时区到最大和最小两个下标进行交换，已排序部分包围未排序部分）
public int[] selectionSortPro(int[] nums){
int left = 0, right = nums.length-1;
int min = left, max = left;
while(left <= right){
min = left;
max = left;
for(int i = left; i <= right; ++i){
if(nums[i] > nums[max]){
max = i;
}
if(nums[i] < nums[min]){
min = i;
}
}
// 分别交换最小最大到未排序部分的首部尾部
swap(nums, left, min);
// 考虑到刚刚的left位置的值被换走了，如果这个left恰好是max的位置，需要继续跟right交换，
// 则更新max的位置到被交换到的地方，也就是min的位置。
if(left == max){
max = min;
}
swap(nums, right, max);
++left;
--right;
}
return nums;
}
冒泡排序
算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数，此时最后一个数为已排序部分，其余为未排序部分；
- 针对所有的未排序元素重复以上的步骤，即通过冒泡的方式将最大的元素冒到未排序部分的最后一个，直到未排序部分只有一个元素。
时间O(n^2)，原地算法没有额外空间，只涉及相邻数据交换所以是稳定的。
// 冒泡排序（稳定，时间On^2，空间1）
public int[] bubbleSort(int[] nums){
int length = nums.length;
// i 代表冒泡的终点，即未排好序部分的最后一个元素的位置，最开始能冒到
// 数组的最后一个元素，每排好一个，就回退一个位置，直到倒数第二个位置也
// 排好，完成排序。
for(int i = length-1; i >= 1; --i){
// j 代表不断冒泡的过程，一直冒到i的位置，当然每一轮随着i的变化，最终
// 冒到的位置也不同。
for(int j = 0; j < i; ++j){
if(nums[j] > nums[j+1]){
swap(nums, j, j+1);
}
}
}
return nums;
}
改良策略
- 当一次遍历未排序部分的过程中没有元素交换，说明已经有序，可以直接跳出循环。
- 记住每次内层循环最后一次的交换位置 k ，k+1 及以后的元素已经有序，可以将已排序部分扩张到 k+1 的位置，即 k 是未排序部分的最后一个下标。
// 改良冒泡排序
public int[] bubbleSortPro(int[] nums){
int length = nums.length;
// 未排序部分的最后一个下标
int k = length-1;
// 记录最后一次交换的位置 j
int index = 0;
// 这里为了比较好表示边界，使用i++的形式，i代表已排序部分的长度
// 内层在未优化时应该是for (j = 0; j < length - 1 - i; j++)
// length-1-i代表未排序部分的最后一个下标，也就是当前未排序部分最大的元素应该去到的位置，在优化后可以被 k（最后一次发生交换的位置） 替代。
for(int i = 0; i < length-1; ++i){
// 标记是否有交换，对应改良1
int has_exchanged = 0;
for(int j = 0; j < k; ++j){
if(nums[j] > nums[j+1]){
swap(nums, j, j+1);
index = j;
has_exchanged = 1;
}
}
// 对应改良1，如果没有交换，说明数组已经有序，直接返回。
if(has_exchanged == 0){
return nums;
}
// 将未排序部分的最后一个下标设为最后一次交换的 j的位置（j+1及以后都是已排序部分，因为没有交换）
k = index;
}
return nums;
}
插入排序
算法流程
- 初始以第一个数字为已排序部分，后面的为未排序部分。
- 不断执行步骤2直到未排序部分没有元素。
时间O(n^2)，原地算法没有额外空间，步骤2中两元素大小相等时不进行交换是为了保持正确的相对位置，所以是稳定的。
public int[] insertionSort(int[] nums) {
int i, j, length = nums.length;
for (i = 1; i < length; i++){
for (j = i - 1; j >= 0 && nums[j] > nums[j + 1]; j--){
swap(nums, j, j + 1);
}
}
return nums;
}
在排逆序的数组的时候是最坏情况，相比选择排序需要做更多的交换，较好的情况是待排数组部分有序。所以引入下面的希尔排序。
希尔排序
算法流程
缩小增量排序，先进行预排序，使任意间隔为h的元素都是有序的（使用插入排序的思想），成为h有序数组，即有h个有序数组交织在一起。这样的好处是，在预排序中，h较大的话可以快速将某些元素移到很远的位置而不用一个一个移过去，为实现更小的h提供方便。h会不断减小到1，这样的h序列叫增量序列increment sequence。到h=1时排完序后整个数组就有序。
// 和插入排序对应着看
void shellsort3(int a[], int n)
{
int i, j, gap;
// 增量序列采用n/2^k，gap从n/2减到1 （Donald Shell增量）
for (gap = n / 2; gap > 0; gap /= 2)
// 排序过程为插入排序，只是间隔1换成gap
for (i = gap; i < n; i++)
for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
Swap(a[j], a[j + gap]);
}
h有序数组变成k有序数组时(k < h)，依然是h有序的。在红书中的increment sequence是3x+1，即1, 4, 13, …, 3x+1，gap从N/3开始，每次除以3，递减到1，这样最坏情况复杂度O(N^3/2)。常用于嵌入式系统等，由于代码少且高效。
所有排序算法总结
参考
若有收获，就点个赞吧
0 人点赞
