欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构:常用的内部排序算法

程序员文章站 2022-05-26 11:33:08
...

目录

 

问题:

正文:

代码: 


问题:

实验学时:2学时

实验类型综合型

 

背景知识各种排序方法

 

目的要求:

    1.掌握常见的内部排序算法的思想及其适用条件。

    2.掌握常见的内部排序算法的程序实现。

 

实验内容:

1.任务:设计一个内部排序算法模拟系统,利用该系统实现常用的7种排序算法,并测试各种排序算法的性能。

2.内容:通过一个简单的菜单,分别实现下列排序要求,采用几组不同数据测试各排序算法的性能(比较次数和移动次数)及稳定性。

  1. 实现简单选择排序、直接插入排序和冒泡排序;
  2. 实现折半插入排序;
  3. 实现希尔排序算法;
  4. 实现快速排序算法(递归和非递归);
  5. 实现堆排序算法。

 

实验说明:

    1.输入和输出:

(1)输入形式:根据菜单提示选择排序算法,输入一组带排序数据。

(2)输出形式:输出排序结果(体现排序过程),及排序过程中数据的比较次数和移动次数,判断排序算法的稳定性。

2.实验要求:

    1. 实现一个简单的交互式界面,包括系统菜单、清晰的输入提示等。
    2. 要输出每一趟排序的结果。
    3. 能够上机编辑、调试出完整的程序。

3.数据类型定义

        #define MAXSIZE 100 /*参加排序元素的最大个数*/

        typedef  int  KeyType;

        typedef struct {

            KeyType  key;

            InfoType  otherinfo;  // 其他字段(自行设计)

        }RedType;

        typedef struct

        {

            RedType  r[MAXSIZE+1];

            int        length; /*参加排序元素的实际个数*/

        }SqList;

 

注意问题:

1.在RedType中增加一个数据项验证各种排序算法的稳定性。

2.注意理解各种算法的思想、了解算法的适用情况及时间复杂度,能够根据实际情况选择合适的排序方法

正文:

这是数据结构的最后一个实验啦,怀恋啊,就完啦

这次的作业代码,实验报告的代码可以直接用,虽然这次这个写啦感觉多此一举,但是还是写一下吧有始有终

我就改了一下读取文件,要不然一个一个输入太麻烦啦

这是我文件里的数,

数据结构:常用的内部排序算法

数据结构:常用的内部排序算法

代码: 

#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100 /*参加排序元素的最大个数*/

using namespace std;

FILE *fp;
char path[1000];
int find_n()
{
    int n;
    if((fp = fopen(path,"r"))==NULL){
        printf("失败了哦!");
    }
    fscanf(fp,"%d",&n);
    return n;

}

/******************冒泡排序********************/
void maopao()
{
    int nums[MAXSIZE];
    int i , j , n , temp;
    int comnum = 0 , movnum = 0;
    int num = 1;

    printf("您已进入冒泡排序\n");
    printf("请输入排序序列长度:");
    //scanf("%d",&n);
    n = find_n();
    printf("请输入排序序列:");
    for(i=0 ; i<n ; i++)
    {
        fscanf(fp,"%d",&nums[i]);
    }
        //fscanf(fp,"%d",&num[i]);
        //scanf("%d",&nums[i]);

    for(i=0 ; i<n-1 ; i++)
    {
        for(j=0 ; j<n-i-1 ; j++)
        {
            comnum++;
            if(nums[j] > nums[j+1])
            {

                temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
                movnum++;
            }
        }

        printf("第%d趟排序结果:",num++);
        for(j=0 ; j<n ; j++)
        {
            printf("%d ",nums[j]);
        }
        printf("\n");
    }
    printf("排序过程比较次数:%d\n排序过程移动次数:%d\n",comnum,movnum);
    printf("\n");

    return ;
}
/************************************************/

/*****************折半插入排序*******************/
void zheban()
{
    int nums[MAXSIZE];
	int i , j , n , temp;
	int low , high , middle;
	int comnum = 0 , movnum = 0;
	int num = 1;

	printf("您已进入折半插入排序\n");
	printf("请输入排序序列长度:");
     n = find_n();
    printf("请输入排序序列:");
    for(i=0 ; i<n ; i++)
    {
        fscanf(fp,"%d",&nums[i]);
    }

	for(i=1 ; i<n ; i++)
	{
		low = 0; //有序数组的开头下标
		high = i-1; //有序数组的末尾下标
		temp = nums[i]; //要被插入的数
		middle = 0;
		//查找要被插入的下标
		while(low <= high)
		{
			middle = (low + high) / 2;
			if(temp < nums[middle])
			{
				high = middle-1;
			}
			else
			{
				low = middle+1;
			}
			comnum++;
		}
		//所有数右移,移完之后插入目标数
		for(j=i ; j>low ; j--)
		{
			nums[j] = nums[j-1];
		}
		//交换nums[i]与nums[low]的位置
		nums[low] = temp;
		movnum++;

		printf("第%d趟排序结果:",num++);
		for(j=0 ; j<n ; j++)
        {
            printf("%d ",nums[j]);
        }
        printf("\n");
	}
	printf("排序过程比较次数:%d\n排序过程移动次数:%d\n",comnum,movnum);
	printf("\n");

    return ;
}
/************************************************/

/*******************希尔排序*********************/
void shell()
{
    int i , j , k , n , dk , temp;
    int nums[MAXSIZE];
    int comnum = 0 , movnum = 0;
    int num = 1;

    printf("您已进入希尔排序\n");
    printf("请输入排序序列长度:");
    n = find_n();
    printf("请输入排序序列:");
    for(i=0 ; i<n ; i++)
    {
        fscanf(fp,"%d",&nums[i]);
    }
    for(dk=n/2; dk>0; dk=dk/2)
    {
		for(i=0; i<dk; i++)
		{
			for(j=i+dk; j<n; j=j+dk)
			{	//单独一次的插入排序
				if(nums[j] < nums[j-dk])
				{
					temp = nums[j];	//哨兵
					k = j - dk;
					while(k>=0 && nums[k]>temp)
					{
						nums[k + dk] = nums[k];
						k = k - dk;
					}
					nums[k + dk] = temp;
					movnum++;
				}
				comnum++;
			}
		}
		printf("第%d趟排序结果:",num++);
        for(i=0 ; i<n ; i++)
        {
            printf("%d ",nums[i]);
        }
        printf("\n");
	}
    printf("排序过程比较次数:%d\n排序过程移动次数:%d\n",comnum,movnum);
    printf("\n");

    return ;
}
/************************************************/

/*******************快速排序*********************/
int CN = 0;
int MN = 0;
int T = 1;
void Fswap(int nums[], int i, int j)
{
	int temp;
	temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
	MN++;
}

int partition(int nums[], int low, int high,int n)
{
    int i;
	int pivotkey;
	pivotkey = nums[low];
	while (low < high)//以pivoekey为轴,将大于它的放在后边,小于它的放在前面
	{
		while (low < high && nums[high] >= pivotkey)//条件判断 low < high
		{
			high--;
			CN++;
		}
		Fswap(nums, low, high);
		while (low < high && nums[low] <= pivotkey)
        {
			low++;
			CN++;
        }
		Fswap(nums, low, high);

		printf("第%d趟排序结果:",T++);
		for(i=0 ; i<n ; i++)
        {
            printf("%d ",nums[i]);
        }
        printf("\n");
	}
	return low;//返回枢轴所在位置
}

void quickSort(int nums[], int low, int high,int n)
{
	int pivot;
	if (low < high)
	{
		pivot = partition(nums, low, high, n);//将nums[]一分为二

		quickSort(nums, low, pivot - 1, n);//对低子表递归排序
		quickSort(nums, pivot + 1, high, n);//对高子表递归排序
	}
}

void kuaipai()
{
    int i , n;
	int nums[MAXSIZE];

	printf("您已进入快速排序\n");
    printf("请输入排序序列长度:");
    //scanf("%d",&n);
    n = find_n();
    //printf("请输入排序序列:");
    CN = 0;
    MN = 0;
    T = 1;
    printf("请输入排序序列:");
    for(i=0 ; i<n ; i++)
    {
        fscanf(fp,"%d",&nums[i]);
    }

	quickSort(nums, 0, n-1, n);

	printf("排序过程比较次数:%d\n排序过程移动次数:%d\n",CN,MN);
	printf("\n");

    return ;
}
/************************************************/

/********************堆排序**********************/
int HCN = 0;
int HMN = 0;
int H = 1;
void HeapAdjust(int nums[], int s, int n)
{
    int i , j;
    int temp;

    for(i=s ; 2*i+1<n ; i=j)
    {
        j = 2*i + 1;
        if((j<n-1)&&(nums[j]<nums[j+1]))
        {
            j++;
            HCN++;
        }
        if(nums[i] < nums[j])
        {
            temp = nums[i];
			nums[i] = nums[j];
			nums[j] = temp;
			HCN++;
			HMN++;
        }
        else
            break;
    }
}

void HeapSort(int nums[], int n)
{
    int i , j;
    int temp;

    for(i=n/2-1 ; i>=0 ; i--)
    {
        HeapAdjust(nums, i, n);
        printf("第%d趟排序结果:",H++);
		for(j=0 ; j<n ; j++)
        {
            printf("%d ",nums[j]);
        }
        printf("\n");
    }
    for(i=n-1 ; i>0 ; i--)
    {
        temp = nums[i];
        nums[i] = nums[0];
        nums[0] = temp;
        HMN++;

        HeapAdjust(nums, 0, i);
        printf("第%d趟排序结果:",H++);
		for(j=0 ; j<n ; j++)
        {
            printf("%d ",nums[j]);
        }
        printf("\n");
    }
}

void duipai()
{
    int i , n;
    int nums[MAXSIZE];

    printf("您已进入堆排序\n");
    printf("请输入排序序列长度:");
    //scanf("%d",&n);
    n = find_n();
    printf("请输入排序序列:");
    HMN = 0;
    HCN = 0;
    H = 1;
     //n = find_n();
    //printf("请输入排序序列:");
    for(i=0 ; i<n ; i++)
    {
        fscanf(fp,"%d",&nums[i]);
    }
	/*for (i=0; i<n; i++)
	{
		scanf("%d",&nums[i]);
	}
*/
	HeapSort(nums, n);
	printf("排序过程比较次数:%d\n排序过程移动次数:%d\n",HCN,HMN);
	printf("\n");

    return ;
}
/************************************************/

/*****************直接插入排序*******************/
void zhicha()
{
    int nums[MAXSIZE];
    int i , j , n;
    int temp;
    int comnum = 0 , movnum = 0;
    int num = 1;

    printf("您已进入直接插入排序\n");
    printf("请输入排序序列长度:");
     n = find_n();
    printf("请输入排序序列:");
    for(i=0 ; i<n ; i++)
    {
        fscanf(fp,"%d",&nums[i]);
    }

    for(i=1 ; i<n ; i++)
    {
        if(nums[i] < nums[i-1])
        {
            temp = nums[i];
            for(j=i-1 ; j>=0 ; j--)
            {
                if(temp < nums[j])
                {
                    nums[j+1] = nums[j];
                    comnum++;
                }
                else
                {
                    break;
                    comnum++;
                }
            }
            nums[j + 1] = temp;
            movnum++;
        }
        else
        {
            comnum++;
            continue;
        }

        printf("第%d趟排序结果:",num++);
        for(j=0 ; j<n ; j++)
        {
            printf("%d ", nums[j]);
        }
        printf("\n");
    }
    printf("排序过程比较次数:%d\n排序过程移动次数:%d\n",comnum,movnum);
    printf("\n");
}
/************************************************/

/*****************简单选择排序*******************/
void jiandan()
{
    int nums[MAXSIZE];
    int i , j , n;
    int temp , t;
    int comnum = 0 , movnum = 0;
    int num = 1;

    printf("您已进入简单选择排序\n");
    printf("请输入排序序列长度:");
    n = find_n();
    printf("请输入排序序列:");
    for(i=0 ; i<n ; i++)
    {
        fscanf(fp,"%d",&nums[i]);
    }

    for(i=0 ; i<n ; i++)
    {
        temp = nums[i];
        t = i;
        for(j=i+1 ; j<n ; j++)
        {
            if(nums[j] < temp)
            {
                temp = nums[j];
                t = j;
            }
            comnum++;
        }
        temp = nums[i];
        nums[i] = nums[t];
        nums[t] = temp;
        movnum++;

        printf("第%d趟排序结果:",num++);
        for(j=0 ; j<n ; j++)
        {
            printf("%d ", nums[j]);
        }
        printf("\n");
    }
    printf("排序过程比较次数:%d\n排序过程移动次数:%d\n",comnum,movnum);
    printf("\n");
}
/************************************************/

/********************主函数**********************/
int main()
{
    int n;
    cout<<"请输入文本的地址:"<<endl;
    cin>>path;
    while(1)
    {
        printf("    主菜单\n");
        printf("请选择排序算法\n");
        printf("冒泡排序法       1\n");
        printf("折半插入排序法   2\n");
        printf("希尔排序法       3\n");
        printf("快速排序法       4\n");
        printf("堆排序法         5\n");
        printf("直接插入排序法   6\n");
        printf("简单选择排序法   7\n");
        printf("退出             0\n");
        scanf("%d",&n);
        switch(n)
        {
            case 1: maopao();   continue;
            case 2: zheban();   continue;
            case 3: shell();    continue;
            case 4: kuaipai();  continue;
            case 5: duipai();   continue;
            case 6: zhicha();   continue;
            case 7: jiandan();  continue;
            default:    break;
        }
        fclose(fp);
        if(n == 0)
            break;
    }

    return 0;
}