首页 > 代码库 > Learning Data Structure_7_排序

Learning Data Structure_7_排序

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


排序(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种排序的时间性能(最好、最差、平均),空间性能、稳定性、适用的序列数量规模等的综合考量选择最合适的排序方法。