排序（Algorithms 4th）
排序就是将一组对象按照某种逻辑顺序重新排列的过程
排序算法的目的是将所有元素的主键按照某种方式排列，也许该元素是一个原始数据类型或者是一个对象。当该元素是一个对象的时候，他必须实现了Comparable[]接口，以及实现compareTo()方法。下面是书中排序算法类的模板：
public class Example{
/*要求该数组一定实现了Comparable接口*/
public static void sort(Comparable[] a)
{ /*排序算法*/ }
private static boolean less(Comparable v, Comparable w)
{ return v.comparaTo(w) < 0; }
private static void exch(Comparable[] a, int i, int j)
{ Comparable t = a[i]; a[i] = a[j]; a[j] = t;}
private static 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.readStrings();
sort(a);
assert isSortes(a);
show(a);
}
}
排序性能
性能要从两个方面进行考虑：时间复杂度与空间复杂度。
graph LR 性能-->时间复杂度 性能-->空间复杂度在研究排序算法时，我们需要计算比较和交换的数量，对于不交换元素的算法，我们会计算访问数组的次数
选择排序算法
选择排序的思想是这样的，首先找到数组中最小的那个元素，其次，将它和数组中的第一个元素交换位置。再次，在剩下的元素中找到最小的元素，将它与数组中的第二个元素交换位置。如此反复，直到将整个数组排序。
可以从定义得出，应该对数组进行二次循环，外循环负责迭代位置与交换元素，内循环负责找到剩余数组中最小元素的位置。每次交换都可以排定一个元素，因此总交换次数为\(N\)。由于每次交换都可以排定一个元素，下一次循环比较的元素就会少一个。
\[N+\left( N-1 \right) +\left( N-2 \right) +\cdots \cdots +2+1 \approx \,\,\frac{N^2}{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);
}
}
}
插入排序
插入排序类似于排序好手中的牌，从第一张开始，后面的每一张都放在相对排序好的牌中，当最后一张牌放到应该放的位置时，整个手牌也就排序好了。
与选择排序一样，当前索引左侧的所有元素都是有序的，但对于插入排序来说其最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序也就完成了。
插入排序与初始顺序有关。插入排序最重要的性质就是当前有序，与插入排序不同的是，当前索引只需在左侧找到目前有序的位置就行，而不需要与剩下的所有元素进行比较。该性质使得插入排序的时间复杂度大约是\(N^2/4\)，比选择排序降低了\(1/2\)，但由于数组在内存中是连续存储的，故索引之前与目标插入位置之后的所有元素都要往后移1位。所以需要大概\(N^2/4\)次交换。对于已经排好序的数组速度会快的多。
这是个不错的选择，abc
对于随机排列的长度为\(N\)且主键不重复的数组，平均情况下插入排序需要\(N^2/4\)次比较以及\(N^2/4\)交换。最坏情况下需要\(N^2/2\)次比较和\(N^2/2\)次交换，最好情况下需要\(N-1\)次比较和\(0\)次交换。
算法代码
public class Insertion
{
public static void sort(Comparable[] a)
{
int N = a.length;
for(int i = 1; i < N; i++)
{
for(int j = i; j > 0; j--)
{
if(less(a[j], a[j-1]))
exch(a, j, j-1);
else
break;
}
}
}
}
//首先找到要插入的位置，然后插入，不涉及到交换操作
public class Insertion
{
public static void sort(Comparable[] a)
{
int N = a.length;
for(int i = 1; i < N; i++)
{
int temp = a[i];
int j;
for(j = i; j > 0 && less(a[j], a[j-1]); j--)
{
a[j] = a[j-1];
}
a[j] = temp;
}
}
}
希尔排序
希尔排序是对插入排序的改进，依靠的性质是插入排序对部分有序的数组很有效
即插入排序需要的交换操作和数组中倒置的数量相同，需要的比较次数大于等于倒置的数量，小于等于倒置的数量加上数组的大小再减一
希尔排序的目的是使得数组部分有序，准确来说，希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。
因为子数组是相互独立的，对于每一个 h 子数组，将每一个元素交换到比它大的元素之前去。也就是说只要把插入排序移动的距离由 1 改变成 h 即可。希尔排序的实现转化为了一个类似于插入排序但使用不同增量的过程。
希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，每一个子数组都很短，排序后的子数组都是部分有序的。这两种情况都很适合于插入排序
算法代码
public class Shell
{
public static void sort(Comparable[] a)
{
int N = a.length;
int h = 1;
while(h < N/3)
{
h = h * 3 + 1;
}
while(h >= 1)
{
for(int i = 1; i < N; i++)
{
for(int j = i; j >= h && less(a[j], a[j-h]); j -= h)
{
exch(a, j, j-h);
}
}
h = h/3;
}
}
}
归并排序（分治思想）
归并排序是典型的以空间换时间的优化方案
他能保证将任意长度位\(N\)的数组排序所需时间和\(NlogN\)成正比；它的主要缺点是它所需要的额外空间和N成正比。
原地归并的抽象方法
实现归并的一种直截了当的办法是将两个不同的有序数组归并到第三个数组中。如果每次都产生一个新的数组的话，会造成极大的存储浪费。下面是一种只会消耗常数级内存(\(N\))的方法，首先将涉及到的所有元素复制到一个辅助数组中，再对归并的两个有序数组中每一个值互相比较，最后把归并的结果放回到原数组中。
public static void merge(Comparable[] a, int lo, int mid, int hi)
{
int i = lo, j = mid + 1;
for(int k = lo; k <= hi; k++)
aux[k] = a[k]; //对象变量
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(a[i], a[j]))//左半边当前元素小于右半边当前元素
a[k] = aux[i++];
else //右半边当前元素小于作左半边当前元素
a[k] = aux[j++]
}
}
自顶向下的归并排序（递归）
如果他能将两个子数组排序，他就能通过归并两个子数组来将整个数组排序
public class Merge
{
private static Comparable[] aux;
public static void sort(Comparable[] a)
{
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi)
{
if(hi <= lo) return; //递归出口
int mid = lo + (hi - lo)/2;
sort(a, lo, mid);
sort(a, mid+1, hi);
//调用完这两个排序方法后，说明a[lo..mid]和a[mid+1..hi]已经有序
//这时可以进行判断，如果a[mid] < a[mid+1]，即不用进行merge操作
if(a[mid] < a[mid+1])
return;
else
merge(a, lo, mid, hi);
}
}
排序过程图
改进的三种方法
- 对小规模子数组使用插入排序
- 测试数组是否已经有序
- 不将元素复制到辅助数组
研究一个新问题时，最好的方法是先实现一个你能想到的最简单的程序，然后对他进行改进
自底向上的归并排序
自顶向下的归并排序是分治思想的绝佳体现，将一个大问题分割成很多小问题，然后用所有小问题的答案来解决整个大问题。现在我们从反方向来思考，我们的任务就是处理许多的小问题，然后不断的合并，直到得到我们想要的结果。
public class MergeBU
{
private static Comparable[] aux;
public 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(lo+sz+sz-1, N-1));
}
}
public class MergeBu
排序过程
快速排序
快速排序引人注目的特点包括它是原地排序（只需要一个很小的辅助栈），且将长度为\(N\)的数组排序所需要的时间和\(NlogN\)成正比
快速排序和归并排序一样，是一种分治的排序算法。他将一个数组分为两个子数组，将两部分独立的排序。快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。
在第一种情况下，递归调用在处理整个数组之前；第二种情况下，递归调用在处理整个数组之后。
代码
public class Quick
{
public static void sort(Comparable[] a)
{
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
}
public static void sort(Comparable[] a, int lo, int hi)
{
if(hi <= lo + M)
{
Insertion.sort(a, lo, hi); //小数组用插入排序
return;
} //递归出口
int j = partition(a, lo, hi); //已经归位
sort(a, lo, j-1);
sort(a, j+1, hi);
}
public static Comparable exchMid(Comparable[] a, int lo, int hi)
{
int mid = lo + (hi- lo)/2;
if(less(a[mid], a[lo]))
exch(a, lo, mid);
if(less(a[hi], a[lo]))
exch(a, lo, hi);
if(less(a[hi], a[mid]))
exch(a, mid, hi);
exch(a, mid, hi-1);
return a[hi-1];
}
public static int partition(Comparable[] a, int lo, int hi)
{
Comparable v = exchMid(a, lo, hi);
//此时最右边的数一定比基准大，a[hi-1]是基准，所以从hi-2开始遍历
int i = lo, j = hi - 1;
if (hi - lo < 2)
return lo + (hi - lo) / 2;
while(true)
{
while(less(a[++i], v));//因为最右边的数比基准大，不需要考虑越界
while(less(v, a[--j]));//最左边的数比基准小，不需要考虑越界
if(i >= j) break;
exch(a, i, j);
}
exch(a, i, hi - 1);
return i;
}
}
注意事项
原地切分
如果使用一个辅助数组，我们可以很容易的实现切分（类似于归并排序，头尾两个指针，从a[1]开始比切分元素小的放在头部，比切分元素大的放在尾部，最后肯定剩余一个切分元素的位置），但将切分元素复制回去的开销也许会让我们得不偿失。
别越界
如果切分元素是数组中最小或者最大的那个元素，我们就要小心别让扫描指针跑出数组的边界。但三取样切分可以避免这种越界检测。
保持随机性
数组元素是的顺序是被打乱过的，这样可以最大程度上保证算法的性能
算法改进
切换到插入排序
和大多数递归排序算法一样，改进快速排序性能的一个简单办法基于以下两点：
- 对于小数组，快速排序比插入排序慢；
- 因为递归，快速排序的
sort()方法会在小数组中调用自己；
三取样切分
原始快速排序是采用数组中的第一个元素作为切分元素，但这不能很好的保证该元素恰巧能讲数组切分成大小差不多的两个数组。所以我们考虑的第二哥办法是使用子数组的一部分元素的中位数来切分数组。将取样大小设为3并用大小居中的元素切分的效果最好。还可以讲取样元素放在数组末尾作为“哨兵”来去掉partition()的数组边界测试