没有合适的资源？快使用搜索试试~ 我知道了~

首页"九种内部排序算法详解及图示"

"九种内部排序算法详解及图示"

6 下载量 114 浏览量更新于2023-11-23 2 收藏 906KB PDF 举报

本资源包含《数据结构》考研的九种内部排序算法的详细讲解，以表格、图文方式呈现每一种排序算法的排序过程。包含的排序算法有直接插入排序、折半排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、链式基数排序，并附有简单介绍各个排序方法的时间复杂度。适用范围为考研党、想要学习排序算法的人员，以及在校大学生等。资源难度为初级，易于学习人员理解。每种排序算法基本以 “小标题-算法代码-排序过程图示-练习” 的方式进行描述，并建议结合博主的博文链接进行搭配学习。链接已放在资源之中（含408真题，免费可用）。【文章共127字】. 全部完成。

折半查找算法代码

typedef struct{

KeyType key; //关键字域

InfoType otherinfo; //其他域

}ElemType;

typedef struct{

ElemType *R; //存储空间基地址，建表时按实际长度分配，0号单元留空

int length; //当前长度

}SSTable;

int Binary_Search(SSTable ST, KeyType key){ // 折半查找

int 1ow = 1, high = ST.length, mid; //置查找区间初值，low为1，high为表长

while (1ow <= high) {

mid = (low + high)/2; //取中间位置

if (ST.R[mid] == key)

return mid; //查找成功则返回所在位置

else if (ST.R[mid] > key)

high = mid - 1; //从前半部分继续查找

else

low = mid + 1; //从后半部分继续查找

}

return -1; //查找失败，返回-1

}

//对顺序表L做折半插入排序

void BInsertSort (SqList &L){

for(i=2; i <= L.length; ++i){

L.r[0] = L.r[1]; //将待插入的记录暂存到监视哨中

//置查找区间初值

low = 1;

high = i-1;

//在r[low..high]中折半查找插入的位置

while (low <= high){

m = (low + high)/2; //折半

if(L.r[0].key < L.r[m].key) high = m - 1; //插入点在前一子表

else low = m + 1; //插入点在后一子表

}

for (j = i-1; j >= high+1; --j)

L.r[j+1] = L.r[j]; //记录后移

L.r[high+1] = L.r[0]; //将 r[0] 即原 r[i]，插入到正确位置

}

折半排序算法代码

第一种写法

（带哨兵）

//对顺序表L做折半插入排序

void BInsertSort(int a[], int n) { //n = a.size()

int i, j, temp, mid, low, high;

for (i = 1; i < n; ++i) {

temp = a[i]; //将待插入的记录暂存到temp中

//置查找区间初值

low = 0;

high = i - 1;

//在a[low..high]中折半查找插入的位置

while (low <= high) {

mid = (low + high) / 2; //折半

if (a[mid] > temp) high = mid - 1; //插入点在前一子表

else low = mid + 1; //插入点在后一子表

}

for (j = i - 1; j >= high + 1; --j){

a[j + 1] = a[j]; //记录后移

}

a[j + 1] = temp;

}

第二种写法

折半排序算法代码

1 2 3 4 5 6 7 8 9 10 11

关键字序列 7 10 13 16 19 29 32 33 37 41 43

指针 low mid high

low = 1, high = 11

mid = (low + high)/2 = 6

1 2 3 4 5 6 7 8 9 10 11

关键字序列 7 10 13 16 19 29 32 33 37 41 43

指针 low mid high

第一次查找：比较要查找元素 11 和中间元素 29 的大小。

因为11 < 29，所以待查元素存在，在范围为[low, mid-1]中，即[1,5]。

low = 1, high = mid - 1 = 5

mid = (low + high)/2 = 3

用折半查找法查找元素11是否在关键字序列{7，10，13，16，19，29，32，33，37，41，43}中

1 2 3 4 5 6 7 8 9 10 11

关键字序列 7 10 13 16 19 29 32 33 37 41 43

指针

low

mid

high

第二次查找：比较要查找元素 11 和中间元素 13 的大小。

因为11 < 13，所以待查元素存在，在范围为[low, mid-1]中，即[1,2]。

low = 1, high = mid - 1 = 2

mid = (low + high)/2 = 1 （向下取整）

剩余92页未读，继续阅读

各种内部排序算法演示

2009-01-21 上传

我用java做的各种内部排序算法演示,做的不是很好(确实不好),不过挺好玩的,大家看看.Windows中运行Run_Windows.bat(Linux下为Run_linux.sh)自动编译并运行(运行完成自动删除*.class).需要先配置好JDK

九种排序算法

2008-01-17 上传

【问题描述】在教科书中，各种排序算法的时间复杂度分析结果只给出了算法执行时间的渐进度，或者大概执行时间。试通过随机数据比较算法的关键字比较次数和关键字移动次数，以取得直观的感受。
【基本要求】（1）对各种内部排序算法进行比较，包括（书中没有提到请自行查阅课外资料）：冒泡排序，插入排序，选择排序，计数排序，快速排序，归并排序，希尔排序，基数排序，堆排序。
（2）待排序表的表长不小于100；其中数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标有关键字参加的比较次数和关键字的移动次数。（关键字交换计为3次移动）
（3）最后要对结果作出简单的分析，包括对各组数据得出结果波动大小的解释。
【实现提示】主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如：正序，逆序和不同程度的乱序。注意采用分块调试的方法。
【选作内容】对不同的输入表长作试验，观察检查两个指标相对于表长的变化关系。还可以对稳定性作验证。

住在阳光的心里

粉丝: 7989
资源: 20

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

"九种内部排序算法详解及图示"

各种内部排序算法演示

九种排序算法

数据结构实验报告-内部排序-多种排序算法的实现-(含希尔排序!)-代码及运行截图

考研数据结构算法代码总结.pdf

数据结构考研试题 内部考研资料

数据结构考研解析：排序算法详解

数据结构考研指南：排序算法详解与外部排序策略

数据结构考研重点：排序算法稳定性分析

2010考研数据结构与排序算法源码解析

考研内部排序详解与算法分析

最新资源

数据结构考研试题内部考研资料