算法导论：比较排序算法札记

算法导论：比较排序算法笔记

好几天没看《算法导论》，今天看了一天的排序算法，印象第一的是基数算法，因为居然违反我的一个常识，它采用的是最低有效位进行排序的。

插入排序、归并排序、堆排序、快速排序，这些都是比较排序算法：它们都是通过对元素进行比较操作来确定输入数组的有序次序，这些算法可以用决策树模型分析，可以证明任意比较排序算法排序n个元素的最坏情况运行时间的下界为Omega（nlgn），其中堆排序和归并排序是渐进最优的比较排序算法。

算法

最坏情况运行时间

平均情况/期望运行时间

插入排序（原址）

Theta（n^2）

Theta（n^2）

归并排序

Theta（nlgn）

Theta（nlgn）

堆排序（原址）

Theta（nlgn）

--------

快速排序（原址）

Theta（n^2）

Theta（nlgn）期望）

堆排序堆排序的时间复杂度和归并排序一样，都是O(nlgn)，另外它具有插入排序的空间原址性优点，即任何时候都只需要常数个额外的空间元素存储临时数据。堆排序中主要是引入了一种称为“堆”的数据结构来进行信息管理。这里的（二叉）堆可以看作是一个近似的完全二叉树。树上的每一个结点对应数组中的一个元素，如图1所示。
二叉堆可以分为两种形式：最大堆和最小堆。因为在堆排序中应用的是最大堆，所以这里只说最大堆，最大堆中是指除根以外的所有结点i都要满足：A[PARENT[i]]>=A[i]，即某个结点的值至多与其父节点一样大。
两个性质：

一个包含n个元素的堆可以看着一颗完全二叉树，那么该堆的高度是O(lgn)，而且堆结构上的一些基本操作的运行时间至多与树的高度成正比，即时间复杂度O(lgn);当用数组表示存储n个元素的堆时，叶结点下标分别是[n/2]+1,[n/2]+2,…，n。

伪代码：

这个子过程是采用自底向上建堆的过程，里面用到了上文的性质2。
具体代码实现过程：

伪代码：


具体代码实现：
#include <utility>using std::swap; int partition(int* array, int left, int right){        int index = left;        int pivot = array[index];               swap(array[index], array[right]);        for (int i=left; i<right; i++)        {                if (array[i] > pivot)    // 降序                        swap(array[index++], array[i]);        }        swap(array[right], array[index]);        return index;} void qsort(int* array, int left, int right){        if (left >= right)                 return;        int index = partition(array, left, right);        qsort(array, left, index - 1);        qsort(array, index + 1, right);}




 

 

查看更多 下一篇