【排序算法时间复杂度】综合排序算法的比较各种内部排序算法的时间复杂度分析结果只给出...

网友回答

【答案】 #include stdio.h
　　#include stdlib.h
　　#define Max 100 //假设文件长度
　　typedef struct{ //定义记录类型
　　 int key; //关键字项
　　}RecType;
　　typedef RecType SeqList[Max+1]; //SeqList为顺序表，表中第0个元素作为哨兵
　　int n; //顺序表实际的长度
　　//==========直接插入排序法======
　　void InsertSort(SeqList R) { //对顺序表R中的记录R[1¨n]按递增序进行插入排序
　　 int i,j;
　　 for(i=2;i =i;j--){ //对当前无序区R[i¨n] 自下向上扫描
　　 if(R[j+1].key =pivot.key) //基准记录pivot相当与在位置i上
　　 j--; //从右向左扫描，查找第一个关键字小于pivot.key的记录R[j]
　　 if(i pivot.key，则
　　 R[j--]=R[i]; //交换R[i]和R[j]，交换后j指针减1
　　 }
　　 R[i]=pivot; //此时，i=j，基准记录已被最后定位
　　 return i; //返回基准记录的位置
　　}
　　//2.=====快速排序===========
　　void QuickSort(SeqList R,int low,int high) { //R[low..high]快速排序
　　 int pivotpos; //划分后基准记录的位置
　　 if(low high,则表示R[low]是叶子，调整结束；否则先令large指向R[low]的左孩子
　　 if(large =R[large].key) //temp始终对应R[low]
　　 break; //当前调整结点不小于其孩子结点的关键字，结束调整
　　 R[low]=R[large]; //相当于交换了R[low]和R[large]
　　 low=large; //令low指向新的调整结点，相当于temp已筛下到large的位置
　　 }
　　 R[low]=temp; //将被调整结点放入最终位置上
　　}
　　//==========构造大根堆==========
　　void BuildHeap(SeqList R) { //将初始文件R[1..n]构造为堆
　　 int i;
　　 for(i=n/2;i> 0;i--)
　　 Heapify(R,i,n); //将R[i..n]调整为大根堆
　　}
　　//==========堆排序===========
　　void HeapSort(SeqList R) { //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
　　 int i;
　　 BuildHeap(R); //将R[1..n]构造为初始大根堆
　　 for(i=n;i> 1;i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。
　　 R[0]=R[1]; R[1]=R[i];R[i]=R[0]; //将堆顶和堆中最后一个记录交换
　　 Heapify(R,1,i-1); //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质。
　　 }
　　}
　　//==========二路归并排序===========
　　//===将两个有序的子序列R[low..m]和R[m+1..high]归并成有序的序列R[low..high]===
　　void Merge(SeqList R,int low,int m,int high) {
　　 int i=low,j=m+1,p=0; //置初始值
　　 RecType *R1; //R1为局部量
　　 R1=(RecType *)malloc((high-low+1)*sizeof(RecType)); //申请空间
　　 while(i