2015-01-25 13:30:24 qq_15379219 阅读数 2944
  • 数据结构基础系列(10):外部排序

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第10部分外部排序。外部排序针对数据量很大时,排序过程必须要在内、外存之间交换数据时的应用,介绍磁盘排序和磁带排序的相关算法。

    8161 人正在学习 去看看 贺利坚

 

 

数据结构与算法课程实验报告

 

 

 

 

实验六:排序实践

                  

 

 

 

 

 

 

 

                    

 

 

姓名:

班级:               

学号: 

 

 

 

 

 

 

 

 

 

 

实验六 排序实践

一.实验内容:

      实现各排序算法,必须实现起泡排序、希尔排序和简单选择排序,其他排序算法选做,并分析各算法的性能。

二.实验目的:

     掌握各排序算法的实现方法,并分析各排序算法的时间和空间性能。

三:问题描述:

希尔排序:在每趟排序前,先设置一个增量,将整个待排记录序列逐段分割成若干个子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。

起泡排序:第一趟起泡排序是将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则将两个记录交换,然后比较第二个记录和第三个记录的关键字。以此类推,直到将第n-1个记录和第n个记录的关键字进行比较过为止。再进行第二趟起泡排序,直到在一趟排序过程中没有进行过交换记录的操作为止。

简单选择排序:通过n-i次关键字间的比较,从n-i+1个记录中选择出关键字最小的记录,并和第i1<=i<=n)个记录交换。

四:问题实现

1.定义了两个数据结构,记录类型和顺序表类型。

typedef struct

{

      int key;         //关键字项

}RedType;           //记录类型

 

typedef struct

{

RedType r[MAX+1];  //r[0]做监视哨或暂存空间,MAX 20 为顺序表的最大长度

int length;   //顺序表长度

}SqList;  //顺序表类型。

2.主要实现思路:将待排序的序列存放在顺序表里,再进行相应的排序,每个排序都有初始关键字、每趟排序结果、最终排序结果的显示。

希尔排序:要自定义排序的趟数和每趟排序的增量,增量存放在一个数组里。主要是通过比较关键字的大小,记录后移,找到插入位置,然后插入。

起泡排序:设置了一个标记 flag;用于标记排序是否结束,flag=1继续,flag=0结束。主要是通过两两比较,每次都选出一个无序区里最大的关键字,直到全部有序为止。

简单选择排序:定义了一个函数SelectMinKey(SqList &L,int i)返回key最小的记录的下标。主要是选择关键字最小的记录的操作。

五:主要源程序代码(包含程序备注)

1.顺序表的初始化

SqList InitSqList(SqList &L)

{

      int N;

      cout<<"请输入待排序数据的个数N="<<endl;

      cin>>N;

      L.length=N+1;

      return L;

}

2.顺序表的创建

SqList CreateSqList(SqList &L)

{

      InitSqList(L);

    cout<<"请输入待排序的数据"<<endl;

      for(int i=1;i<L.length;i++)

      {

           cout<<"L.r["<<i<<"].key=";

           cin>>L.r[i].key;

      }

      return L;

}

3.定义SelectMinKey(SqList &L,int i)函数,返回key最小的记录的下标。

int SelectMinKey(SqList &L,int i)

{

      int j;//v记录关键字最小的记录的下标

      int v=i;

      for(j=i+1;j<L.length;j++)

      {

           if(L.r[j].key<L.r[v].key)v=j;

      }

      return v;

}

4. 简单选择排序的实现

void SelectSort(SqList &L)//对顺序表L作简单选择排序

{

      cout<<"初始关键字 ";

      for(int j1=1;j1<L.length;j1++)cout<<" "<<L.r[j1].key;

      int j;

      int count=0;//记录排序趟数

 

      for(int i=1;i<L.length;i++)   //选择第i小的记录,并交换到位

      {

       j=SelectMinKey(L,i);    //选择key最小的记录

         if(i!=j)                    //与第i个记录交换

         {

              L.r[0]=L.r[i];   

              L.r[i]=L.r[j];

              L.r[j]=L.r[0];

         }

         count++;   

           cout<<endl<<count<<"趟排序结果:";

           for(int j2=1;j2<L.length;j2++)cout<<" "<<L.r[j2].key;

      }

}

5.起泡排序的实现

void BubbleSort(SqList &L)

{

      cout<<"初始关键字 ";

      for(int j1=1;j1<L.length;j1++)cout<<" "<<L.r[j1].key;

 

      int count=0;//记录排序趟数

      int flag=1;//用于标记排序是否结束,flag=1继续,flag=0结束

      int m=L.length-2;//m用于记录无序区的个数,初始为n-1,因为L.r[0]不放数据,所以L.length=n+1

      while((m>0)&&(flag==1))   //m=0说明数据已全部有序

      {

           flag=0;

           for(int i=1;i<=m;i++)

           {

                 if(L.r[i].key>L.r[i+1].key)

                 {

                flag=1;

                      L.r[0]=L.r[i];

                      L.r[i]=L.r[i+1];

                      L.r[i+1]=L.r[0];

                 }

           }

           m--;

           count++;   

           cout<<endl<<count<<"趟排序结果:";

           for(int j2=1;j2<L.length;j2++)cout<<" "<<L.r[j2].key;

      }

}

6.一趟希尔排序的实现

void ShellInsert(SqList &L,int d) // L.r[0]是暂存单元,不是哨兵。j<=0时,插入位置已找到

{

      int j;

    for(int i=d+1;i<L.length;++i)

      {

           if(L.r[i].key<L.r[i-d].key)

           {

                 L.r[0]=L.r[i];//L.r[i]插入有序增量子表,暂存在L.r[0]

                 for(j=i-d;j>0&&(L.r[0].key<L.r[j].key);j-=d)

                 {

                      L.r[j+d]=L.r[j];         //记录后移,查找插入位置

                 }

                 L.r[j+d]=L.r[0];      //插入位置已找到,插入

 

           }

      }

}

 

7. t趟希尔排序的实现

void ShellSort(SqList &L)

{

      int t;

      int dk[MAX];

      cout<<"请输入排序趟数"<<endl;

      cin>>t;

      cout<<"请输入增量序列,要求没有除1外的公因子"<<endl;

      for(int i=0;i<t;i++)

      {

           cin>>dk[i];

      }

      while(dk[t-1]!=1)

      {

           cout<<"最后一个增量值必须为1"<<endl;

      }

      cout<<"初始关键字 ";

      for(int j1=1;j1<L.length;j1++)cout<<" "<<L.r[j1].key;

      for(int k=0;k<t;k++)

      {

           ShellInsert(L,dk[k]);

           cout<<endl<<k+1<<"趟排序结果:";

           for(int j2=1;j2<L.length;j2++)cout<<" "<<L.r[j2].key;

      }

     

     

}

 

8.主程序

void main()

{ 

      int ch,n=1; 

      do

      {

           SqList L;

          CreateSqList(L);

           cout<<"1.简单选择排序;2.冒泡排序;3.希尔排序"<<endl;

          cin>>ch;

           switch(ch)

           {

           case 1:SelectSort(L);

                 break;

           case 2:BubbleSort(L);

                 break;

           case 3:ShellSort(L);

                 break;       

           }

           cout<<endl<<endl<<"排序后:"<<endl;

           for(int i=1;i<L.length;i++)

           {

                 cout<<" "<<L.r[i].key;

           }

 

           do

           {

           cout<<endl<<endl<<"1.继续;2.退出"<<endl;

           cin>>n;          

           }while(n!=1&&n!=2);

      }while(n==1);

     

}

 

六:总结

在设计希尔排序的增量时,存在一些问题。我设计的是让用户自己定义要排序的趟数,和每趟排序的增量,并且设置了最后一趟增量必须为1,但其他没有强制设置。

2019-11-12 10:34:24 weixin_42703039 阅读数 149
  • 数据结构基础系列(10):外部排序

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第10部分外部排序。外部排序针对数据量很大时,排序过程必须要在内、外存之间交换数据时的应用,介绍磁盘排序和磁带排序的相关算法。

    8161 人正在学习 去看看 贺利坚

排序算法选择
一、目的与要求

  1. 掌握树及图型结构的逻辑特点及存储实现;
  2. 根据选题,按规范化流程完成课程设计报告:
    ⑴.提供需求分析。(15分)
    ⑵.列出概要设计。(包括:抽象数据类型的描述;程序结构图或功能模块图)(20分)
    ⑶.给出详细设计。(包括:①存储结构的描述;②算法的详细设计,对复杂算法,最好画出其N-S流程图;③函数的调用关系图)(30分)
    ⑷.进行调试分析(注:调试时遇到的问题及解决方法,程序的输出结果及对结果的分析)。(15分)
    ⑸. 整理设计总结。(设计心得体会,以及其他总结信息等)(10分)
    ⑹.附有程序清单(注:代码可具有适当注释,用来说明程序的功能、结构)。(10分)
    二、设计步骤
    1.提供需求分析。
    由用户选择对该组数据进行排序的方法:直接插入排序、冒泡排序、快速排序、简单选择排序。并可以查看每趟排序的结果。
    需要不同的排序方法函数
    2.列出概要设计
    抽象数据类型的描述 无
    程序结构图或功能模块图
    在这里插入图片描述

3.详细设计
存储结构的描述

	srand((unsigned)time(NULL));
	int a[10];
	for (int i = 0; i < 10; i++)
		a[i] = rand() % 100;//生成随机数组

算法的详细设计

void InsertSort(int* a, int n)//直接插入
{
	assert(a);
	int i, j;
	for (i = 1; i < n; i++)
	{
		if (a[i] < a[i - 1])
		{
			int temp = a[i];
			for (j = i - 1; j >= 0 && a[j] > temp; j--)
			{
				a[j + 1] = a[j];
			}
			a[j + 1] = temp;
		}
		printf("第%02d趟:", i);
		PrintArray(a, n);
	}
}
void shellInsert(int array[], int n)//Hibbard增量 希尔
{
	int t = (int)(log(n + 1) / log(2));//t为排序趟数,排序趟数应为log2(n+1)的整数部分
	int i, dk;
	for (i = 1; i <= t; i++)
	{
		dk = (int)(pow(2, t - i + 1) - 1);//计算Hibbard增量
		//根据当前增量进行插入排序
		int k, j, temp;
		for (k = dk; k < n; k++)//分别向每组的有序区域插入
		{
			temp = array[k];
			for (j = k - dk; (j >= k % dk) && array[j] > temp; j -= dk)//比较与记录后移同时进行
				array[j + dk] = array[j];
			if (j != k - dk)
				array[j + dk] = temp;//插入
		}
	}
}
void ShellSort(int* a, int n)//希尔插入
{
	assert(a);

	int gap = n;
	int i, j, k = 1;
	while (gap /= 2)
	{
		for (i = gap; i < n; i++)
		{
			int temp = a[i];
			for (j = i - gap; j >= 0 && a[j] > temp; j -= gap)
			{
				a[j + gap] = a[j];
			}
			a[j + gap] = temp;
		}
		printf("第%02d趟:", k++);
		PrintArray(a, n);
	}
}

void BubbleSort(int* a, int n)//冒泡排序
{
	assert(a);

	int i, j = n, k = 1;
	int flag = 1;
	while (flag)
	{
		flag = 0;
		for (i = 1; i < j; i++)
		{
			if (a[i] < a[i - 1])
			{
				swap(&a[i], &a[i - 1]);
				flag = 1;
			}	
		}
		j--;
		if (flag)
		{
			printf("第%02d趟:", k++);
			PrintArray(a, n);
		}
	}
}
void SelectionSort(int* a, int n)//直接选择
{
	assert(a);

	int min, i, j;
	for (i = 0; i < n; i++)
	{
		min = i;
		for (j = i; j < n; j++)
		{
			if (a[j] < a[min])
				min = j;
		}
		swap(&a[i], &a[min]);
		printf("第%02d趟:", i+1);
		PrintArray(a, n);
	}
}

void QuickSort(int* a, int left, int right, int n)//快速排序
{
	assert(a);

	if (left < right)
	{
		static int k = 1;
		int i = left, j = right, x = a[left];
		while (i < j)
		{
			while (i < j && a[j] >= x) // 从右向左找第一个小于x的数
				j--;
			if (i < j)
				a[i++] = a[j];

			while (i < j && a[i] < x) // 从左向右找第一个大于等于x的数
				i++;
			if (i < j)
				a[j--] = a[i];
		}
		a[i] = x;
		printf("第%02d趟:", k++);
		PrintArray(a, n);
		QuickSort(a, left, i - 1, n); 
		QuickSort(a, i + 1, right, n);// 递归调用 
		
	}
}
void MergeSort(int*a, int left, int right, int* temp)//归并排序
{
	if (left >= right)
		return;

	int mid = (left + right) / 2;//left + ((right - left) >> 1);
	int begin1, begin2, end1, end2;
	int i = 0;

	MergeSort(a, left, mid, temp);
	MergeSort(a, mid + 1, right, temp);

	begin1 = left;
	end1 = mid;
	begin2 = mid + 1;
	end2 = right;
	i = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] > a[begin2])
		{
			temp[i++] = a[begin2++];
		}
		else
		{
			temp[i++] = a[begin1++];
		}
	}
	while (begin1 <= end1)
	{
		temp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		temp[i++] = a[begin2++];
	}

	//memcpy(a + left, temp + left, end1-left);
	for (i--; i >= left; i--)
	{
		a[i] = temp[i];
	}
}

函数的调用关系
选择哪种排序方法,调用对应函数
4.进行调试分析
在这里插入图片描述
在这里插入图片描述在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述成功输出了从小到大的数字,说明排序算法实现正确
三、设计总结
通过本次实验,我完成各种不同的排序算法,实现了对排序算法的应用,并看到计算机在实现不同排序时,每一趟的排序情况,更加深刻理解排序算法。
四、代码清单

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<math.h>
#include<time.h>

void swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}
void PrintArray(int* a, int n)
{
	int i = 0;
	for (; i < n - 1; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("%d\n", a[i]);
}
//自小到大
void InsertSort(int* a, int n)//直接插入
{
	assert(a);
	int i, j;
	for (i = 1; i < n; i++)
	{
		if (a[i] < a[i - 1])
		{
			int temp = a[i];
			for (j = i - 1; j >= 0 && a[j] > temp; j--)
			{
				a[j + 1] = a[j];
			}
			a[j + 1] = temp;
		}
		printf("第%02d趟:", i);
		PrintArray(a, n);
	}
}
void shellInsert(int array[], int n)//Hibbard增量 希尔
{
	int t = (int)(log(n + 1) / log(2));//t为排序趟数,排序趟数应为log2(n+1)的整数部分
	int i, dk;
	for (i = 1; i <= t; i++)
	{
		dk = (int)(pow(2, t - i + 1) - 1);//计算Hibbard增量
		//根据当前增量进行插入排序
		int k, j, temp;
		for (k = dk; k < n; k++)//分别向每组的有序区域插入
		{
			temp = array[k];
			for (j = k - dk; (j >= k % dk) && array[j] > temp; j -= dk)//比较与记录后移同时进行
				array[j + dk] = array[j];
			if (j != k - dk)
				array[j + dk] = temp;//插入
		}
	}
}
void ShellSort(int* a, int n)//希尔插入
{
	assert(a);

	int gap = n;
	int i, j, k = 1;
	while (gap /= 2)
	{
		for (i = gap; i < n; i++)
		{
			int temp = a[i];
			for (j = i - gap; j >= 0 && a[j] > temp; j -= gap)
			{
				a[j + gap] = a[j];
			}
			a[j + gap] = temp;
		}
		printf("第%02d趟:", k++);
		PrintArray(a, n);
	}
}

void BubbleSort(int* a, int n)//冒泡排序
{
	assert(a);

	int i, j = n, k = 1;
	int flag = 1;
	while (flag)
	{
		flag = 0;
		for (i = 1; i < j; i++)
		{
			if (a[i] < a[i - 1])
			{
				swap(&a[i], &a[i - 1]);
				flag = 1;
			}	
		}
		j--;
		if (flag)
		{
			printf("第%02d趟:", k++);
			PrintArray(a, n);
		}
	}
}
void SelectionSort(int* a, int n)//直接选择
{
	assert(a);

	int min, i, j;
	for (i = 0; i < n; i++)
	{
		min = i;
		for (j = i; j < n; j++)
		{
			if (a[j] < a[min])
				min = j;
		}
		swap(&a[i], &a[min]);
		printf("第%02d趟:", i+1);
		PrintArray(a, n);
	}
}

void QuickSort(int* a, int left, int right, int n)//快速排序
{
	assert(a);

	if (left < right)
	{
		static int k = 1;
		int i = left, j = right, x = a[left];
		while (i < j)
		{
			while (i < j && a[j] >= x) // 从右向左找第一个小于x的数
				j--;
			if (i < j)
				a[i++] = a[j];

			while (i < j && a[i] < x) // 从左向右找第一个大于等于x的数
				i++;
			if (i < j)
				a[j--] = a[i];
		}
		a[i] = x;
		printf("第%02d趟:", k++);
		PrintArray(a, n);
		QuickSort(a, left, i - 1, n); 
		QuickSort(a, i + 1, right, n);// 递归调用 
		
	}
}
void MergeSort(int*a, int left, int right, int* temp)//归并排序
{
	if (left >= right)
		return;

	int mid = (left + right) / 2;//left + ((right - left) >> 1);
	int begin1, begin2, end1, end2;
	int i = 0;

	MergeSort(a, left, mid, temp);
	MergeSort(a, mid + 1, right, temp);

	begin1 = left;
	end1 = mid;
	begin2 = mid + 1;
	end2 = right;
	i = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] > a[begin2])
		{
			temp[i++] = a[begin2++];
		}
		else
		{
			temp[i++] = a[begin1++];
		}
	}
	while (begin1 <= end1)
	{
		temp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		temp[i++] = a[begin2++];
	}

	//memcpy(a + left, temp + left, end1-left);
	for (i--; i >= left; i--)
	{
		a[i] = temp[i];
	}
}
void table()
{
	printf("请选择对该组数据进行排序的方法:\n");
	printf("1.直接插入排序\n");
	printf("2.希尔排序\n");
	printf("3.冒泡排序\n");
	printf("4.快速排序排序\n");
	printf("5.简单选择排序\n");
	printf("6.归并排序\n");
	printf("0.退出\n");
}
int main()
{
	//int a[10] = { 9,4,3,2,5,6,1,7,0,8 };
	srand((unsigned)time(NULL));
	int a[10];
	for (int i = 0; i < 10; i++)
		a[i] = rand() % 100;//生成随机数组
	int n = sizeof(a) / sizeof(a[0]);
	int* temp = (int*)malloc(sizeof(int)*n);
	int x = 0;
	printf("排序前数组:");
	PrintArray(a, n);
	table();
	scanf("%d", &x);
	printf("第00趟:");
	PrintArray(a, n);
	switch (x)
	{
	case 1:
		InsertSort(a, n);//直接插入
		break;
	case 2:
		//shellInsert(a, n);//Hibbard增量 希尔
		ShellSort(a, n);//希尔插入
		break;
	case 3:
		BubbleSort(a, n);//冒泡排序
		break;
	case 4:
		QuickSort(a, 0, n - 1, n);//快速排序
		break;
	case 5:
		SelectionSort(a, n);//直接选择
		break;
	case 6:
		MergeSort(a, 0, n-1, temp);//归并排序
		break;
	case 0:
		break;
	}
	printf("排序后数组:");
	PrintArray(a, n);
	system("pause");
	return 0;
}
2019-12-18 16:19:40 weixin_43272781 阅读数 272
  • 数据结构基础系列(10):外部排序

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第10部分外部排序。外部排序针对数据量很大时,排序过程必须要在内、外存之间交换数据时的应用,介绍磁盘排序和磁带排序的相关算法。

    8161 人正在学习 去看看 贺利坚

《数据结构》实验报告

学号:  2018329621200   

机器号 10-414-28  

姓名: 申屠志刚

日期:  2019/12/18        

程序名:       main.cpp       

实验内容:   快速排序   

  • 目的和要求(需求分析):
  1. 掌握快速排序的实现方法
  2. 掌握快速排序的基本思想
  3. 掌握快速排序的时间性能
  4. 要求:用快速排序法实现对无序序列的排序
  • 程序设计的基本思想,原理和算法描述:

 使用分治策略,将一个序列分为两个子序列。

步骤:

在待排序的n个记录中任选一个进行记录(通常选第一个),作为为基准(分区标准)。

进行分区,即:将所有比基准值小的元素放在基准左边,所有比基准值大的元素放在基准的右边,中间为所选的基准。

对左右两个分区递归进行步骤1、2,递归结束条件是序列的大小是0或1。

  • 调试和运行程序过程中产生的问题及采取的措施:

  • 源程序及注释:
/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
void quickSort(int a[],int low, int high)//a:待排序数组,low:最低位的下标,high:最高位的下标
{
    int left=low,right=high;
    int key=a[left];//用数组的第一个记录作为分区元素
    if(low>=high)
        return;
    while(left!=right){
        while(left<right&&a[right]>=key)//从右向左扫描,找第一个码值小于key的记录,并交换到key
            right--;
        a[left]=a[right];
        while(left<right&&a[left]<=key)//从左向右扫描,找第一个码值大于key的记录,并交换到右边
            left++;
        a[right]=a[left];
    }
    a[left]=key;//分区元素放到正确位置
    quickSort(a,low,left-1);
    quickSort(a,left+1,high);
}
int main()
{
    int a[]={2,6,2,3,5,8,9,1,2,4,5,3};
    quickSort(a,0,12);
    for(auto b:a)
        cout<<b<<endl;
    //cout << "Hello world!" << endl;
    return 0;
}
  • 运行结果

 

  • 心得与体会:

通过本次试验,让我更深刻理解了快速排序法与其应用,因为快速排序是对冒泡排序的一种改进,所以在冒泡排序的原有基础上再学习快速排序就显得不是很困难。

2015-12-20 16:28:05 qq_29600137 阅读数 1285
  • 数据结构基础系列(10):外部排序

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第10部分外部排序。外部排序针对数据量很大时,排序过程必须要在内、外存之间交换数据时的应用,介绍磁盘排序和磁带排序的相关算法。

    8161 人正在学习 去看看 贺利坚

1.希尔排序

     

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
//希尔排序 
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef struct 
{
	int key;
	char *otherinfo;
}ElemType;
typedef struct 
{
	ElemType *r;
	int length;
}SqList;
void ShellInsert(SqList &L,int dk)
{
	int i,j;
	for(i=dk+1;i<=L.length;i++)
	{
		if(L.r[i].key<L.r[i-dk].key)
		{
			L.r[0]=L.r[i];
			for(j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)
			{
				L.r[j+dk]=L.r[j];
			}
			L.r[j+dk]=L.r[0];
		}
	}
}
void ShellSort(SqList &L,int dt[],int t)
{
	int k;
	for(k=0;k<t;k++)
	{
		ShellInsert(L,dt[k]);
	}
}
int main()
{
	SqList L;
	L.r=new ElemType[100];
	L.length=0;
	printf("请输入数据个数:");
	int nn;
	scanf("%d",&nn);
	printf("请输入待排序数据:\n");
	for(int i=1;i<=nn;i++)
	{
		scanf("%d",&L.r[i].key);
		L.length++;
	}
	int i,t;
	int *dt=new int[1000];//增量数组 
	printf("输入增量的个数:");
	int yy;
	scanf("%d",&yy);
	for(i=0;i<yy;i++)
	{
		scanf("%d",&dt[i]);
	} 
	ShellSort(L,dt,yy);
	printf("排序后的结果:");
	for(i=1;i<=nn;i++)
	{
		printf("%d ",L.r[i].key);
	}
	printf("\n");
	return 0;
}
<strong><span style="font-size:24px;">2.快速排序</span></strong>

快速排序(Quicksort)是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
//快速排序 
#include <iostream>
using namespace std;
#define  MAXSIZE  20          			//顺序表的最大长度
typedef struct
{
	int key;
	char *otherinfo;
}ElemType;
//顺序表的存储结构                         
typedef struct
{
    ElemType *r;	         						//存储空间的基地址
    int  length;            						//顺序表长度
}SqList;											//顺序表类型
int Partition(SqList &L,int low,int high)
{ 
	//对顺序表L中的子表r[low..high]进行一趟排序,返回枢轴位置
	int pivotkey;
	L.r[0]=L.r[low];                    	//用子表的第一个记录做枢轴记录
	pivotkey=L.r[low].key;		   			//枢轴记录关键字保存在pivotkey中
	while(low<high)
	{										//从表的两端交替地向中间扫描
		while(low<high&&L.r[high].key>=pivotkey) --high;
		L.r[low]=L.r[high];					//将比枢轴记录小的记录移到低端
		while(low<high&&L.r[low].key<=pivotkey) ++low;
		L.r[high]=L.r[low];					//将比枢轴记录大的记录移到高端
	}//while
	L.r[low]=L.r[0];						//枢轴记录到位
	return  low;							//返回枢轴位置
}//Partition
void QSort(SqList &L,int low,int high)
{	//调用前置初值:low=1; high=L.length;
    //对顺序表L中的子序列L.r[low..high]做快速排序
	int pivotloc;
    if(low<high)
	{										//长度大于1
       pivotloc=Partition(L,low,high); 		//将L.r[low..high]一分为二,pivotloc是枢轴位置
       QSort(L,low,pivotloc-1);				//对左子表递归排序
       QSort(L,pivotloc+1,high);        	//对右子表递归排序
	}
}											//QSort
void QuickSort(SqList &L)
{
   //对顺序表L做快速排序
   QSort(L,1,L.length);
}											//QuickSort								
void Create_Sq(SqList &L)
{
	int i,n;
	cout<<"请输入数据个数,不超过"<<MAXSIZE<<"个。"<<endl;
	cin>>n;											//输入个数
	cout<<"请输入待排序的数据:\n";
	while(n>MAXSIZE)
	{
		cout<<"个数超过上限,不能超过"<<MAXSIZE<<",请重新输入"<<endl;
		cin>>n;
	}
	for(i=1;i<=n;i++)
	{
		cin>>L.r[i].key;
		L.length++;
	}
}
void show(SqList L)
{
	int i;
	for(i=1;i<=L.length;i++)
		cout<<L.r[i].key<<endl;
}
int main()
{
	SqList L;
	L.r=new ElemType[MAXSIZE+1];
	L.length=0;
	Create_Sq(L);
	QuickSort(L);
	cout<<"排序后的结果为:"<<endl;
	show(L);
}
3.堆排序
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。
//堆排序 
#include <iostream>
using namespace std;
#define  MAXSIZE  20          						//顺序表的最大长度
typedef struct
{
	int key;
	char *otherinfo;
}ElemType;                       
typedef struct
{
    ElemType *r;	         						//存储空间的基地址
    int  length;            						//顺序表长度
}SqList;											//顺序表类型
void HeapAdjust(SqList &L,int s,int m)
{ 
   //假设r[s+1..m]已经是堆,将r[s..m]调整为以r[s]为根的大根堆
	ElemType rc;
	int j;
	rc=L.r[s];
    for(j=2*s;j<=m;j*=2)
	{												//沿key较大的孩子结点向下筛选
		if(j<m&&L.r[j].key<L.r[j+1].key) ++j;		//j为key较大的记录的下标
        if(rc.key>=L.r[j].key) break;      			//rc应插入在位置s上
		L.r[s]=L.r[j]; s=j; 
    }
	L.r[s]=rc;                          			//插入
}												//HeapAdjust								
void Create_Sq(SqList &L)
{
	int i,n;
	cout<<"请输入数据个数,不超过"<<MAXSIZE<<"个。"<<endl;
	cin>>n;											//输入个数
	cout<<"请输入待排序的数据:\n";
	while(n>MAXSIZE)
	{
		cout<<"个数超过上限,不能超过"<<MAXSIZE<<",请重新输入"<<endl;
		cin>>n;
	}
	for(i=1;i<=n;i++)
	{
		cin>>L.r[i].key;
		L.length++;
	}
}
void CreatHeap(SqList &L)
{
	//把无序序列L.r[1..n]建成大根堆
	int i,n;
	n=L.length;
	for(i=n/2;i>0;--i)       					//反复调用HeapAdjust 
		HeapAdjust(L,i,n);
}												//CreatHeap
void HeapSort(SqList &L) 
{ 
	//对顺序表L进行堆排序 
	int i;
	ElemType x;
	CreatHeap(L);              					//把无序序列L.r[1..L.length]建成大根堆 
	for(i=L.length;i>1;--i)
	{ 
		x=L.r[1];               				//将堆顶记录和当前未经排序子序列L.r[1..i]中最后一个记录互换 
		L.r[1]=L.r[i];            
		L.r[i]=x; 
		HeapAdjust(L,1,i-1);					//将L.r[1..i-1]重新调整为大根堆 **
   	}
}
void show(SqList L)
{
	int i;
	for(i=1;i<=L.length;i++)
		cout<<L.r[i].key<<endl;
}
int main()
{
	SqList L;
	L.r=new ElemType[MAXSIZE+1];
	L.length=0;
	Create_Sq(L);
	HeapSort(L);
	cout<<"排序后的结果为:"<<endl;
	show(L);
}





2016-08-22 15:52:28 zheng__jun 阅读数 1638
  • 数据结构基础系列(10):外部排序

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第10部分外部排序。外部排序针对数据量很大时,排序过程必须要在内、外存之间交换数据时的应用,介绍磁盘排序和磁带排序的相关算法。

    8161 人正在学习 去看看 贺利坚

数据结构实验之排序六:希尔排序

Time Limit: 1000ms   Memory limit: 65536K  

题目描述

我们已经学习了各种排序方法,知道在不同的情况下要选择不同的排序算法,以期达到最好的排序效率;对于待排序数据来说,若数据基本有序且记录较少时, 直接插入排序的效率是非常好的,希尔排序就是针对一组基本有序的少量数据记录进行排序的高效算法。你的任务是对于给定的数据进行希尔排序,其中增量dk=n/(2^k)(k=1,2,3……)

输入

连续输入多组数据,每组输入数据的第一行给出一个正整数N(N <= 10000),随后连续给出N个整数表示待排序关键字,数字间以空格分隔。

 

输出

输出dk=n/2和dk=1时的结果。

示例输入

10
10 9 8 7 6 5 4 3 2 1
10
-5 9 7 -11 37 -22 99 288 33 66

示例输出

5 4 3 2 1 10 9 8 7 6
1 2 3 4 5 6 7 8 9 10
-22 9 7 -11 37 -5 99 288 33 66
-22 -11 -5 7 9 33 37 66 99 288

提示

希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。

该方法的基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。

 

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

第一次 gap = 10 / 2 = 5

49   38   65   97   26   13   27   49   55   4

1A                                        1B

        2A                                         2B

                 3A                                         3B

                         4A                                          4B

                                  5A                                         5B

1A,1B,2A,2B等为分组标记,数字相同的表示在同一组,大写字母表示是该组的第几个元素, 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49)  (97, 55)  (26, 4)这样每组排序后就变成了(13, 49)  (27, 38)  (49, 65)  (55, 97)  (4, 26),下同。

第二次 gap = 5 / 2 = 2

排序后

13   27   49   55   4    49   38   65   97   26

1A             1B             1C              1D            1E

        2A               2B             2C             2D              2E

第三次 gap = 2 / 2 = 1

4   26   13   27   38    49   49   55   97   65

1A   1B     1C    1D    1E      1F     1G    1H     1I     1J

第四次 gap = 1 / 2 = 0 排序完成得到数组:

4   13   26   27   38    49   49   55   65   97

 

#include<stdio.h>
#define MaxN 10000
int a[MaxN];
int n;
void ShellSort()
{
    int i,j,dk,k=2,tmp;
    dk=n/k;     //增量赋初值
    while(dk>0)
    {
        for(i=dk; i<n; i++) //对所有间隔dk位置的元素组采用直接插入排序
        {
            tmp=a[i];
            j=i-dk;
            while(j>=0&&tmp<a[j])//对间隔dk位置的元素组排序
            {
                a[j+dk]=a[j];
                j-=dk;
            }
            a[j+dk]=tmp;
        }
        if(dk==n/2||dk==1)
            for(i=0; i<n; i++)
                printf("%d%c",a[i],i==n-1?'\n':' ');
        k*=2;
        dk=n/k;
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);
        ShellSort();
    }
    return 0;
}


数据结构实验报告

阅读数 3632

没有更多推荐了,返回首页