排序算法

排序 
冒泡排序：相邻比较，沉淀灭底排序
往复排序：相邻比较，沉淀灭底冒泡灭顶排序
插入排序：插队排序。队已排好，来了一位迟到的人，高个子逐个向后移动，最后新人插入空位。
选择排序：看一遍，选最小的，放到第一位。剩下的，重复。
希尔排序：1维变2维，先一列一列排。相当于按步长分组之后排序。长度依次为：...，5，3，1.
梳排序：跟希尔排序差不多。长度依次为：n，n/1.3，n/1.3/1.3，...，1.

桶排序：分区（0-10，10-20，...）子排，再放回原数组。桶太少？桶的标号合并，桶内再排序，依次放回原数组。


快速排序：双手手掌相向，夹起一摞书。把第一位挖空保存到基准值temp，右手向左移动，碰到第一个小于等于temp的扔到第一位的空位；换左手向右移动，碰到第一个大于等于temp的扔到（右边）空位；换右手...直到双手合掌，把temp放回中间空位。对temp的左边数列和右边数列进行同样的操作，递归。互相抛双色鱼。基准值跟中位数的概念差不多，可用于线性时间查找中位数。



归并排序：二分法分组排序，合并方法：掐尖子生。
堆排序：最大堆，摘头，整堆，循环。
基数排序：从左到右一位位对比调整。

计数排序：非负数。数组A，数组B初始化为0，长度为A的最大值+1，统计A中数字出现次数放入B，0出现的次数为B[0]，A[i]出现的次数为B[A[i]]。再对B处理，从左到右，B[i]=B[i-1]+B[i]，因为自己所在的位置=前面数字的数量+自己的数量。得到的B成为位置数组。
11320=a
1211=b
1345=b

a排序后的aa，1位是0（=index），3位是1，4位是2，5位是3，数组从0开始：
a排序后的aa，0位是0（=index），2位是1，3位是2，4位是3
aa=0?123

========================================================
b=1345, aa=[?????]从a的左边开始
a[0]=1, b[a[0]]=b[1]=3, so: aa[b[a[0]]-1]=aa[3-1]=aa[2],=a[0]=1, 即aa[2]=1
“b[a[0]]-1”，为什么要-1？-1后刚好是aa的下标，而且此标号位置已占/放，-1后前一位才是待定的。

此时，b=1245, aa[??1??]
b[a[1]]=b[1]=2, so: aa[b[a[0]]-1]=aa[2-1]=aa[1],=a[1]=1, 即aa[1]=1
此时，b=1145, aa[?11??]