算法——排序
一、插入排序
1.直接插入排序与折半插入排序。
1.1步骤：
(1)对于第i个元素，先用临时变量保存之，然后在1 ~ i-1的有序序列中找到其该插入的位置k。
(2)将k到i-1的所有元素后移一位，导致k被腾出。
(3)将临时变量保存的i号元素赋值到k位置。
*对于折半插入排序，因为i前必有序，找插入位置可使用折半查找。注意mid与临时变量相等时（即序列有重复元素），让low = mid + 1而非直接结束，最后将low ~ i-1或high+1 ~ i-1的元素往后移动一位腾出位置供插入。k=low。这样做是为了保证稳定性。考虑abcccdec，最后一个c为待插入前面的元素，mid=4与临时变量匹配就认为找到了k的话，在5的位置还有一个c就会被移动，就不稳定。
*对于直接插入排序，步骤(1)的找位置与步骤(2)同时进行。
*时间复杂度为O(n^2)。空间复杂度为O(1)。稳定。
2.希尔排序/缩小增量排序
2.1思想：
以逐渐减小为1的增量（步长）划分子表，一个增量d可以把原序列化为d个子表，对每个子表插入排序即可。增量为1就是直接插入排序了。
*时间复杂度不明。空间复杂度为O(1)。不稳定。
二、交换排序
1.冒泡排序
*对于求冒泡的趟数的，把每一趟结束的序列写出来不要偷懒。最后千万别忘了得到一个排完序的序列之后实际上程序还要再跑一趟从而发现没有进行任何交换才会结束。
*时间复杂度为O(n^2)。空间复杂度为O(1)。稳定。
2.快速排序
*思想：移走首元素留下空位，比首元素（枢轴pivot）小的移到前面空位从而在后面产生空位，大的移到后面空位从而在前面产生空位，两者交替，最终空的就是存放首元素的位置。
*画二叉排序树的心算方法：把序列写出来，把首元素（枢轴pivot）写到序列下面，序列与其下的pivot充当一个结点。左手手指为low指针，右手笔为high指针，分别指向序列首尾。先low不动，high从当前位置的前一位开始判断是否比pivot小，不是则写入到该结点右分支的最左，high往左移动并继续判断，直到找到并写入到该结点左分支的最右或high与low相等则表明该结点成功生成子结点了。若结束原因非后者，则此次是保持high不变，low从其后一位开始移动直到low指向的大于pivot从而写入到high的位置或low与high相等。两者如此交替重复几轮终会导致low=high。此时两个子结点就生成完毕。然后对两个子结点的序列进行同样的操作。（详见王道p351第10题）
*时间复杂度：最好时树高logn，树的每一层low与high都对整个序列一个个的遍历，为n。故最好时间复杂度O(nlogn)。最坏树是单支树，O(n^2)。快速排序发生最好的情况的概率更大，故平均时间复杂度O(nlogn)。
*空间复杂度：即同时处于栈段的函数栈的个数，即树的树高，因此最好O(logn)最坏O(n)，平均O(logn)。
*定下一个序列的枢轴最终所在的位置需要比较的次数就是该序列长度-1。因为所有的比较无非就是枢轴元素与其他所有元素的比较。
三、选择排序
1.简单选择排序
*思想：每次从无序序列中选出最大/最小的元素交换到有序序列前/后一位。
2.堆排序
*堆即顺序存储的，根与其两个孩子有大小关系的完全二叉树。若堆有n个元素，则非叶结点的数量为⌊n/2⌋个。
*堆分为大根堆与小根堆。
步骤：
a.先将序列建堆。方法是序列前⌊n/2⌋个元素调用HeadAdjust函数。该函数针对传入其的根结点，暂存根结点并产生k与i双指针，其中k永远是i的双亲。在一个i每次乘2（指向其左孩子）的循环中，先比较左右孩子孰大孰小以确定i是否+1成为k的右孩子，在比较i与k孰大孰小决定是否让i移动到k的位置上，若无需移动则表明当前k结点为根的树符合堆的定义了，否则接下来k=i调整其子树成为堆。
b.建立n-1次的循环。这里与选择排序一致，因为堆顶一定是最大/小的元素，省去了选择排序遍历的麻烦。但每次将堆顶元素交换到后面都要调用HeadAdjust函数调整前面。
*建堆时间复杂度O(n)，堆排序时间复杂度O(nlogn)，总体O(nlogn)，空间复杂度O(1)。不稳定。
*堆的插入操作：新结点放序列末尾，然后向上调整。时间复杂度O(logn)。
*堆的删除操作：删除结点，以序列末尾元素代替。然后向下调整。时间复杂度O(logn)。
*题目若要求堆排序、堆插入或堆删除的比较次数，对每个结点，先比较其两个子结点的大小，选出有资格与该结点比较的子结点与该结点比较。子结点若不为叶结点则继续往下记录比较次数。
*题目若要求堆排序、堆插入或堆删除的交换次数，对每个结点，若其子结点移动到该结点的位置就算“交换”，即使实际代码中子结点并没有被该结点赋值。
四、归并排序
1.思想（以排成从小到大的序列为例）：
*全局建立一个辅助数组B，长度与序列长度相同。（因为首位弃用故长度为元素个数+1）
*函数Merge:传入待排序数组A，以及low,high,mid。左半部分数组为A[low~mid]，右半部分数组为A[mid+1~high]，两个子数组都有序。将所有这些元素通通移动到B中同下标的位置。然后设置三指针i,j,k。i为B中左半部分数组的移动索引，j为B中右半部分数组的移动索引，k为A的移动索引。循环比较B[i]与B[j]，谁小谁移到B[k]（相等则先把左子数列中的移到A保证稳定性），A[i]移走i++，A[j]移走j++，k不管谁移走都要加1。最终因为i与j的任何一个出界退出循环。最后再将没有移动完的B的子数组移动到A剩余位置。
*函数MergeSort:利用递归，递归结束条件是传入该层递归函数的low与high相等，否则产生变量mid=(low+high)/2，以low到mid调用他自己，再以mid+1到high调用他自己。最后调用Merge将low到high中的序列排有序。
2.排序趟数取决于树高，O(logn)，每趟O(n)，时间复杂度O(nlogn)，空间复杂度O(n)，稳定。
五、基数排序
1.思想：从关键字本身的信息出发，设关键字为r进制，位数为d位，个数为n个。设置r个队列，将最低位，放进相应队列（分配），再将各个队列的关键字保持先后顺序的拿出来存进链表（收集），再到下一位直至最高位。从高位出发到低位亦可行。
2.共d趟，每趟分配O(n)，收集O(r)，时间复杂度O(d(n+r))，空间复杂度O(r)。
