Princeton-Algorithm-Sort初级

该文章为Princeton-Algorithms Part I读书笔记，相关视频在此。

1. Sort Any Type of Data

• Comparable接口
  只要对象实现了Comparable接口，它就能够进行比较。

  
  Comparable接口

• v.compareTo(w) 方法

  • v < w : -1
  • v = w : 0

  • v > w : 1

    
    v.compareTo(w)

2. Selection Sort

基本思想：

保持前部分sorted，后部分unsorted。在第i次迭代中，在未排序的部分中找最小的，再将最小的swap到位置i。

两个不变性invariants：

1. 左半部分由小至大已排序
2. 右半部分的数据都不小于左半部分

selection sort invariants

实现

选择排序实现

效率

• O(N^2)
• input insensitive：即使是sorted的input也会花O(N^2)的时间
• 对数据的移动是最少的，最优的数据交换次数，至多O(N)

选择排序性质

3. Insertion Sort

基本思想

保持前部分有序，后部分无序。在第i次迭代中，将第i个数据插入到之前排好序的数据中的相应位置。

两个不变性invariants

1. 已排好序的左半部分
2. 右半部分目前还从未得到访问

insertion sort invariants

实现

插入排序实现

效率

• best：O(N)，worst：O(N^{2)，average：O(N}2)
• Input sensitive，对于partially sorted的数组，时间可以达到线性O(N)

引入一个概念：逆序对inversion

是指一对各自相对大小错位的数据对。对数据的swap操作就是在减少逆序对。

• An array is partially sorted if the number of inversions is ≤ c N.
• 实际上是插入排序的用时是O(I + N)。I是inversion的数量(最好是0，最差N^2)，N是遍历数组的用时。当逆序对的数量是n的数量级，那么称数据partially ordered。对于这样的数据集，插入排序的效率可以达到线性。（因为交换的次数是o(n)，比较的次数也是O(n)）。

4. Shell Sort

基本思想

相当于一个进阶版插入排序。在插入排序中，当数据在找自己的相应位置时，数据的移动一次只移动一位，但在希尔排序中，数据的一次移动h次，称之为h-sort。

基本方法

利用一个increament sequence(1~h)。首先开始h-sort，不断地进行到1-sort(即Insertion sort)。好处在于：

• 对于大的h，insertion sort的比较步长大，会省去很多比较，因此效率高。
• 对于小的h，由于在之前的sorting中减少了一部分inversions，所以数组现在属于partially sorted，因此insertion sort的效率又得以提升！

如何决定要用到的Increment Sequence？
Increment Sequence对该算法的效率有影响。该采用怎样的sequence来做h-sort，仍然处在一个不断研究的过程。

实现

希尔排序实现

效率

理论上确切的数值还没有定论！但是用3x+1这样的序列的话，复杂度大概是O(N^1.5)，实践上其实接近了O(NlgN)。

5. 排序问题引出的相关问题：Shuffle

思路1：

给每个数据随机生成一个自然数，然后再以这个自然数为key来sort数据，结果产生一个uniformly random permutation。

效率：

sort上花销大。

思路2：Knuth Shuffle -> 线性

进行N次循环，第i次循环中，在0 ~ i之间等概率地(uniformly random)生成一个随机数r，最后将a[r]与a[i]的位置交换。

实现

Knuth Shuffle

效率

这样的shuffle方式保证了每种premutation等概率出现(uniformly random)，可以达到线性效率。

注意：只能是动态的部分的范围中随机生成一个数r，不能一直以全局的长度生成一个随机数，这样的出的结果并不是uniformly random permutation。

应用

• 德扑洗牌
  实际应用中实际上由于seed的限制，会有很多bug：
  洗牌实现
  所以，实际应用中可以利用硬件来洗牌，当然，依然不能够完美，总之，完美的随机洗牌是hard的！