学做电商那个网站好,网站建设投票主题,网站建设项目工作分解,国内免费域名申请堆排序
假定有一组数据极多的数#xff0c;让我们进行排序#xff0c;那我们很容易想到一种经典的排序方法#xff0c;冒泡排序#xff0c;我们对冒泡排序的时间复杂度进行分析#xff1a; 显然#xff0c;冒泡排序的时间复杂度是O#xff08;n^2#xff09;,当数据量…堆排序
假定有一组数据极多的数让我们进行排序那我们很容易想到一种经典的排序方法冒泡排序我们对冒泡排序的时间复杂度进行分析 显然冒泡排序的时间复杂度是On^2,当数据量巨大时冒泡排序需要比较长时间才能完成排序这在实际应用中是没有意义的。
而相比之下的堆排序时间开销则小得多。
接下来先给出堆排序的代码
void Swap(int* child, int* parent)
{int tem *child;*child *parent;*parent tem;
}void DownAdjust(int* p,int size,int parent)
{int child parent * 2 1;while (childsize){if (childsize-1 p[child 1] p[child])//size-1,不是sizechild;if (p[child] p[parent]){Swap(p[child], p[parent]);//parent child;child parent * 2 1;}else{break;}}
}//堆排序
void HeapSort(int* p, int size)
{//1.建堆//先找到最后一个非叶子节点然后逆序向下调整for (int i (size - 1 - 1) / 2; i 0; i--){DownAdjust(p, size, i);}//2.对堆排序int end size - 1;while (end0){Swap(p[0], p[end]);DownAdjust(p, end, 0);--end;}
}
我们知道堆在逻辑上是完全二叉树在物理上是数组那么给一个很大的数组,我们完全对这个数组进行建堆然后进行堆排序。
接下来对堆排序的时间复杂度进行分析
一个程序的时间复杂度看的是执行次数最多的基本语句因此看建堆的时间复杂度即可 因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明 ( 时间复杂度本来看的 就是近似值多几个结点不影响最终结果 ) 因此时间复杂度为On
两者对比我们发现堆排序显然是更优的。
我们可以看看运行实例
冒泡排序 堆排序 可以看出堆排序的优越性。
