1. Toy模板网首页
  2. > Toy博客

头歌数据结构实训参考---十大经典排序算法

10月前 作者：HUTAC 分类：Toy博客 阅读(63) 违法举报

这篇具有很好参考价值的文章主要介绍了头歌数据结构实训参考---十大经典排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

可通过 目录 快速查阅对应排序算法文章来源地址https://www.toymoban.com/news/detail-762373.html

第1关 冒泡排序


#include "sort_.h"

void print_array(int *arr, int n)
// 打印数组
{
    if(n==0){
        printf("ERROR: Array length is ZERO\n");
        return;
    }
    printf("%d", arr[0]);
    for (int i=1; i<n; i++) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}



void sort_array(int *arr, int n)
//  编程实现《冒泡排序算法》：将乱序序列arr转化为升序序列
//  函数参数：乱序整数数组arr 数组长度
//  要求输出：调用print_array(int *arr, int n)输出前三次冒泡操作后的序列，以及最终的升序序列
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    for(int i=0;i<n;i++)
    {
    for(int j=0;j<n-1;j++)
    {
     if(arr[j]>arr[j+1])
     {
         int temp=arr[j];
         arr[j]=arr[j+1];
         arr[j+1]=temp;
     }
    }
    if(i<3)
    print_array(arr,n);
    }
    print_array(arr,n);

    
    /********** End **********/
}

第2关 选择排序


#include "sort_.h"

void print_array(int *arr, int n)
// 打印数组
{
    if(n==0){
        printf("ERROR: Array length is ZERO\n");
        return;
    }
    printf("%d", arr[0]);
    for (int i=1; i<n; i++) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}

void sort_array(int *arr, int n)
//  编程实现《选择排序算法》：将乱序序列arr转化为升序序列
//  函数参数：乱序整数数组（无重复元素） 数组长度
//  要求输出：调用print_array(int *arr, int n)输出前三次选择操作后的序列，以及最终的升序序列
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int index,min;
    for(int i=0;i<n-1;i++)
    {
        min=arr[i];
        index=i;
    for(int j=i+1;j<n;j++)
    {
        if(min>arr[j])
        {
            min=arr[j];
            index=j;
        }
    }
    arr[index]=arr[i];
    arr[i]=min;
    if(i<3)
    print_array(arr,n);
    }
    print_array(arr,n);

    
    /********** End **********/
}

第3关 插入排序



#include "sort_.h"

void print_array(int *arr, int n)
// 打印数组
{
    if(n==0){
        printf("ERROR: Array length is ZERO\n");
        return;
    }
    printf("%d", arr[0]);
    for (int i=1; i<n; i++) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}

void sort_array(int *arr, int n)
//  编程实现《插入排序算法》：将乱序序列arr转化为升序序列
//  函数参数：乱序整数数组（无重复元素） 数组长度
//  要求输出：调用print_array(int *arr, int n)输出前三次插入操作后的序列，以及最终的升序序列
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int temp,index;
    for(int i=1;i<n;i++)
    {
        temp=arr[i];
        index=i;
        for(int j=i-1;j>=0;j--)
        {
            if(arr[j]>temp)
			{
				arr[index--]=arr[j];
				arr[j]=temp;
			}
        }
    if(i<4)
    print_array(arr,n);
    }
    print_array(arr,n);
    
	
    
    /********** End **********/
}

第4关 希尔排序


#include "sort_.h"

void print_array(int *arr, int n)
// 打印数组
{
    if(n==0){
        printf("ERROR: Array length is ZERO\n");
        return;
    }
    printf("%d", arr[0]);
    for (int i=1; i<n; i++) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}

void sort_array(int *arr, int n)
//  编程实现《希尔排序算法》：将乱序序列arr转化为升序序列
//  函数参数：乱序整数数组 数组长度
//  要求输出：调用print_array(int *arr, int n)输出三遍增量排序操作后的序列，以及最终的升序序列
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int sort_array[]={5,2,1};
    int temp,index,sep;
    for(int k=0;k<3;k++)
    {
        sep=sort_array[k];
    for(int i=sep;i<n;i++)
    {
        temp=arr[i];
        index=i;
        for(int j=i-sep;j>=0;j-=sep)
        {
            if(arr[j]>temp)
			{
				arr[index]=arr[j];
                index-=sep;
				arr[j]=temp;
			}
        }
    }
    print_array(arr,n);
    }
    print_array(arr,n);
    
    /********** End **********/
}

第5关 归并排序


#include "sort_.h"
int cmp(const void*a,const void*b)
{
    return (*(int*)a-*(int*)b);
}
void print_array(int *arr, int n)
// 打印数组
{
    if(n==0){
        printf("ERROR: Array length is ZERO\n");
        return;
    }
    printf("%d", arr[0]);
    for (int i=1; i<n; i++) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}

int* merge_array(int *arr1, int n1, int* arr2, int n2)
//  编程实现两个有序数组arr1和arr2合并
//  函数参数：有序数组arr1 数组arr1长度 有序数组arr2 数组arr2长度
//  函数返回值：返回从小到大排序后的合并数组
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int *arr3;
    arr3=(int*)malloc(sizeof(int)*(n1+n2));
    int a1=0,a2=0,a3=0;
    while(a1<n1&&a2<n2)
    {
        if(arr1[a1]<=arr2[a2])
        arr3[a3++]=arr1[a1++];
        else
        arr3[a3++]=arr2[a2++];
    }
    while(a1<n1)
    arr3[a3++]=arr1[a1++];
    while(a2<n2)
    arr3[a3++]=arr2[a2++];
    return arr3;
    /********** End **********/
}
int* merge_sort(int *arr, int n)
//  基于merge_array函数编程实现归并排序：自上而下的递归方法
//  函数参数：有序数组arr 数组arr长度
//  函数返回值：返回从小到大排序后的数组
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int *rarr=&arr[n/2];
    int lr=n-n/2;
    qsort(arr,n/2,sizeof(int),cmp);
    qsort(rarr,lr,sizeof(int),cmp);
    merge_array(arr,n/2, rarr, lr);
    /********** End **********/
}

第6关 快速排序


#include "sort_.h"

void print_array(int *arr, int n)
// 打印数组
{
    if(n==0){
        printf("ERROR: Array length is ZERO\n");
        return;
    }
    printf("%d", arr[0]);
    for (int i=1; i<n; i++) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}

int partition_array(int *arr ,int l,int r)
// 编程实现arr[l, r]分区：选定一个基准，左边比基准小，右边比基准大
// 返回基准所处位置
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int temp = arr[l];
	while(l<r)
	{        
		while((l<r)&&arr[r]>=temp)
			r--;
		arr[l] = arr[r];
		while((l<r)&&arr[l]<=temp)
			l++;
		arr[r] = arr[l];

    }
    arr[l] = temp;
    return l;
    /********** End **********/
}

int* quick_sort(int *arr, int l, int r)
//  基于partition_array函数编程实现快速排序：自上而下的递归方法
//  函数参数：有序数组arr 初始l=0，r=n-1
//  函数返回值：返回从小到大排序后的数组
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
     int pos = partition_array(arr,l,r);

    if(l<r)
    {
        if(l<pos-1)
			arr = quick_sort(arr,l,pos-1);
        if(pos+1<r)
            arr = quick_sort(arr,pos+1,r);
    }
    return arr;

    /********** End **********/
}

第7关 堆排序


#include "sort_.h"

void print_array(int *arr, int n)
// 打印数组
{
    if(n==0){
        printf("ERROR: Array length is ZERO\n");
        return;
    }
    printf("%d", arr[0]);
    for (int i=1; i<n; i++) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}

void adjustHeap(int *arr, int param1, int j)
// 编程实现堆的调整
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int temp=0;
    if(j<param1)
	{
		int max=j;
		int s1=2*j+1;
		int s2=2*j+2;
		if(arr[s1]>arr[max]&&s1<param1)
			max=s1;
		if(arr[s2]>arr[max]&&s2<param1)
			max=s2;
		
		if(max!=j)
		{
			
            temp = arr[max];
            arr[max] = arr[j];
            arr[j]   = temp; 
			
            adjustHeap(arr,param1,max);		
		}
	}
    /********** End **********/
}

int* heap_sort(int *arr, int n)
//  基于adjustHeap函数编程实现堆排序
//  函数参数：无序数组arr 数组长度n
//  函数返回值：返回从小到大排序后的数组
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int i=0,temp=0;
    int last=n-1;				
	int parent=(last-1)/2;		
	for(int i=parent;i>=0;i--)	
	{
		adjustHeap(arr,n,i);		
	}
    for(int i=n-1;i>=0;i--)
	{

        temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;	
		adjustHeap(arr,i,0);		
	}
    return arr;

    /********** End **********/
}

 第8关 计数排序



#include "sort_.h"

void print_array(int *arr, int n)
// 打印数组
{
    if(n==0){
        printf("ERROR: Array length is ZERO\n");
        return;
    }
    printf("%d", arr[0]);
    for (int i=1; i<n; i++) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}


void sort_array(int *arr, int n)
//  编程实现《计数排序算法》
//  函数参数：乱序整数数组 数组长度
//  要求输出：调用print_array(int *arr, int n)输出：
//  每一行一个元素及其个数（升序），如 1 1
//  以及最终的升序序列
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int max=arr[0];
    int min=arr[0];
    for(int i=0;i<n;i++)
    {
        if(arr[i]>max)
        max=arr[i];
        if(arr[i]<min)
        min=arr[i];
    }
    int num[1000]={0};
    for(int i=0;i<n;i++)
    num[arr[i]]++;
    int index=-1;
    for(int j=min;j<=max;j++)
    {
        if(num[j]!=0)
        printf("%d %d\n",j,num[j]);
        int temp = num[j];
        while(num[j]!=0) 
        {
            arr[++index] = j;
            num[j]--;
        }
    }
    print_array(arr,n);

    
    /********** End **********/
}

第9关 桶排序



#include "sort_.h"

void print_array(int *arr, int n)
// 打印数组
{
    if(n==0){
        printf("ERROR: Array length is ZERO\n");
        return;
    }
    printf("%d", arr[0]);
    for (int i=1; i<n; i++) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}


int* sort_array(int *arr, int n)
//  编程实现《桶排序算法》
//  函数参数：乱序整数数组 数组长度
//  函数返回值：返回从小到大排序后的数组
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int max=arr[0];
    int min=arr[0];
    for(int i=0;i<n;i++)
    {
        if(arr[i]>max)
        max=arr[i];
        if(arr[i]<min)
        min=arr[i];
    }
    int num[100]={0};
    for(int i=0;i<n;i++)
    num[arr[i]]++;
    int index=-1;
    for(int j=min;j<=max;j++)
    {
        if(num[j]!=0)
        int temp = num[j];
        while(num[j]!=0) 
        {
            arr[++index] = j;
            num[j]--;
        }
    }
    return arr;
    /********** End **********/
}

第10关 基数排序



#include "sort_.h"

void print_array(int *arr, int n)
// 打印数组
{
    if(n==0){
        printf("ERROR: Array length is ZERO\n");
        return;
    }
    printf("%d", arr[0]);
    for (int i=1; i<n; i++) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}

int bucket[10]={0};
int temp[100]={0};
int* sort_array(int *arr, int n)
//  编程实现《基数排序算法》
//  函数参数：乱序整数数组 数组长度
//  函数返回值：返回从小到大排序后的数组
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int max=arr[0];
    for(int i=0;i<n;i++)
    if(arr[i]>=max)
    max=arr[i];
    int d=1;   
	while(max>=10)  
	{
		max/=10;
		d++;
	}
    int i,j,k;
	int radix = 1;
	for(i=1;i<=d;i++)   
	{
	    for(j=0;j<10;j++)  
		bucket[j]=0;
		for(j=0;j<n;j++)    
		{
			k=(arr[j]/radix)%10;
			bucket[k]++;
		}
	    for(j = 1; j < 10; j++)
        bucket[j] += bucket[j - 1] ; 
		for(j = n-1; j>=0; j--) 
        {
            k = (arr[j] / radix) % 10;
            temp[bucket[k] - 1] = arr[j];
            bucket[k]--;
        }
        for(j = 0; j < n; j++) 
        arr[j] = temp[j];
        radix = radix * 10;  
	} 
    return arr;

    
    
    /********** End **********/
}

到了这里，关于头歌数据结构实训参考---十大经典排序算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】十大经典排序算法-快速排序

    【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客： www.hellocode.top 🏰 Java知识导航： Java-Navigate 🔥 CSDN： HelloCode. 🌞 知乎 ：HelloCode 🌴 掘金 ：HelloCode ⚡如有问题，欢迎指正，一起学习~~ 快速排序（Quick Sort）是一种高效的排序算法，是对冒泡排序的优化。它采用分治法（Divide and Conquer）的思想，将待排序序列

    2024年02月13日
    浏览(63)
  • 【数据结构与算法】十大经典排序算法-希尔排序

    【数据结构与算法】十大经典排序算法-希尔排序

    🌟 个人博客： www.hellocode.top 🏰 Java知识导航： Java-Navigate 🔥 CSDN： HelloCode. 🌞 知乎 ：HelloCode 🌴 掘金 ：HelloCode ⚡如有问题，欢迎指正，一起学习~~ 希尔排序是一种插入排序的改进版本，旨在解决插入排序在处理大规模数据时的效率问题。通过将数组分为多个子序列并对

    2024年02月12日
    浏览(79)

  • 获取头歌实训参考答案（EduCoder）

    头歌EduCoder平台实训答案在此，里面搜集了一些答案，可以查查有没有想看的。 https://edaser.github.io/ 一定 不要直接复制答案 ，建议还是自己做，实在不会做的，参考看完后要独立完成。 在这里可以查询一些实训的答案，后台的数据库记录了几百个实训关卡的答案，实现的方

    2024年02月11日
    浏览(41)

  • 【头歌educoder】离散数学实训参考-第一章-集合

    目录 1. 集合及其基本运算的实现 第一关：set简单应用 第二关：《仲夏夜之梦》中的回文单词对 第三关：求幂集  第四关：计算n个集合的笛卡尔乘积 2. 自然数系统 第一关：NaturalNumber的输出  第二关：NaturalNumber的加法 第三关：NaturalNumber的乘法 第四关：将NaturalNumber转换为阿

    2024年02月09日
    浏览(48)

  • 【头歌educoder】离散数学实训参考-第二章-关系-part1-关系基础

    目录  第一关：求给定集合的对角线关系(Diagonal Relation)  第二关：关系的合成  第三关：关系的幂运算  第四关：关系的并运算  第五关：转换成关系矩阵  第六关：自反关系的判断  第七关：反自反关系的判断  第八关：对称关系的判断  第九关：非对称关系的判断  第十

    2024年02月07日
    浏览(43)
  • 《数据结构与算法》之十大基础排序算法

    《数据结构与算法》之十大基础排序算法

    冒泡排序是一种交换排序，它的思路就是在待排序的数据中，两两比较相邻元素的大小，看是否满足大小顺序的要求，如果满足则不动，如果不满足则让它们互换。 然后继续与下一个相邻元素的比较，一直到一次遍历完成。一次遍历的过程就被成为一次冒泡，一次冒泡的结束

    2024年02月05日
    浏览(98)
  • 【头歌】数据结构-队列的应用

    【头歌】数据结构-队列的应用

      第1关：循环队列 任务描述 本关任务：编写一个循环队列，实现入队、出队操作，判断队空、队满等特殊情况。 相关知识 为了完成本关任务，你需要掌握：1.循环队列定义，2.入队、出队的定义，3.队空、队满的情况。 循环队列定义 循环队列将数组存储区看成是一个首尾相

    2024年02月08日
    浏览(49)

  • 头歌JAVA数据结构答案

    一、Java数据结构-循环链表的设计与实现 第1关 单循环链表的实现—链表的添加、遍历 第2关 单循环链表的实现—链表的删除 第3关 双向循环链表的实现—链表的插入 第4关：双向循环链表的实现—链表的删除 二、Java数据结构-线性表的设计与实现 第1关：顺序表的实现之增删

    2024年02月08日
    浏览(46)
  • 数据结构：一篇拿捏十大排序(超详细版)

    数据结构：一篇拿捏十大排序(超详细版)

    排序： 所谓排序，就是使一串记录，按照其中的某个或某些的大小，递增或递减的排列起来的操作。 稳定性： 假定在待排序的记录序列中，存在多个具有相同的的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前， 而

    2024年02月08日
    浏览(52)
  • 数据结构头歌实验梳理

    数据结构头歌实验梳理

    PS：该代码块表明了链接存储线性表所有常见相关用法及性质。对于初学者需要分成一小块一小块食用 特别说明： “当前位置”：当前位置由curr指针给出，当前位置的前一个位置由pre指针给出，当前位置的编号由position给出。后面将定义的若干操作与当前位置有关，例如：在

    2023年04月12日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包