归并排序算法是典型的分治算法,对于规模较大的问题,可以分解成若干容易求解的简单的问题,最后把解合并构成初始问题的解。不存在跳跃比较,所以归并排序是一种稳定的排序算法。比较占用内存,效率高且稳定。
基本思想:假设初始序列有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2](上括号,不小于它的最小整数)个长度为2或1的有序子序列;再两两归并,……,如此重复,直至得到一个长度为n的有序序列为止,称为2路归并排序。 Continue reading
归并排序算法是典型的分治算法,对于规模较大的问题,可以分解成若干容易求解的简单的问题,最后把解合并构成初始问题的解。不存在跳跃比较,所以归并排序是一种稳定的排序算法。比较占用内存,效率高且稳定。
基本思想:假设初始序列有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2](上括号,不小于它的最小整数)个长度为2或1的有序子序列;再两两归并,……,如此重复,直至得到一个长度为n的有序序列为止,称为2路归并排序。 Continue reading
http://www.coder4.com/archives/3036
1、线性表也可以用顺序表示实现,即用一组地址连续的存储单元依次存储线性表的数据元素。特点是ai和ai+1位于相邻的存储单元上,只要确定了存储线性表的起始位置,任意元素都可以随机存取。 Continue reading
堆排序就是对简单选择排序进行的一种改进。(调整堆的过程就是选择待排序序列中的最大值,本质和选择排序是一样的)。
记录的比较与交换是跳跃式进行,因此堆排序是一种不稳定的原地排序方法。
不适合待排序序列个数较少的情况。
在堆排序算法中,我们使用的是大顶堆,小顶堆通常在构造优先队列时使用。
堆结构
堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子的结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。 Continue reading
基本思想:简单选择排序就是通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录交换值。
Continue reading
Enjoy your Study Time!
版权@TracyLLing
希尔排序相当于直接插入排序的升级(分组插入排序),又称缩小增量排序,同属于插入排序类,不是稳定的排序算法。
比直接插入排序快的原因:
刚开始的时候间隔较大, 每个组里面的数据较少,排序很快
;当分隔加大的时候, 每组的数据变多, 但是因为已经有了前面的工作,数据接近于有序, 所以也很快
基本思想:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下,效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。 Continue reading
快速排序和冒泡排序同属交换排序,但是由于关键字的比较和交换是跳跃进行的,所以是不稳定的排序。
快速排序的基本思想:通过一趟排序讲待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对着两部分记录进行排序,以达到整个序列有序的目的。 Continue reading
冒泡排序算法为一种比较排序算法(还有快速排序),较小的数字如同气泡般慢慢浮到上面,所以称为冒泡排序。为就地排序,稳定。
算法思想:两两比较相邻记录的关键字,如果反序则交换,知道没有反序的记录为止。 Continue reading
插入排序是对少量元素进行排序的有效算法,各个数字是原地排序,插入排序是稳定的。
算法思想:将一个元素通过和当前已经排序好的数组的最大元素进行比较,并在待插入数组较小的情况下通过设置哨兵,整体移动,插入正确位置,从此得到一个新的排序好的数组的过程。
算法导论中的伪代码:
△INSERT-SORT(A)
for j ← 2 to length[A]
do key ← A[j]
△Insert A[j] into the sorted sequence A[1..j-1].
i ← j-1
while i>0 and A[i]>key
do A[i+1] ← A[i]
i ← i-1
A[i+1] ← key