浑沦吞枣的过了一遍数据结构，今天把最后一章排序的内容结束。大概实现了一个星期看完的想法，当然不是为了求速度，这一次看主要是把各种数据结构做到心中有数，概念清晰，了解各自有哪些经典的算法和算法思路原理。以后若要用到特定的结构和算法再去算法导论中详细研读。下面是今天的学习笔记。

排序（ranking）

    1.排序可看成是对线性表的操作；多个关键字排序可转化成单个关键字排序；排序的稳定和不稳定；主要讲内排序，其排序算法主要受3方面影响：时间性能，辅助空间，算法复杂性。

    2.按复杂度分：简单算法（冒泡排序、简单选择排序、直接插入排序），改进算法（希尔排序、堆排序、归并排序、快速排序）

    3.冒泡排序

      基本思想：是一种交换排序，两两比较相同相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

      初级版：找第i小的记录时，将第i个格子里的元素与i+1位比较，小的放i位；继续将i位与i+2位比较，直至将i位于第n位比较交换，得到第i小的记录；再进行下一轮找第i+1小的记录。

      正宗的冒泡排序：找第i小的记录时，要同时比较和交换 n-i 次（总n个记录），小的元素经比较交换上浮至第i个位置中。

      冒泡优化：若在某轮上浮中没有发生交换（设置一个是否发生交换的标记flag），则已有序，停止之后的冒泡，结束程序。

    4.简单选择排序

      原理：通过n-i次比较，从n-i-1个记录中选出最小后，将其与第i位的记录交换；

      与冒泡的区别：冒泡是比较一次伴随一次交换；简单选择法是一轮中多次比较完后，进行一次交换。

    5.直接插入排序

      原理：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。类似于理扑克的过程。

    6.希尔排序

      基本有序：小的基本在前，大的基本在后。

      原理：跳跃分割——不稳定，将相聚某个增量的记录组成一个子序列，在子序列内部进行直接插入都的结果依然是基本有序的。将间隔由n/2依次按规律减小，直至1（最后一个增量必须是1）

    7.堆排序

      堆：是这样性质的完全二叉树——每个结点的值都大于或等于其左右孩子结点的值——大顶堆（或<=小顶堆）。

      排序背景：简单选择排序在每轮比较时，并没有把比较结果保存下来，导致后几轮重复前面的一些比较——改进就是每轮选到最小记录时，根据该轮的比较结果对其他记录做出相应的调整。

      排序原理：将待排序的序列构造成一个大顶堆（HeapAdjust函数），此时整个序列的最大值就是根节点，将其移除后由树的末尾元素填补得到一个新的完全二叉树，将其用HeapAdjust函数重新调整为一个大顶堆，重复上述过程，直至最后一个有孩子的结点。

      大顶堆构造函数HeapAdjust：将当前结点找到他左右子结点的较大值，互换，再找到其子节点的较大值互换。

    8.归并排序

      原理：假设初序列含n个记录，看做n个长为1的有序的子序列，两两有序归并（merge函数），得到不小于n/2个的最小整数有序序列，再两两归并，直至得到一个长为n的有序序列为止；递归；

      merge函数：合并两个有序序列SR[i..m]、SR[m+1..n]；i，j对应的记录谁小谁存入TR[k]，谁就++，另一不变，同时k++；进入下一轮，i，j对应的元素继续比较..,直至i增加到大于m或j增加到大于n。

      改进占用内存的递归实现归并排序：用迭代。

    9.快速排序

      原理：通过一趟排序对待排序的序列分成两部分，左边的记录均比枢轴小，右边的比枢轴大——Partiton函数实现；再将左右两部分内部分别进行上述分割，递归实现。

      Partiton函数（返回左右排好后枢轴pivot所在的位置）：每一轮中，找到序列右端起j--第一个比pivot小的与其交换，使小的在其左侧，找到序列左端起i++第一个比pivot大的与其交换，使大的在其右侧；直至i和j相等为止。

      优化——Partiton函数算法实现中对于枢轴pivot的选择，固定选取、随机选取、三数取中、九数取中；

      优化不必要的交换：Partiton函数中的每轮左右排序，比较多次，但只交换一次。

      优化小数组时的排序方案：当high-low小于某个常数时，直接用直接排序法。

      优化递归转迭代省空间。

    10.上述7种排序的时间性能（最好、最差、平均），空间性能、稳定性、适用的序列数量规模等的综合考量选择最合适的排序方法。