六种排序算法总结

作者: 红色黎明 分类: C++,学习笔记 发布时间: 2012-10-06 23:55

今天花了点时间看《数据结构与算法分析(C语言描述)》,把里面涉及到的几种排序算法大致总结了一下。不过这书里面的一些排序示例存在明显错误,所以在看的时候需要注意一下。

1、快速排序。号称实践中最快的已知排序算法。平均运行时间为O(N log N),最坏情形的性能为O(N^2)。

快速排序算法思路:

1、选择枢纽元。

2、初始化i为Left+1,j为Right-2。i向右移,如果A[i]均小于枢纽元,则继续右移。j向左移,如果A[j]均小于枢纽元,则继续向左移。

3、如果此时i仍在j左边,则交换A[i]和A[j](因为此时A[i]大于枢纽元,而A[j]小于枢纽元,则交换之后小的元素在左大的元素在右),直至i>j时此趟排序结束。

4、交换A[i]和枢纽元的位置。此时A[i]的左边均是小于A[i]的,而右边则均大于A[i]。

2、插入排序,时间复杂度为O(N^2)。

插入排序算法思路:

1、将数组的第一个元素当作已经排序的初始数组,而后面的元素通过逐一与前一个元素比较大小,插入到初始数组的适当位置中。

2、若前一个元素较大,则与后一个元素交换(即插入到前一个元素的前面),继续比较;若后一个元素较大,则此趟排序结束。

3、堆排序,时间复杂度为O(N log N)。

堆排序算法思路:此处为最大堆排序。

1、建立二叉树。从倒数第一个父亲结点开始,每次比较父亲结点和其儿子结点的大小,大的结点交换到父亲结点的位置。从而建立起一个堆。在父亲结点发生变化时,需重新与其儿子结点进行排序。

2、将位于根结点的元素与堆的最后一个元素进行交换,将堆的大小缩减1,继续递归地进行堆排序。

4、希尔排序(缩小增量排序),希尔排序的运行时间依赖于增量序列的选择。

希尔排序算法思路:使用希尔增量的希尔排序。

1、设置增量,示例中为 “/2″。

2、从A[Increment]开始,后面的元素逐一与前面隔Increment-1个位置的元素进行比较,若后面元素比前面元素小,则交换元素位置,若两个元素顺序不需改变,则继续向右执行比较。若递减Increment的元素存在的话则继续向前比较,直至元素大小顺序正确或元素不存在为止。

3、反复直到增量的值开始小于0则结束。

5、归并排序,运行时间为O(N log N),不过很难用于主存排序,因为合并两个排序的表需要线性附加内存,算法中还要花费时间拷贝到临时数组等一些附加工作,严重放慢排序速度。

归并排序算法思路:

1、递归地将数组的前半部分和后半部分进行排序。

2、取两个输入数组A和B,一个输出数组C,以及三个计数器Aptr,Bptr,Cptr,它们初始置于对应数组的开始端。A[Aptr]和B[Bptr]中的最小者被拷贝到C中的下一个位置,相关计数器向前推进一步。当两个输入表有一个用完时,将另一个表中剩余部分拷贝到C中。

6、选择排序(最简单的排序)。

选择排序算法思路:首先找到最小元素,将其放在A[0]中,然后找到剩下的N-1个元素中的最小元素,将其存放在A[1]中,重复此过程直至找到第二大的元素,并将其存在A[N-1]中。

以上为C++代码,如若需运行,必须包含algorithm的头文件(里面包含swap函数)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注