goal00001111

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

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