612.1.004 ALGS4 | Elementary Sorts - 基础排序算法

川长思鸟来 2021-12-22 06:33 153阅读 0赞

> sublime编辑器写代码，命令行编译  
> 减少对ide的依赖//可以提示缺少什么依赖import  
> 所有示例代码动手敲一遍  
> Graham's Scan是经典的计算几何算法  
> shffule 与 map-reduce 有关—— 云计算  
> 知道这些算法在身边切实的应用，对学习动力很有帮助  
> **下一章开始，使用 git进行源代码管理!**  
> 先用来做自己的项目管理

## Inspiration ##

计算机思维——不要重复造轮子  
零件的通用性——拆分拆分再拆分，专业与分工细致

1.Callback = reference to executable code

![1143923-20190311101802016-97778912.png][]

> 核心思想是将函数作为实参传递给其他函数  
> Interface-Java 使我们能够以类型安全的方式使用为任何类型的数据开发的排序算法

**Roadmap**

> 对象需要实现Compareble Interface()  
> 这些数据类型具有重新实现compareTo()方法的实例方法

排序实现里与数据类型无关  
具体的比较由Comparable 接口处理  
![1143923-20190311101822635-5416969.png][]

## What I can use —— code ##

*  [Selection Sort | 选择排序][Selection Sort _]
 *  [Insertion Sort | 插入排序][Insertion Sort _]
 *  [ShellSort | 希尔排序][ShellSort _]

> 点击链接可看动画演示

**1 Two useful sorting abstrations**

**Less**

private static boolean less(Comparable v, Comparable w) { return v.compareTo(w)< 0 ;}

**Exchange**

//exchange a[i] & a[j] private static void exch(Comparable[] a,int i ,int j) { Comparable swap = a[i]; a[i] = a[j]; a[j] = swap; }

**2.Selection Sort**

> select the min

## 1 rules of the game ##

*  Goal : Sort **any** type of data

**sorting problem**  
![1143923-20190311101832094-819989914.png][]

real numbers

![1143923-20190311101842807-1968988279.png][]

String

![1143923-20190311101848336-397894379.png][]

### Callbacks ###

> key point :passing function as arguments to other function  
> 核心思想是将函数作为实参传递给其他函数  
> Interface-Java 使我们能够以类型安全的方式使用为任何类型的数据开发的排序算法  
> ![1143923-20190311101859823-1600520676.png][]

### Roadmap | 技术路线图 - Callback ###

public inter face Comparable<Item> { public int compareTo(Item that); // generics method }

> 对象需要实现Compareble Interface()  
> 这些数据类型具有重新实现compareTo()方法的实例方法  
>   
> 排序实现里与数据类型无关  
> 具体的比较由Comparable 接口处理

![1143923-20190311102115919-1858432870.png][]

### Two useful sorting abstrations ###

**Less**

private static boolean less(Comparable v, Comparable w) { return v.compareTo(w)< 0 ;}

**Exchange**

private static void exch(Comparable[] a,int i ,int j) { Comparable swap = a[i]; a[i] = a[j]; a[j] = swap; }

## 2 Selection Sort | 选择排序 ##

> 即使数据集已经部分有序，仍需重新遍历一遍  
> N^2

QuestionDemo-Selection Sort

![1143923-20190311102150458-471376514.png][]

Inner Loop - Selection sort

![1143923-20190311102222835-274629351.png][]

public class SelectionSort { public static void sort(Comparable[] a) { int N = a.length; for (i = 0; i < N;i++) { int min = i; for(int j = i+1; j < N;j++) if(less(a[j], a[min])) min = j; exch(a, i, min); } } private static boolean less(Comparable v,Comparable w) { return v.compareTo(w) < 0; } private static void exch (Comparable[] a, int i, int j) { Comparable swap = a[i]; a[i] = a[j]; a[j] = swap; } }

## 3 Insertion Sort | 插入排序 ##

> Move one position at one time  
> 如果左边（比自己）更大，则继续向左互换

QuestionDemo-Insertion Sort

Step1

![1143923-20190311102254174-217091959.png][]

Step2

![1143923-20190311102323034-1424322501.png][]

**Inner Loop - Insertion sort**

![1143923-20190311102351505-1599498032.png][]

import edu.princeton.cs.algs4.Insertion; import edu.princeton.cs.algs4.StdOut; import edu.princeton.cs.algs4.StdRandom; public class InsertionSort { public static void sort(Comparable[] a) { int N = a.length; for (int i = 0; i < N; i++) { for(int j = i; j > 0; j--) if(less(a[j],a[j-1])) exch(a,j,j-1); else break; } } private static boolean less(Comparable v,Comparable w) { return v.compareTo(w) < 0; } private static void exch (Comparable[] a, int i, int j) { Comparable swap = a[i]; a[i] = a[j]; a[j] = swap; } } public class SortDemo { public static void main(String[] args) { int N = Integer.parseInt(args[0]); Double[] a = new Double[N]; for (int i = 0; i < N; i++) { a[i] = StdRandom.uniform(); } Insertion.sort(a); for (int i = 0; i < N; i++) { StdOut.println(a[i]); } } }

## 4 ShellSort | 希尔排序 ##

> Shell - the name of the creator 1959  
> Move more than one position at one time // compare to the Insertion Sort  
> 一次移动多个位置  
> 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
> 
> 希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

Photo：

![1143923-20190311102416187-18375732.png][]

**7，3，1 Sort**

![1143923-20190311102434906-28681648.png][]

*  Shellsort: which increment sequence to use?

![1143923-20190311102453137-1652157929.png][]

package edu.princeton.cs.algs4; public class ShellSort{ public static void sort(Comparable[] a){ int n = a.length; x = 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ... int h = 1; while (h < n/3) h = 3*h + 1; while (h >= 1) { //h-sort the array // Insertion sort for (int i = h; i < n;i++){ for (j = i; j >= h && less(a[j],a[j-h]); j-= h){ exch(a, j, j-h); } } assert isHsorted(a, h); h /=3;//move to next increment,eg. 13,4,1 } assert isHsorted(a, h); } /*************************************************************************** * Helper sorting functions. ***************************************************************************/ // is v < w ? private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } // exchange a[i] and a[j] private static void exch(Object[] a, int i, int j) { Object swap = a[i]; a[i] = a[j]; a[j] = swap; } /*************************************************************************** * Check if array is sorted - useful for debugging. ***************************************************************************/ private static boolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) if (less(a[i], a[i-1])) return false; return true; } // is the array h-sorted? private static boolean isHsorted(Comparable[] a, int h) { for (int i = h; i < a.length; i++) if (less(a[i], a[i-h])) return false; return true; } // print array to standard output private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.println(a[i]); } } /** * Reads in a sequence of strings from standard input; Shellsorts them; * and prints them to standard output in ascending order. * * @param args the command-line arguments */ public static void main(String[] args) { String[] a = StdIn.readAllStrings(); ShellSort.sort(a); show(a); } }

## 5 Shuffle - StdRandom.java ##

> Knuth Shuffle  
> a uniformly random permutation of the input array in linear time.  
> 洗牌

**Goal**  
from

![1143923-20190311102550486-126209297.png][]

to  
![1143923-20190311102608829-1018527771.png][]

**Code**

![1143923-20190311102630075-211907261.png][]

public class StdRandom { public static void shuffle(Object[] a) { int N = a.length; for (int i = 0; i < N; i++); { int r = StdRandom.uniform(i+1); //StdRandom.uniform 均匀分布 [0,i+1) //r = between 0 and i exch(a,i,r); } } }

## 6 Convex Hull ##

> Graham's Scan  
> 凸包  
> The convex hull of a set of N points is the smallest perimeter fence enclosing the points

**Goal**  
![1143923-20190311102654277-1315524037.png][]

> counterclockwise：逆时针  
> clockwise:顺时针

**mechanical algorithm**

![1143923-20190311112551395-636545359.png][]

**Computer application**  
1.motion planning

![1143923-20190311112715217-1617893246.png][]

2.farthest pair

![1143923-20190311112747776-1346319504.png][]

**Fact**

![1143923-20190311112810697-81297335.png][]

P.S. Polar angle

![1143923-20190311112828546-1595400457.png][]

### Graham's Scan 葛立恒扫描 ###

> 没错 ，就是提出葛立恒数的那位葛立恒  
> accroding the two facts

**Demo**

![1143923-20190311112846597-1532228275.png][]

**challenge**

![1143923-20190311112906549-1249873208.png][]

### Implementing ccw（counterclockwise） ###

**what is ccw**

![1143923-20190311112921547-1052378071.png][]

\*\* math\*\*

> according to the Slope （斜率）  
> ![1143923-20190311112946675-1913589614.png][]

\*\* implement\*\*  
![1143923-20190311113018283-657213168.png][]

转载于:https://www.cnblogs.com/Neo007/p/10509568.html

[1143923-20190311101802016-97778912.png]: /images/20211220/84bf0052da284855b7708d4f4b7c69f6.png
[1143923-20190311101822635-5416969.png]: /images/20211220/c9d88e68b49c4fd9847df44da15dc3c8.png
[Selection Sort _]: https://www.toptal.com/developers/sorting-algorithms/selection-sort
[Insertion Sort _]: https://www.toptal.com/developers/sorting-algorithms/insertion-sort
[ShellSort _]: http://www.sorting-algorithms.com/shell-sort
[1143923-20190311101832094-819989914.png]: /images/20211220/bf7f134ccccf4d608708f77e831f84e5.png
[1143923-20190311101842807-1968988279.png]: /images/20211220/6b10c3bcc0d64fdab740db6375148cf8.png
[1143923-20190311101848336-397894379.png]: /images/20211220/6fe179ad14ab49b69d13e7e54d20f3ea.png
[1143923-20190311101859823-1600520676.png]: /images/20211220/46a5cd3688a04db3b9caac56ac8ee609.png
[1143923-20190311102115919-1858432870.png]: /images/20211220/51429bb372c243f88a69b1f57764485f.png
[1143923-20190311102150458-471376514.png]: /images/20211220/077655acbcd145bcb87cfbc4e26dbe49.png
[1143923-20190311102222835-274629351.png]: /images/20211220/4715cdb9df0a45e382bd2f2c762e6c94.png
[1143923-20190311102254174-217091959.png]: /images/20211220/a79f0e30ed174329acda656409ccce77.png
[1143923-20190311102323034-1424322501.png]: /images/20211220/bfe244eaee8d497db78ec574e4c555b1.png
[1143923-20190311102351505-1599498032.png]: /images/20211220/570f6bfcf0724b67b4f307cf809063b6.png
[1143923-20190311102416187-18375732.png]: /images/20211220/f49b6b8915464416b0d92dadf8603358.png
[1143923-20190311102434906-28681648.png]: /images/20211220/b7631f9ff5794e188fbafc1ab88792af.png
[1143923-20190311102453137-1652157929.png]: /images/20211220/7a46c0a4438b4fd18f5ab0678564f722.png
[1143923-20190311102550486-126209297.png]: /images/20211220/8fa4f336a26f4a58bbc5202bb5981c7d.png
[1143923-20190311102608829-1018527771.png]: /images/20211220/501c0cfdb01844208c2eac2840683712.png
[1143923-20190311102630075-211907261.png]: /images/20211220/a982b26250c147898f95251f0ee10f39.png
[1143923-20190311102654277-1315524037.png]: /images/20211220/4b2dfb3b8a2740f0b1e87df7c37bb8bb.png
[1143923-20190311112551395-636545359.png]: /images/20211220/a269fa742dc941f2839bb2f08687690a.png
[1143923-20190311112715217-1617893246.png]: /images/20211220/fec217010c7d46759fd1ae90841d4d28.png
[1143923-20190311112747776-1346319504.png]: /images/20211220/5fe452a59f094110a07bbca05ba1834c.png
[1143923-20190311112810697-81297335.png]: /images/20211220/5be23aa4f6da492eb57924e74c9da304.png
[1143923-20190311112828546-1595400457.png]: /images/20211220/99b887ca17414a58a1c134b0a4272284.png
[1143923-20190311112846597-1532228275.png]: /images/20211220/fe563c6f1feb4ff098a0cca18e9b27bd.png
[1143923-20190311112906549-1249873208.png]: /images/20211220/d1fc890182904cd698d88b52f9142427.png
[1143923-20190311112921547-1052378071.png]: /images/20211220/620801ac5e6c48a3b91610c02222c1d5.png
[1143923-20190311112946675-1913589614.png]: /images/20211220/d739492efce44c0e9ed7ea3b090640f0.png
[1143923-20190311113018283-657213168.png]: /images/20211220/e9a9aea3f9394a6bb7ad72c1ec4ba441.png