用字符“画”排序算法。
基本约定：
- 排序的对象为一个数组
array - 排序的范围为
[lo,hi) - 同时排序的长度为
hi-lo - array示意图如下：
lo hi
array: -----[ ]-----
方括号中的元素为排序区间
Bubble Sort(冒泡排序)
实现：
lo hi
[ ][ ]
------------ ----------
待排序区间W 已排序区间S
不断的遍历W，将最大值移到S的最左侧hi处；
改进：
lo hi
[ k ][ ]
------------ ----------
待排序区间W 已排序区间S
不断的遍历W，即[lo,hi)区间，将最大值移到S的最左侧hi处，同时判断W的尾部是否有序；
若W的[k,hi)已经有序，则下一次对[lo, hi=k)进行遍历；
Selection Sort(选择排序)
lo hi
[ m ][i ]
------------ -----------
待排序区间W 已排序区间S
不断的从W中选出最大者m，放入S的第一个位置i处；
Insertion Sort(插入排序)
lo hi
[ i ][e ]
------------ -----------
已排序区间S 待排序区间W
不断将W中第一个元素e，插入到S中位置i处；
i为S中元素不大于e的最大元素的位置；
(1) 基本形式：先search再insert；
(2) 改进版：因为S是有序的，故从右向左遍历S，与e比较，若比e大，则右移；
Merge Sort(归并排序)
lo hi
[ ]
分：将排序区间分成左右两部分
[ ][ ]
------ ------
L R
合：同时遍历L和R，按大小依次插入到新区间S中
[ ]
--------------
已排序区间S
不断的递归，执行“分，合”，直至L、R中只有一个元素。
Quick Sort(快速排序)
lo hi
[ p ]
--------- ----
L R
基本原理：在数组中，随机选定元素p，使得 p左侧元素 <= p <= 右侧元素；
不断的对L、R执行上述过程，直至L、R只有一个元素。
将p称为轴点，轴点可选取范围为[lo, hi]，与基本约定有所不同；
轴点：左侧元素[lo, mi) <= 轴点元素mi <= 右侧元素(mi, hi]。
根据轴点的确定过程，可知快速排序前后，可能打乱相同元素间的相对顺序；
即快速排序是不稳定的。
(1)基本实现
[ ][i j][ ]
---- ----
L R
随机选取轴点p，将i和j与轴点p进行比较，从而将i和j不断的归入到L或R中；
(2)变种实现
[p][ q][i ][k----------]
------- --------
L R
随机选取轴点p，并对调至最左侧，不断的比较k和候选轴点p，
p <= k : k归入R中；
p > k : k归入L中，即交换i和k，L的长度+1；
最终交换p和q，q做为最终的轴点。
Heap Sort(堆排序)
max --------->
/ \
[ # --- heap --- ][i ]
lo hi
---------------- --------------
堆区间H 已排序区间S
不断地将堆顶元素(即最大值)，放入S的最左侧i处（有点类似于选择排序）。
Shell Sort(希尔排序)
(1) 希尔排序过程
将整个序列视作一个矩阵，逐列各自排序w-sorting (w为矩阵列数)
排序序列: 8 1 5 6 9 4 3 7 2
步长序列: [1, 2, 3, 5]
5-sorting : 8 1 5 6 9 => 4 1 5 2 9 => 4 1 5 2 9 8 3 7 6
4 3 7 2 8 3 7 6
3-sorting : 4 1 5 => 2 1 5 => 2 1 5 3 7 6 4 9 8
2 9 8 3 7 6
3 7 6 4 9 8
2-sorting : 2 1 => 2 1 => 2 1 4 3 5 6 7 9 8
5 3 4 3
7 6 5 6
4 9 7 9
8 8
1-sorting : 1 2 3 4 5 6 7 8 9
进行w-sort时，使用选择排序：
因为开始的时候，w更大，列元素个数少，逆序对少，选择排序消耗少；
等到后面的时候，w更小，列元素个数多，但逆序对少，选择排序消耗少；
(2) 间隔有序
h-ordered : 序列s[0,n)对于任何 0<= i < n-h，都有s[i] <= s[i+h]；
任一个序列进行h-sorting后，必定是h-ordered；
若一个序列同时为g-ordered和g-ordered，则序列也为(mg+nh)-ordered，m和n为自然数；
排序对比
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 [ yehuohan@gmail.com ]