实验八排序
一、实验目的
1. 熟悉掌握教材中所介绍的几种排序方法。
2. 学会分析各种内排序算法的性能 。
二、实验内容
1. 随机产生20位整数
2. 输入序列，编写程序，按下列排序方法将序列从小到大排序并输出。
(1) 冒泡排序
(2) 快速排序
3. 纪录每种方法比较次数和移动次数
三、实验步骤
1、冒泡排序
冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较。如此下去，直至最终完成排序。
2、快速排序
(1)基本思想
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
(2)实现方法
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是：
1）设置两个变量I、J，排序开始的时候：I=1，J=N-1；
2）以第一个数组元素作为关键数据，赋值给X，即 X=A[0]；
3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于X的值，让该值与X交换；
4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于X的值，让该值与X交换；
5）重复第3、4步，直到 I=J；
四、算法说明
首先为了避免产生的随机数过大，我们限定了了随机数为1-100之间，其次我们分别运用函数产生随机数两次，第一次为使用冒泡排序，第二次为使用快速排序。
五、测试结果
六、分析与探讨
在设计中除了注意冒泡排序和快速排序的原理外，还需要注意函数间的套用中出现的形参和实参的类型统一，以及交换两个数值时候，中介参数的使用。
七、附录：源代码
源代码列在附录中，要求程序风格清晰易理解，有充分的注释。有意义的注释行不少于30%。
#include"stdio.h"
#include"time.h"
#include"stdlib.h"
#include"iostream"
using namespace std;
void QuickSort(int p[], int start, int end)
{
if (start >= end)
{
return;
}
int i=0, j=0, tmp=0;
i = start;
j = end-1;
do
{
while(p[i] < p[end])
{
i++;
}
while(p[j] >= p[end])
{
j--;
}
if (i { tmp = p[i]; p[i] = p[j]; p[j] = tmp; } else { tmp = p[i]; p[i] = p[end]; p[end] = tmp; } } while(i QuickSort(p, start, i-1); QuickSort(p, i+1, end); } void PrintArrary(int data[], int size) { for (int i=0; i { cout < } cout< } void main() { int a[20],i,j,t,flag; int argc[20]; srand((unsigned)time(0)); for(i=0;i<20;i++) a[i]=rand()%100; cout<<"随机产生20个100以内的整数"< for(i=0;i<20;i++) cout < for(i=0;i<19;i++) /* 改进型冒泡法排序 */ { flag=0; for(j=0;j<20-i-1;j++) if(a[j]>a[j+1]) { t=a[j]; /* 交换a[i]和a[j] */ a[j]=a[j+1]; a[j+1]=t; flag=1; } if(flag==0)break; } cout< cout <<"将这20个整数按照冒泡排序进行升序排列"< for(i=0;i<20;i++) cout< cout< for(i=0;i<20;i++) argc[i]=rand()%100; cout<<"再次随机产生20个100以内的整数"< PrintArrary(argc, 20); cout< QuickSort(argc, 0, 19); cout<<"将这20个整数按照快速排序进行升序排列"< PrintArrary(argc, 20); } 实验六 内部排序算法比较 1、实验目的 掌握多种排序方法的基本思想，如直接插入、起泡、简单选择、快速、堆、希尔排序等排序方法，并能够用高级语言实现。 2、问题描述 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受 3、基本要求 （1） 对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 （2） 待排序的表长不小于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。 （3） 最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。 4、测试数据 由随机数产生器生成。 5、实现提示 主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如，正序、逆序和不同程度的乱序。注意采用分块调试的方法。 6、源程序 #include #include #include #define MAXNUM 10000 long cn[MAXNUM],mn[MAXNUM]; typedef struct { int key; }datatype; void D_InsertSort(datatype R[],long n)//直接排序 { long i ,j; for(i=2;i<=n;i++) { cn[0]++; if(R[i].key { R[0]=R[i];mn[0]++; for(j=i-1;R[0].key R[j+1]=R[j]; R[j+1]=R[0]; mn[0]+=2; } } } void Select_Sort(datatype R[],long n)//简单选择排序 { long i,j,k; for(i=1;i { k=i; for(j=i+1;j<=n;j++) { cn[1]++; if(R[j].key k=j; } if(i=k) { R[0]=R[k]; R[k]=R[i]; R[i]=R[0]; mn[1]+=3; } } } void Bubble_Sort(datatype R[],long n)//冒泡排序 { long i,j; for(i=1;i { for(j=1;j<=n-i;j++) { cn[2]++; if(R[j].key { R[0]=R[j]; R[j]=R[j+1]; R[j+1]=R[0]; mn[2]+=3; } } } } void HeapAdjust(datatype R[], long s, long t)//堆调整 { datatype rc; long i,j; rc=R[s]; i=s; for(j=2*i;j<=t;j=2*j) { cn[3]++; if(j j=j+1; if(rc.key>R[j].key) break; R[i]=R[j]; mn[3]++; i=j; } R[i]=rc; } void HeapSort(datatype R[], long n)//推排序 { long i; for(i=n/2;i>0;i--) HeapAdjust(R,i,n); for(i=n;i>1;i--) { R[0]=R[1]; R[1]=R[i]; R[i]=R[0]; mn[3]+=3; HeapAdjust(R,1,i-1); } } void Merge(datatype R[],datatype R1[], long s, long m, long t) { long i ,j ,k; i=s;j=m+1;k=s; while(i<=m&&j<=t) { cn[4]++; if(R[i].key { R1[k++]=R[i++]; mn[4]++; } else { R1[k++]=R[j++]; mn[4]++; } } while(i<=m) { R1[k++]=R[i++]; mn[4]++; } while(j<=t) { R1[k++]=R[j++]; mn[4]++; } } void MSort(datatype R[],datatype R1[], long s,long t) { long m; if(s==t) { R1[s]=R[s]; mn[4]++; } else{ m=(s+t)/2; MSort(R,R1,s,m); MSort(R,R1,m+1,t); Merge(R1,R,s,m,t); } } void MergeSort(datatype R[],datatype R1[],long n)//归并排序 { MSort(R,R1,1,n); } long Partition(datatype R[], long low, long high) { R[0]=R[low]; mn[5]++; while(low { while(low { cn[5]++;high--; } if(low { R[low]=R[high]; low++; mn[5]++; } while(low { cn[5]++; low++; } if(low { R[high]=R[low]; high--; mn[5]++; } } R[low]=R[0]; mn[5]++; return low; } void Quick_Sort(datatype R[],long s, long t)//快速排序 { long i; if(s { i=Partition(R,s,t); Quick_Sort(R,s,i-1); Quick_Sort(R,i+1,t); } } void prin(datatype R[], long n) { long i; printf("排序结果为 ：\n"); for(i=1;i<=n;i++) { printf("%d ",R[i]); } printf("\n"); } void suiji() { long i,n; datatype R[MAXNUM]={0};////定义结构数组 printf("请输入你要输入d个数\n"); scanf("%d",&n); if(n>500000) { printf("超出范围重新输入\n"); scanf("%d ",&n); } for(i=1;i<=n;i++) R[i].key=rand()%1000; printf("排序前的元素顺序\n"); for(i=1;i { printf("%d ",R[i].key); } printf("\n"); D_InsertSort(R,n);//直接排序 Select_Sort(R,n);//简单选择排序 Bubble_Sort(R,n);//冒泡排序 HeapSort(R,n); //推排序 datatype R2[MAXNUM]={0}; MergeSort(R,R2,n); Quick_Sort(R,0,n);//快速排序 prin(R,n); } int main() { suiji(); printf(" 比较结果 \n"); printf(" 排序方式 比较次数 移动次数\n"); printf(" 直接 %d %d \n",cn[0],mn[0]); printf(" 简单选择 %d %d \n",cn[1],mn[1]); printf(" 冒泡 %d %d \n",cn[2],mn[2]); printf(" 推排序 %d %d \n",cn[3],mn[3]); printf(" 快速排序 %d %d \n",cn[5],mn[5]); return 0; } 7、总结： 理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下
第二篇：数据结构实验六 内部排序
