`

数据结构之排序的实现

阅读更多

1、插入排序

 

void InsertSort(RecType R[],int n){
    int i,j,k;
    RecType temp;
    for (i=1; i<n; i++) {
        temp=R[i];
        j=i-1;
        while (j>=0&&temp.key<R[j].key) {
            R[j+1]=R[j];
            j--;
        }
        R[j+1]=temp;
   
       printf("    i=%d  ",i);
       for (k=0; k<n; k++) {
           printf("%3d",R[k].key);
        }
        printf("\n");
    }
    
}

 2、冒泡排序

 

void BubbleSort(RecType R[],int n){
    int i,j,k;
    RecType temp;
    for (i=0; i<n-1; i++) {
        for (j=n-1; j>i; j--) {
            if(R[j].key<R[j-1].key){
                temp=R[j];
                R[j]=R[j-1];
                R[j-1]=temp;
            
            }
        }
        printf("  i=%d:    ",i);
        for (k=0; k<n; k++) {
            printf("%2d",R[k].key);
        }
        printf("\n");
    }
}

 

3、选择排序

 

void SelectSort(RecType R[],int n){
    int i,j,k;
    RecType temp;
    for (i=0; i<n-1; i++) {
        k=i;
        for (j=i+1; j<n; j++) {
            if(R[j].key<R[k].key){
                k=j;
            }
        }
        if(k!=i){
            temp=R[i];
            R[i]=R[k];
            R[k]=temp;
        }
        printf("  i=%d:    ",i);
        for (k=0; k<n; k++) {
            printf("%2d",R[k].key);
        }
        printf("\n");
    }
}

 4、希尔排序

 

void ShellSort(RecType R[],int n){
    int i,j,d,k;
    RecType temp;
    d=n/2;
    while (d>0) {
        for (i=d; i<n; i++) {
            j=i-d;
            while (j>=0&&R[j].key>R[j+d].key) {
                temp=R[j];
                R[j]=R[j+d];
                R[j+d]=temp;
                j=j-d;
            }
        }
   
       printf("  d=%d:    ",d);
       for (k=0; k<n; k++) {
           printf("%3d",R[k].key);
       }
       printf("\n");
       d=d/2;
  }
}

 

5、快速排序

 

void QuickSort(RecType R[],int s,int t){
    int i=s,j=t,k;
    RecType temp;
    if(s<t){
        temp=R[s];
        while(i!=j){
            while(j>i&&R[j].key>temp.key)
                   j--;
            if(i<j){
                R[i]=R[j];
                i++;
            }
            while(i<j&&R[i].key<temp.key)
                i++;
            if(i<j){
                R[j]=R[i];
                j--;
            }
        }
        R[i]=temp;
        printf("      ");
        for(k=0;k<10;k++){
            if(k==i){
                printf(" [%d]",R[k].key);
            }else{
                printf("%4d",R[k].key);
            }
        }
        printf("\n");
        
        QuickSort(R,s,i-1);
        QuickSort(R,i+1,t);
    
    }
}
 

6、堆排序

 


void Sift(RecType R[],int low,int high){

    int i=low,j=2*i;
    RecType temp=R[i];
    while(j<=high){
        if(j<high&&R[j].key<R[j+1].key){
            j++;
        }
        if(temp.key<R[j].key){
            R[i]=R[j];
            i=j;
            j=2*i;
        }else{
            break;
        }
    }
    R[i]=temp;
}
void HeapSort(RecType R[],int n){
    int i;
    RecType temp;
    for(i=n/2;i>=1;i--)
        Sift(R,i,n);
    printf("初始堆: ");DispHeap(R,1,n);printf("\n");
    for (i=n; i>=2; i--) {
        printf("交换%d与%d,输出%d\n",R[i].key,R[1].key,R[1].key);
        temp=R[1];
        R[1]=R[i];
        R[i]=temp;
        Sift(R,1,i-1);
        printf("筛选调整得到堆:");
        DispHeap(R,1,i-1);
        printf("\n");
    }
     
}

 

7、归并排序

 

 

void Merge(RecType *R,int low,int m,int high)
{//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]
    int i=low,j=m+1,p=0; //置初始值
    RecType *R1; //R1是局部向量
    R1=(RecType *)malloc((high-low+1)*sizeof(RecType));
    if(!R1)return; //申请空间失败
    while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上
        R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];
    while(i<=m) //若第1个子文件非空,则复制剩余记录到R1中
        R1[p++]=R[i++];
    while(j<=high) //若第2个子文件非空,则复制剩余记录到R1中
        R1[p++]=R[j++];
    for(p=0,i=low;i<=high;p++,i++)
        R[i]=R1[p];//归并完成后将结果复制回R[low..high]
}

void MergeSort(RecType R[],int low,int high)
{//用分治法对R[low..high]进行二路归并排序
    int mid;
    if(low<high){//区间长度大于1
        mid=(low+high)/2;//分解
        MergeSort(R,low,mid);//递归地对R[low..mid]排序
        MergeSort(R,mid+1,high); //递归地对R[mid+1..high]排序
        Merge(R,low,mid,high);//组合,将两个有序区归并为一个有序区
    }
}
 
分享到:
评论

相关推荐

    SNS单模无芯光纤仿真与传感器结构特性分析——基于Rsoft beamprop模块

    内容概要:本文主要探讨了SNS单模无芯光纤的仿真分析及其在通信和传感领域的应用潜力。首先介绍了模间干涉仿真的重要性,利用Rsoft beamprop模块模拟不同模式光在光纤中的传播情况,进而分析光纤的传输性能和模式特性。接着讨论了光纤传输特性的仿真,包括损耗、色散和模式耦合等参数的评估。随后,文章分析了光纤的结构特性,如折射率分布、包层和纤芯直径对性能的影响,并探讨了镀膜技术对光纤性能的提升作用。最后,进行了变形仿真分析,研究外部因素导致的光纤变形对其性能的影响。通过这些分析,为优化光纤设计提供了理论依据。 适合人群:从事光纤通信、光学工程及相关领域的研究人员和技术人员。 使用场景及目标:适用于需要深入了解SNS单模无芯光纤特性和优化设计的研究项目,旨在提高光纤性能并拓展其应用场景。 其他说明:本文不仅提供了详细的仿真方法和技术细节,还对未来的发展方向进行了展望,强调了SNS单模无芯光纤在未来通信和传感领域的重要地位。

    发那科USM通讯程序socket-rece

    发那科USM通讯程序socket-set

    嵌入式八股文面试题库资料知识宝典-WIFI.zip

    嵌入式八股文面试题库资料知识宝典-WIFI.zip

    JS+HTML源码与image

    源码与image

    物流行业车辆路径优化:基于遗传算法和其他优化算法的MATLAB实现及应用

    内容概要:本文详细探讨了物流行业中路径规划与车辆路径优化(VRP)的问题,特别是针对冷链物流、带时间窗的车辆路径优化(VRPTW)、考虑充电桩的车辆路径优化(EVRP)以及多配送中心情况下的路径优化。文中不仅介绍了遗传算法、蚁群算法、粒子群算法等多种优化算法的理论背景,还提供了完整的MATLAB代码及注释,帮助读者理解这些算法的具体实现。此外,文章还讨论了如何通过MATLAB处理大量数据和复杂计算,以得出最优的路径方案。 适合人群:从事物流行业的研究人员和技术人员,尤其是对路径优化感兴趣的开发者和工程师。 使用场景及目标:适用于需要优化车辆路径的企业和个人,旨在提高配送效率、降低成本、确保按时交付货物。通过学习本文提供的算法和代码,读者可以在实际工作中应用这些优化方法,提升物流系统的性能。 其他说明:为了更好地理解和应用这些算法,建议读者参考相关文献和教程进行深入学习。同时,实际应用中还需根据具体情况进行参数调整和优化。

    嵌入式八股文面试题库资料知识宝典-C and C++ normal interview_8.doc.zip

    嵌入式八股文面试题库资料知识宝典-C and C++ normal interview_8.doc.zip

    基于灰狼优化算法的城市路径规划Matlab实现——解决TSP问题

    内容概要:本文介绍了基于灰狼优化算法(GWO)的城市路径规划优化问题(TSP),并通过Matlab实现了该算法。文章详细解释了GWO算法的工作原理,包括寻找猎物、围捕猎物和攻击猎物三个阶段,并提供了具体的代码示例。通过不断迭代优化路径,最终得到最优的城市路径规划方案。与传统TSP求解方法相比,GWO算法具有更好的全局搜索能力和较快的收敛速度,适用于复杂的城市环境。尽管如此,算法在面对大量城市节点时仍面临运算时间和参数设置的挑战。 适合人群:对路径规划、优化算法感兴趣的科研人员、学生以及从事交通规划的专业人士。 使用场景及目标:①研究和开发高效的路径规划算法;②优化城市交通系统,提升出行效率;③探索人工智能在交通领域的应用。 其他说明:文中提到的代码可以作为学习和研究的基础,但实际应用中需要根据具体情况调整算法参数和优化策略。

    嵌入式八股文面试题库资料知识宝典-Intel3.zip

    嵌入式八股文面试题库资料知识宝典-Intel3.zip

    嵌入式八股文面试题库资料知识宝典-2019京东C++.zip

    嵌入式八股文面试题库资料知识宝典-2019京东C++.zip

    嵌入式八股文面试题库资料知识宝典-北京光桥科技有限公司面试题.zip

    嵌入式八股文面试题库资料知识宝典-北京光桥科技有限公司面试题.zip

    物理学领域十字形声子晶体的能带与传输特性研究及应用

    内容概要:本文详细探讨了十字形声子晶体的能带结构和传输特性。首先介绍了声子晶体作为新型周期性结构在物理学和工程学中的重要地位,特别是十字形声子晶体的独特结构特点。接着从散射体的形状、大小、排列周期等方面分析了其对能带结构的影响,并通过理论计算和仿真获得了能带图。随后讨论了十字形声子晶体的传输特性,即它对声波的调控能力,包括传播速度、模式和能量分布的变化。最后通过大量实验和仿真验证了理论分析的正确性,并得出结论指出散射体的材料、形状和排列方式对其性能有重大影响。 适合人群:从事物理学、材料科学、声学等相关领域的研究人员和技术人员。 使用场景及目标:适用于希望深入了解声子晶体尤其是十字形声子晶体能带与传输特性的科研工作者,旨在为相关领域的创新和发展提供理论支持和技术指导。 其他说明:文中还对未来的研究方向进行了展望,强调了声子晶体在未来多个领域的潜在应用价值。

    嵌入式系统开发_USB主机控制器_Arduino兼容开源硬件_基于Mega32U4和MAX3421E芯片的USB设备扩展开发板_支持多种USB外设接入与控制的通用型嵌入式开发平台_.zip

    嵌入式系统开发_USB主机控制器_Arduino兼容开源硬件_基于Mega32U4和MAX3421E芯片的USB设备扩展开发板_支持多种USB外设接入与控制的通用型嵌入式开发平台_

    e2b8a-main.zip

    e2b8a-main.zip

    少儿编程scratch项目源代码文件案例素材-火柴人跑酷(2).zip

    少儿编程scratch项目源代码文件案例素材-火柴人跑酷(2).zip

    【HarmonyOS分布式技术】远程启动子系统详解:跨设备无缝启动与智能协同的应用场景及未来展望

    内容概要:本文详细介绍了HarmonyOS分布式远程启动子系统,该系统作为HarmonyOS的重要组成部分,旨在打破设备间的界限,实现跨设备无缝启动、智能设备选择和数据同步与连续性等功能。通过分布式软总线和分布式数据管理技术,它能够快速、稳定地实现设备间的通信和数据同步,为用户提供便捷的操作体验。文章还探讨了该系统在智能家居、智能办公和教育等领域的应用场景,展示了其在提升效率和用户体验方面的巨大潜力。最后,文章展望了该系统的未来发展,强调其在技术优化和应用场景拓展上的无限可能性。 适合人群:对HarmonyOS及其分布式技术感兴趣的用户、开发者和行业从业者。 使用场景及目标:①理解HarmonyOS分布式远程启动子系统的工作原理和技术细节;②探索该系统在智能家居、智能办公和教育等领域的具体应用场景;③了解该系统为开发者提供的开发优势和实践要点。 其他说明:本文不仅介绍了HarmonyOS分布式远程启动子系统的核心技术和应用场景,还展望了其未来的发展方向。通过阅读本文,用户可以全面了解该系统如何通过技术创新提升设备间的协同能力和用户体验,为智能生活带来新的变革。

    嵌入式八股文面试题库资料知识宝典-C and C++ normal interview_1.zip

    嵌入式八股文面试题库资料知识宝典-C and C++ normal interview_1.zip

    少儿编程scratch项目源代码文件案例素材-激光反弹.zip

    少儿编程scratch项目源代码文件案例素材-激光反弹.zip

    COMSOL相控阵检测技术在有机玻璃斜楔中检测工件内部缺陷的应用研究

    内容概要:本文详细介绍了COMSOL相控阵检测技术在有机玻璃斜楔上放置16阵元进行工件内部缺陷检测的方法。首先阐述了相控阵检测技术的基本原理,特别是通过控制各阵元的激发时间和相位来实现声波的聚焦和扫描。接着,重点解析了横孔缺陷的反射接收波,解释了波的折射现象及其背后的物理原因。最后,通过实例展示了COMSOL模拟声波传播过程的成功应用,验证了该技术的有效性和准确性。 适合人群:从事固体力学、无损检测领域的研究人员和技术人员,尤其是对相控阵检测技术和COMSOL仿真感兴趣的读者。 使用场景及目标:适用于需要精确检测工件内部缺陷的研究和工业应用场景,旨在提高检测精度和效率,确保产品质量和安全。 其他说明:文中提到的声速匹配现象有助于理解波在不同介质间的传播特性,这对优化检测参数设置有重要意义。

    少儿编程scratch项目源代码文件案例素材-极速奔跑者.zip

    少儿编程scratch项目源代码文件案例素材-极速奔跑者.zip

    嵌入式八股文面试题库资料知识宝典-微软_interview.zip

    嵌入式八股文面试题库资料知识宝典-微软_interview.zip

Global site tag (gtag.js) - Google Analytics