首页 25考研 在职考研 0元畅学 26考研

新东方在线 > 考研 > 计算机 > 考研计算机资料 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

计算机考研：数据结构常用算法精析(9)

2013-12-12 15:18:39来源：新东方在线编辑

　　分割算法

　　int Partition(Sqlist&L,int low,int high)

　　{ L.R[0]=L.R[low];

　　pivotkey=L.R[low].key;

　　while(low

　　{ while(low=pivotkey)

　　--high;

　　L.R[low]=L.R[high];

　　while(low

　　++low;

　　L.R[high]= L.R[low];

　　}

　　return low;

　　}

　　总控函数：

　　void QSort(Sqlist&L,int low,int high)

　　{ if(low

　　{

　　pivotloc=Partition(L,low,high);

　　QSort(L,low,pivotloc-1);

　　QSort(L,pivotloc+1,high);

　　}

　　}

　　调用方法：QSort(L,1,L,lenght);

　　算法分析：

　　若 原本就正序或逆序，每次调用一次后，记录数只减少了一个，故此时T(n)=C(n+(n-1)+……+1)=O(n2)。这是快速排序效率最差的情况。所以快速排序算法有待改进。

　　简单选择排序： 属于稳定排序时间复杂度(O(n2))

　　算法描述

　　void Slectsort (Sqlist& L) ∥直接选择排序的算法∥

　　{

　　for (i=1;i

　　{

　　j=SeloctMinkey(L,i); //从i到L.len中选择key最小的记录

　　if (i!=j)

　　{ temp=L.R[i];

　　L.R[i]=L.R[j];

　　L.R[j]=temp;

　　}

　　}

　　}

　　堆排序：属于选择排序 不稳定，时间复杂度(O(nlogn))，没有最好和最差的分别，也需 要辅助的栈空间

　　若ki≥k2i、ki≥k2i+1。此时，根结点k1的值最大，称为“大根堆”。

　　若ki≤k2i、ki≤k2i+1满足“”关系，则k1最小，称为“小根堆”。

　　在堆排序中，我们采用的是大根堆，原因是大根堆中，根最大，对删除很方便，直接把它与最后一个叶子结点交换就可以了。

　　记录key集合k={k1 k2……kn}， 排序 分两步进行：

　　(1)将{k1 k2……kn}建成一个大根堆;

　　(2)取堆的根(key最大者)，然后将剩余的(n-1)个key又调整为堆，再取当前堆

　　的根(key次大者)，……，直到所有key选择完毕。

考研公开课小程序

本文关键字: 计算机 考研 数据结构

上一页 1 2 3 下一页

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
25考研 在职研 AI择校 去测评 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

考研资料大礼包

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10