06 2006 档案

     摘要: 插入排序是一种简单的排序方法,因为的实现比较简单,所以在数据量较少时应用很广泛。插入排序根据其插入的不同方式,可以分为直接插入排序,折半插入排序,2-路插入排序,表插入排序和希尔排序。在这里我将一一写出各种插入排序的算法代码。  阅读全文

posted @ 2006-06-20 23:22 梦想飞扬 阅读(3342) | 评论 (1)  编辑 |

     摘要: 归并排序算法以O(nlogn)最坏情形运行时间运行,而所使用的比较次数几乎是最优的。它可以用递归的形式实现,形式简洁易懂。但是需要注意的是当用递归形式时,如果数据较多,则开销很大,实用性很差,所以我们一般采用非递归的形式。我这里两种形式都给出。  阅读全文

posted @ 2006-06-15 23:24 梦想飞扬 阅读(1715) | 评论 (2)  编辑 |

     摘要: 快速排序是在实践中最快的已知排序算法,它的平均运行时间是O(NlogN)。该算法之所以特别快,主要是由于非常精练和高度优化的内部循环。在队列中寻找合适的枢点元素,并按枢点元素划分序列,是快速排序算法的关键。
为简单起见,我这里数组的第一个元素作为枢点元素,重新排列数组,使得枢点元素之前的元素都小于枢点元素,而枢点元素之后的元素都大于或等于枢点元素。  阅读全文

posted @ 2006-06-14 10:19 梦想飞扬 阅读(1165) | 评论 (0)  编辑 |

     摘要: 排序在最坏的情况下,其时间复杂度也能达到O(nlogn)。相对于快速排序来说,这是它最大的优点,此外,堆排序仅需要一个记录大小供交换用的辅助存储空间。
堆排序的数据结构是二叉堆,二叉堆的特点有两个,一个是它是一棵完全二叉树,另一个是它的根结点小于孩子结点,所以我们很容易找到它的最小结点----根结点;当然如果你想找到最大结点的话,那就要扫描所有的叶子结点,这是很费时间的,如果你想找的是最大结点的话,你最好把它弄成一个大顶堆,即一棵根结点大于孩子结点的完全二叉树。
二叉堆通常用数组来实现,它舍弃下标0,从下标1开始置数,则很容易满足,对于数组中任意位置i上的元素,其左儿子的位置在2i上,右儿子的位置在2i+1上,双亲的位置则在i/2上。
堆排序的算法之一是把数组构建成二叉堆----这只要增添一个长度为n+1的辅助空间,然后把原数组的元素依次插入到二叉堆即可。然后删除二叉堆的根,把它作为排序后的数组的第一个元素,然后使二叉堆的长度减1,并通过上移使得新得到的序列仍为二叉堆,再提取新二叉堆的第一个元素到新数组。依此类推,直到提取最后  阅读全文

posted @ 2006-06-14 10:18 梦想飞扬 阅读(4242) | 评论 (2)  编辑 |

posted @ 2006-06-07 18:00 梦想飞扬 阅读(6540) | 评论 (4)  编辑 |

posted @ 2006-06-04 16:53 梦想飞扬 阅读(1391) | 评论 (4)  编辑 |

posted @ 2006-06-04 16:52 梦想飞扬 阅读(1949) | 评论 (2)  编辑 |

posted @ 2006-06-01 23:33 梦想飞扬 阅读(677) | 评论 (1)  编辑 |