数据结构实验快速排序

实 验 报 告

实验名称 排序 课程名称 数据结构与算法实验

专业班级：信息安全

学 号：

姓 名：

| |

一、实验目的

掌握快速排序

二、实验内容

1、快速排序

编写程序，实现快速排序。从键盘上输入10个整数，存放在数组中，然后用快速排序法对其从小到大进行排序，并输出排序结果。 2、堆排序

编写程序，实现堆排序。从键盘上输入10个整数，存放在数组中，然后用堆排序法对其从小到大进行排序，并输出排序结果。

三、主要算法与结构

//快速排序

int QuickSort(int a[],int l,int r) { int pivot; //枢轴 int i=l; int j=r; int tmp; pivot=a[(l+r)/2];//取数组中间的数为枢轴 do { while (a[i]pivot) j--; // j左移 if (i<=j) { tmp=a[i]; a[i]=a[j]; a[j]=tmp; //交换a[i]和a[j] i++; j--; } } //堆排序

void sift (int a[],int size ,int p) { int tmp= a[p]; int child=2*p+1; while(child child++; if(tmp

void heapsort( int a[], int n) { int i, tmp;

for(i=n/2-1;i>=0;i--) sift(a, n,i); for( i=n-1;i>0;i--) { tmp=a[0]; a[0]=a[i]; a[i]=tmp; sift(a, i,0); } }

四、实验代码

//快速排序

#include #define MAX 10

int QuickSort(int a[],int l,int r) { int pivot; //枢轴 int i=l; int j=r; int tmp; pivot=a[(l+r)/2];//取数组中间的数为枢轴 do { while (a[i]pivot) j--; // j左移 if (i<=j) { tmp=a[i]; a[i]=a[j]; a[j]=tmp; //交换a[i]和a[j] i++; j--;

} } while(i<=j); if (l

/*********************************************/ int main() { int array[MAX]; int i;

cout<<\请输入\个整数:\ for (i=0;i>array[i]; QuickSort(array,0,MAX-1); cout<<\快速排序后：\ for (i=0;i//堆排序

#include #define MAX 10 using namespace std;

void sift (int a[],int size ,int p) { int tmp= a[p]; int child=2*p+1; while(child else break; } a[p]=tmp; }

void heapsort( int a[], int n) { int i, tmp;

for(i=n/2-1;i>=0;i--) sift(a, n,i); for( i=n-1;i>0;i--) { tmp=a[0]; a[0]=a[i]; a[i]=tmp; sift(a, i,0); }}

void main () { int i; int a[MAX];

cout<<\请输入\个整数\for( i=0;i>a[i];

heapsort(a,MAX);

cout<<\经堆排序后：\for( i=0;i五、实验结果

//快速排序

//堆排序

六、实验总结

通过本次试验，让我更深刻理解了快速排序法与其应用，因为快速排序是对冒泡排序的一种改进，所以在冒泡排序的原有基础上再学习快速排序就显得不是很困难。但在上机的操作过场中，发现了自己平时疏忽的细节，以后的学习过程中要多加注意。