1.基础排序
我们查看一个元素那个元素有一条记录，我们要排序的信息准确地说，记录中有一部分叫做关键字（主键），我们要讲记录根据关键字进行排列。这就是排序问题。在Java中，元素通常都是对象，对主键的抽象是通过一种内置的机制（Comparable接口）来实现的。
1.1 排序类算法模板
public class Example {
public static void sort(Comparable\[\] a){
//algr2.1 or 2.2 or 2.3 or others
}
private static boolean less(Comparable v,Comparable w)
{ return v.compareTo(w) < 0;}
private static void exch(Comparable\[\] a,int i,int j)
{ Comparable t =a\[i\];a\[i\]=a\[j\];a\[j\] =t;}
private void show(Comparable\[\] a)
{ //在单行中打印数组
for(int i=0;i<a.length;i++)
StdOut.print(a\[i\]+" ");
StdOut.println();
}
public static boolean isSorted(Comparable\[\] a)
{ //测试数组元素是否有序
for(int i = 1;i<a.length;i++)
if(less(a\[i\],a\[i-1\])) return false;
return true;
}
public static void main(String\[\] args)
{//从标准输入读取字符串，将它们排序并输出
String\[\] a = In.readString();
sort(a);
assert isSorted(a);
show(a);
}
}1.1.1排序成本模型
在研究排序算法时我们计算比较和交换的次数，对于不交换元素的算法，我们计算访问数组的次数。
1.1.2数据类型
排序算法适用于任何实现了Comparable接口的数据类型，像Integer，String，Double都实现了comparable接口。在创建自己的数据类型时，我们要保证实现Comparable接口，要做到这一点，只需要实现一个compareTo()方法来定义目标类型对象的自然次序（natrual order）。
public class Date implements Compareable<Date>
{
private final int day;
private final int month;
private final int year;
public Date(int d,int m,int y)
{ day=d;month=m;year=y;}
public int day(){ return day;}
public int month(){ return month;}
public int year(){ return year;}
public int compareTo(Date that)
{
if( this.year > that.year) return +1;
if( this.year < that.year) return -1;
if( this.month > that.month) return +1;
if( this.month < that.month) return -1;
if( this.year > that.year) return +1;
if( this.year < that.year) return -1;
return 0;
}
public String toString()
{ return month+"/"+day+"/"+year;}
}1.1.2.1全序关系
自反性(Totality): for all v ,v=v; 反对称性(Antisymmetry)：if v<=w and w<=v,then v=w; 传递性(Transitivity)： if v<=w,and w<=x,then v<=x.
1.2选择排序
找到一个最小的元素并将它和未排序序列的第一个元素交换。每次交换都能排定一个位置因此交换的从次数是N。对于长度为N的数组选择排序需要(N^2)/2次比较和N次交换。选择排序有两个很鲜明的特点：1.运行时间和输入无关2.数据移动是最少的。 好了，不扯这些学术的，选择排序其实就是个冒泡排序，在没排序的元素里找到一个最小的元素然后把它排到前面仅此而已。 
public class Selection
{
public static void sort(Comparable\[\] a)
{
int N = a.length;
for (int 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)
{ /\* as before */ }
private static void exch(Comparable\[\] a, int i, int j)
{ /\* as before */ }
}1.1.3插入排序
顾名思义，插入排序其实有点像选择排序的逆过程，跟着index走走走，碰到一个元素把它跟已排序的数组元素比较，直到找到一个比他大的元素，然后插到他前面，要是没有比他大的就扔到最后。
public class Insertion
{
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)
{ /\* as before */ }
private static void exch(Comparable\[\] a, int i, int j)
{ /\* as before */ }
}但是考虑一种特殊的情况那就是如果我们要排序的数组是一个部分有序的数组，那插入排序可能比别的排序算法都要快。BTW，想要提高插入排序的速度并不难，只要在内循环中将较大的元素都向右移而不是交换两个元素（这样访问数组的次数就能cut掉一半）。这个特性为shell排序埋下伏笔。疯狂暗示。
1.3比较两种算法
光说不行，给出一个能计算时间的class
public class SortCompare
{
public static void main(String\[\] alg,Double\[\] a){
Stopwatch timer = new Stopwatch();
if(alg.equals("Insertion")) Insertion.sort(a);
if(alg.equals("Selection")) Selection.sort(a);
if(alg.equals("Shell")) Shell.sort(a);
if(alg.equals("Merge")) Merge.sort(a);
if(alg.equals("Quick")) Quick.sort(a);
if(alg.equals("Heap")) Heap.sort(a);
}
public static double timeRandomInput(String alg,int N,int T){
double total =0.0;
double\[\] a = new Double\[N\];
for(int t =0 ;t < T; t++){
for(int i =0;i < N;i++){
a\[i\] = StdRandom,uniform();
total += time(alg,a);
}
return total;
}
public static void main(String\[\] args){
String alg1 = arg\[0\];
String alg2 = arg\[1\];
int N = Integer.parseInt(args\[2\]);
int T = Integer.parseInt(args\[3\]);
double t1 = timeRandomInput(alg1,N,T);
double t2 = timeRandomInput(alg2,N,T);
StdOut.printf("For %d random doubles\\n %s is",N,alg1);
StdOut,printf(" %.1f times faster than %s\\n", t2/t1,alg2);
}
}1.3.1如何打乱一个数组
方法很简单给已有的数组每个元素产生一个随机数，然后将这些数组元素按照随机数大小排列即可。BUT，我们真的要付出一个完整排序的时间来打乱数组吗？可不可以找到一个更6的方法，absolutely！而且这个算法只需要线性的时间。首先index i遍历数组每次在0和i之间产生一个随机数，然后交换i和随机数位置的元素即可。给下class：
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);
exch(a, i, r);
}
}
}会有人在选择数组位时随机选择0~N之间的数，这实际上是不能实现随机排序的。为啥？你该恶补离散了骚年，赶紧翻出《Discrete Mathematics and it’s Application》偷偷看。
1.4希尔排序Shell
希尔排序其实是插入排序和其他排序的一种结合，首先假设我们有一个数组，我们先将他部分排序按照不同的增量，这样就获得了一个比较小的数组来进行排序，这恰恰是插入排序所擅长的部分。
如上图所示，数组有15个元素，按照增量4对数组（h有序数组）进行分离然后对着四个元素排序，我们计算增量的公式有很多种，推荐一个1/2（3^k-1），这是一个递增序列。 希尔排序更高效的原因是他权衡了子数组的规模和有序性（通过前面给的那个公式），排序之前每个h子数组都很短，排序之后数组是部分有序的，这两种情况都很适合希尔排序。（子数组的有序情况取决于递增序列的选择）。 给出希尔排序的代码~~（WordPress写代码好麻烦连个tab键都用不了，先下个vs code，蓝瘦，安一波发现Java的extension是RedHat 提供的啊，最近刚被？IBM收购不是，闭源系统祖师爷收购开源先锋23333）。
public class Shell{
public static void sort (Comparable \[\]){
int N=a.length();
int h=1;
while(h<N/3) h =3*h+1; //1,4,13,40,121........
while(h>=1){
//make the array be h-sorted array
for(inti=h;i<N;i++){
//insert the element a\[i\] to a\[i-h\],a\[i-2\*h\],a\[i-3\*h\]...
for(intj= i;j >= h &&less(a\[j\],a\[j-h\]); j-=h)
exch(a,j,j-h);
}
h=h/3;
}
}
}希尔排序的运行时间是不到平方级的，对插入排序的一个小小改变就突破了平方级的限制，这就是算法的精妙之处，BTW，最坏情况是和N^2/3成正比。 放图
1.5归并排序Merge
归并排序算法的思想很简单就是一个分治法的思想，只要将数组一分为二，然后不断将小数组分下去对每个小数组排序然后对两个小数组合并最终会得到一个完整排序的数组，但是归并排序需要一个辅助数组aux[]。
public class Merge{
private static void merge(Comparable\[\] a,Comparable\[\] aux,int lo,int mid,int hi){
assert isSorted(a,lo,mid);
assert isSorted(a,mid+1,hi);
for(int k=lo;k <= hi;k++)
aux\[k\]=a\[k\];
int i=lo,j=mid+1;
for(int k=lo;k<=hi;k++){
if(i>mid) a\[k\]=aux\[j++\];
else if(j>hi) a\[k\]=aux\[i++\];
else if(less(aux\[j\],aux\[i\])) a\[k\]=aux\[j++\];
else a\[k\]=aux\[i++\];
}
assert isSorted(a,lo,hi);
}
}解释一下assetion语句，在Java里arrest提供了一种检查代码的方法，通过assert你可以表示自己想干什么，在Java里assert接受一个boolean，默认是禁用的。 
所以你可以在编程时开启assert方法，然后在最后关闭这不会对最终的代码有任何影响。 归并排序对于任何数组包括倒序的情况都有同样的时间复杂度，nlogn。 假设你要对10亿个元素排序如果你使用插入排序，那么你可能需要300年，但归并排序只需要半个小时。 这张图很好解释了归并排序 
学习过离散数学我们知道第一个等式的原因就是，当建设N是2的幂次时，每次分治都会产生两个小数组的时间和一次总的比较的时间。 下面这种方法是两边同时除以n，比较偏数学 
或者下面这种数学归纳法的方式 
归并排序的时间复杂度很棒，但是空间复杂度不很友好，你需要至少一半的空间来储存辅助数组，虽然有方法来实现原地排序的Merge但是方法太过复杂。所以有几个小trick可以提高Merge算法的性能，第一个在数组元素的个数小于一定值时，采用插入排序。
if(hi <= lo+CUTOFF -1){
Insertion.sort(a,lo,hi);
return;
}另一种方法是不是每次豆浆数组copy进辅助数组，而是两个数组的互相充当对方的辅助数组，这样就节省了一半的copy操作的时间。 
还有一种方法是在排序前先检查是否已经数组有序。这样即使每个元素都需要检查也只需要线性复杂度的时间。
if(!less(a\[mid+1\],a\[mid\])) return;
public class Merge{
private static void merge(Comparable\[\] a,Comparable\[\] aux,int lo,int mid,int hi){
assert isSorted(a,lo,mid);
assert isSorted(a,mid+1,hi);
for(int k=lo;k <= hi;k++)
aux\[k\]=a\[k\];
int i=lo,j=mid+1;
for(int k=lo;k<=hi;k++){
if(i>mid) a\[k\]=aux\[j++\];
else if(j>hi) a\[k\]=aux\[i++\];
else if(less(aux\[j\],aux\[i\])) a\[k\]=aux\[j++\];
else a\[k\]=aux\[i++\];
}
assert isSorted(a,lo,hi);
}
private static void sort(Comparable\[\] a,Comparable\[\] aux ,int lo,int hi){
if(hi <= lo+CUTOFF -1){
Insertion.sort(a,lo,hi);
return;
}
int mid = lo+(hi-lo)/2;
sort(aux,a,lo,mid);
sort(aux,a，mid+1,hi);
if(!less(a\[mid+1\],a\[mid\])) return;
merge(a,aux,lo,mid,hi);
}
public static void sort(Comparable\[\] a){
aux = new Comparable\[a.length\];
sort(a,aux,0,a.length-1);
}
}1.5.1自底向上的归并排序（Bottom-up Merge sort）
自底向上的方法与递归不同，我们将每个数组中的元素都看作一个已经排序的长度为1的数组，然后将这些元素按二元组排序，然后按四元组排序。最终通过Merge我们会获得一个完全有序的数组。下面是递归和自底向上两种方法直观的比较。 
这样做的好处是可以遍历整个数组但是不用递归操作。所以自底向上的时间复杂度最差是logn。 上代码
public class MergeBU {
private static Comparable\[\] aux;
private static void merge(Comparable\[\] a,int lo,int mid,int hi){
//as before
}
private static void sort(Comparable\[\] a){
int N = a.length;
aux = new Comparable\[N\];
for(int sz=1;sz<N;sz=sz+sz)
for(int lo=0;lo<N-sz;lo+=sz+sz)
merge(a,lo,lo+sz-1,Math.min(N-1,lo+sz+sz-1));
//此处将最后一组元素可能会少于sz的情况考虑不会出现数组越界
}
}2 凸包convex hull
这个必须要讲一下哈，2018徐州ICPC的最后一题233当时看出来了，但是不会葛立恒扫描法当场gg，还好最后混了个银嘻嘻。 凸包的定义就是平面上一组点的集合，凸包是恰好能将全部点囊括进去的凸多边形。 
like this。凸包的计算可以引申出许多有趣的问题，例如，徐州m题是求一个最小个数的点的集合刚好把另一组点囊括进去。或者是求两点之间跨越障碍物的最小距离例如： 
或者是寻找一组点之间距离最远的两点。但是这些问题都离不开凸包的求解，而凸包求解中应用的葛立恒扫描法( Graham scan)的关键部分就是排序。 凸包的顶点相对于具有最低y坐标的点p以极角的递增顺序出现。 只能通过逆时针转动来穿过凸包。 将p点作为起点也就是y坐标最低的点，然后按照从p到其他点极角的大小排序，然后在遍历的过程中我们直接舍弃那些无法产生逆时针旋转的角，例如1 2 3时 3到4无法产生逆时针旋转的角所以我们将其舍去，然后4到5也无法产生逆时针旋转的角所以舍去4 ，以此类推。
这是葛立恒扫描法在处理简并问题式的数学过程 
不多bb，上一小段代码
public class Point2D
{
private final double x;
private final double y;
public Point2D(double x, double y)
{
this.x = x;
this.y = y;
}
...
public static int ccw(Point2D a, Point2D b, Point2D c)
{
double area2 = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
if (area2 < 0) return -1; // clockwise
else if (area2 > 0) return +1; // counter-clockwise
else return 0; // collinear
}
}葛立恒扫描法用两种方法对点进行排序
Stack<Point2D> hull = new Stack<Point>();
Arrays.sort(p,Point2D.Y_ORDER); //此时点p\[0\]是y坐标最小的点
Arrays.sort(p,p\[0\].BY\_POLAR\_ORDER);//此时数组按照p\[0\]极角大小排序
hull.push(p\[0\]);
hull.push(p\[1\]); //将这两个点压栈
for(int i =2 ;i<N;i++){
Point2D top = hull.pop();
while(Point2D.cww(hull.peek(),top,p\[i\])<=0)//通过ccw方法判断两个点事逆时针的
top=hull.pop();
hull.push(top);
hull.push(p\[i\]); //将p\[i\] 压栈
}3排序复杂度
计算复杂性是我们研究算法解决问题X的性能的一个重要指标。 计算模型：可允许的操作。 花费（cost）：操作的计数。(# compare) 上界（upperbound）：是指一些（some）算法对于问题X的花费。 下界（lowerbound）：是指所有（all）算法对于问题X的花费。 最优算法：可以用最小花费解决问题X的算法。 对于我们目前的排序问题来说，计算模型是决策树（decision tree）（只允许通过比较这种方式访问数据），花费是对比较的次数计数，上界是nlogn由mergersort得来，下界为止，最优算法也未知。 
决策树模型。所以我们提出，排序的下界是lg(N!)Nlg(N),假设数组由n个不同的值a1到an组成，最坏的情况由决策树的高度h决定，高度为h的二叉树最多有2^h个叶子，因为只有N！种不同的排序，所以至少有N！片叶子。所以有2^h≥#leaves≥N!,由斯图灵公式（Stirling formula）我们得到h≥lg(N!)Nlg(N),所以对于排序问题，可以得到下界也为Nlg(N)，最优算法为mergesort。 但是在这几种情况下，下限可能不成立，（1）数组初始有序（2）主键的分布（3）主键的表示形式。 例如：（1）对于部分有序的数组，插入排序可能只需要N-1次比较； （2）有重复的主键，三分快排会更快； （3）数字主键，比较数字和字符比字符串要快得多。 学习的过程是实践和理论结合，在只有比较操作的层面Mergesort是最优，可是在空间复杂度上，，Mergesort并不是最优。以刚刚的理论为知道，我们能否设计出一个算法可以使得比较的次数为1/2×Nlg(N)，或者在时间复杂度和空间复杂度都是最优？这是值得我们去思考的。
4比较器（comparators）
在实际问题里我们常常要对同一组数据按不同的主键值排序，像Comparable接口使用的是元素的自然顺序
public class Date implements Comparable {
private final int month, day, year;
public Date(int m, int d, int y) {
month = m; day = d; year = y;
}
…
public int compareTo(Date that) {
if (this.year < that.year ) return -1;
if (this.year > that.year ) return +1;
if (this.month < that.month) return -1;
if (this.month > that.month) return +1;
if (this.day < that.day ) return -1;
if (this.day > that.day ) return +1;
return 0;
}
}接下来是使用可改变排序的Comparator接口
public interface Comparator<Key>
int comparator(Key v,Key w)要注意的是所有的排序必须是之前我们讨论过得全序序列，例如，对于一个字符串，我们可以有以下几种排序方法：
Natural order 自然序列. Now is the time
Case insensitive 不区分大小写. is Now the time
Spanish 西班牙语. café cafetero cuarto churro nube ñoño
British phone book . McKinley Mackintosh
演示几种系统排序的方法
String\[\] a; ...
Arrays.sort(a); ...
Arrays.sort(a, String.CASE\_INSENSITIVE\_ORDER); ...
Arrays.sort(a, Collator.getInstance(new Locale("es"))); ...
Arrays.sort(a, new BritishPhoneBookOrder());最重要的是将数据类型的定义与两个被比较的对象的定义分开。 下面用Comparator代替Comparable来实现一个使用我们插入排序：
public static void sort(Object\[\] a, Comparator comparator) {
int N = a.length;
for (int i = 0; i < N; i++)
for (int j = i; j > 0 && less(comparator, a\[j\], a\[j - 1\]); j--)
exch(a, j, j - 1);
}
private static boolean less(Comparator c, Object v, Object w) {
return c.compare(v, w) < 0;
}
private static void exch(Object\[\] a, int i, int j) {
Object swap = a\[i\];
a\[i\] = a\[j\];
a\[j\] = swap;
}在实际使用中首先定义一个内部类实现Comparator接口然后再实现compare（）方法，下面给出一个完全的实列：
import java.util.Comparator;
public class Student{
public static final Comparator<Student> BY_NAME = new ByName();
public static final Comparator<Student> BY_SECTION = new BySection();
private final String name;
private final int section;
private static class ByName implements Comparator<Student>{
public int compare(Student v,Student w)
{ return v.name.compareTo(w.name);}
}
private static class BySection implements Comparator<Student>{
public int compare(Student v,Student w)
{ return v.section - w.section;}
}
}4.1极角顺序
给定一个点p，根据与点p极角的顺序来对其他点排序。 
在Graham scan中得到应用，可以通过高中学习的三角函数的方法来判断极角大小，可是计算三角函数的花费是很高的，所以采用上面提到的ccw()方法：
1.如果p1高于p点而p2低于q点，那p1的极角更小；
2.如果p1低于p点而p2高于q点，那p1的极角更大；
3，其他情况根据ccw(p,p1,p2)来判断。
老规矩上代码：
import java.util.Comparator;
public class Point2D
{
public final Comparator<Point2D> POLAR_ORDER = new PolarOrder();
private final double x,y;
private static int ccw(Point2D a,Point2D b,Point2D c)
{ /\*as in previous lecyure \*/}
private class PolarOrder implements Comparator<Point2D>
{
public int compare(Point2D q1,Point2D q2)
{
double dy1 = q1.y - y;
double dy2 = q2.y - y;
if (dy1 == 0 && dy2 == 0){} //p,p1,p2 在一条线上
else if (dy1 >= 0 && dy2 < 0) return -1; //q1高于p点，q2低于p点
else if (dy2 >= 0 && dy1 < 0) return +1; //q1低于p，q2高于p
else return -ccw(Point2D.this,q1,q2); //从内部类中访问调用点
}
}
}5.稳定性
一个排序算法称为稳定的当它在主键值相同时可以保留这些元素在原序列的相对位置。在我们之前提到的排序算法中，只有插入排序和归并排序是稳定的，选择排序，shell排序和快速排序都是不稳定的排序方法。下图是一个直观的例子。 
插入排序是稳定的因为相同键值的元素永远不会被放到前一个元素前。 
选择排序是不稳定的 
Mergesort也是稳定的，我们可以设置如果键值相同则统一从左侧序列获取。
