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

• 算法结构

可通过 目录 快速查阅对应排序算法

第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;jarr[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;jarr[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=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=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=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(jarr[max]&&s1arr[max]&&s2=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;imax)
        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;imax)
        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=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 =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 **********/
}

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/6c738743e9.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐