常用排序算法的比较(6)

0。0 第一次写了10KB+的代码略感动。 虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

2.程序设计

2.1 概述

该程序用typedef struct_Time{ Char Name[20]; // 算法名称 Double Num;//运算所需时间 }Time;

利用结构体Time储存排序算法名称，以及算法排序所用具体时间。这样的定义，方便了在比较时间长短时，能够对应的知道算法名称。从而更方便的判断哪种算法比较优化。

在具体运算中，该程序代码的具体功能如下： GetRandom（）：按照用户的需要，输入所需测试的随机数个数，产生随机数至文件里；

rRandom（）：利用文件指针，将文件里的数据读写到程序里利用指针申请的动态内存当中；

InsertSort（）：直接插入排序； BinarySort（）：折半查找插入排序； ShellSort（）：希尔排序； BubbleSort（）：冒泡排序； QuickSort（）：快速排序； SelectSort（）：简单选择排序； HeapSort（）：堆排序； MergeSort（）：归并排序； Fprintf（）：将排序好的数据记录到文件当中； TimeSort（）：利用Time的指针，对存入Time的动态内存中的元素的关键字Num进行排序，找出耗时最短时间的两种排序方法；

IntoMenu（）：程序人性化体现，按照菜单提示轻松使用该程序。

2.2程序运行流程图

0。0 第一次写了10KB+的代码略感动。 虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

2.3主要算法的具体逻辑分析

2.3.1直接插入排序

直接插入排序的主要思路是，将待排序的数值不断的插入到有序段中，将有序段逐渐扩大，知道所有数值进入有序段中。

InsertSort（）：

for( i = 1; i <= Num; i++) { p[0] = p[i]; j = i -1; while( p[0] < p[j]) { p[j +1] = p[j];//将大于p[i]的数往后移动 j--; } p[j +1] = p[0]; }

亮点：将顺序表中的p[0]（第一个元素）作为排序的哨兵，不用于存储有效数据，用来保存第i个元素p[i]的副本，使不导致因为记录后移而丢失p[i]的内容。还在查找循环中“监视”下标变量j是否越界。防止数据溢出造成错误。

2.3.2折半查找插入排序

该方法，在直接插入排序的思路之上，将查找方式——折半查找植入到算法当中。

折半查找，先取有序段的中间元素与查找值进行比较。如查找值小于中间元素，则再取低半部的中间元素与查找值进行比较。如此重复知道查找成功或最终未找到这个数为止。

与直接插入排序法相比，折半查找排序法减少了与关键字相比较的次数，从而提高了算法的效率。

BinarySort（）：

for( i = 1; i <= Num; i++) { p[0] = p[i]; low = 1; high = i -1; while(low <= high)//寻找有序列中待插入值的位置 { m = (low + high)/2; if(p[0] < p[m])