数据结构实验快速排序

1、实 验 报 告 实验名称 排序 课程名称 数据结构与算法实验 | 专业班级：信息安全 学 号： 姓 名：1、 实验目的掌握快速排序2、 实验内容1、快速排序编写程序，实现快速排序。从键盘上输入10个整数，存放在数组中，然后用快速排序法对其从小到大进行排序，并输出排序结果。2、堆排序编写程序，实现堆排序。从键盘上输入10个整数，存放在数组中，然后用堆排序法对其从小到大进行排序，并输出排序结果。3、 主要算法与结构/快速排序int QuickSort(int a,int l,int r)int pivot;/枢轴int i=l;int j=r;int tmp;pivot=a(l+r)/2;/取数组

2、中间的数为枢轴do while (ai<pivot) i+; /i右移while (aj>pivot) j-; / j左移if (i<=j)tmp=ai; ai=aj; aj=tmp;/交换ai和aji+;j-;/堆排序void sift (int a,int size ,int p) int tmp= ap;int child=2*p+1;while(child<size) if(child<size-1)&&(achild <achild+1)child+;if(tmp<achild)ap=achild;p=child;child=

3、2*p+1;else break;ap=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=a0; a0=ai;ai=tmp;sift(a, i,0);4、 实验代码/快速排序#include <iostream.h>#define MAX 10int QuickSort(int a,int l,int r)int pivot;/枢轴int i=l;int j=r;int tmp;pivot=a(l+r)/2;/取数组中间的

4、数为枢轴do while (ai<pivot) i+; /i右移while (aj>pivot) j-; / j左移if (i<=j)tmp=ai; ai=aj; aj=tmp;/交换ai和aji+;j-; while(i<=j);if (l<j) QuickSort(a,l,j);if (i<r) QuickSort(a,i,r);return 1;/*/int main()int arrayMAX;int i;cout<<"请输入"<<MAX<<" 个整数:"for (i=0;i

5、<MAX;i+)cin>>arrayi;QuickSort(array,0,MAX-1);cout<<"快速排序后："<<endl;for (i=0;i<MAX;i+)cout<<arrayi<<" "cout<<endl;return 0;/堆排序#include<iostream>#define MAX 10using namespace std;void sift (int a,int size ,int p) int tmp= ap;int child

6、=2*p+1;while(child<size) if(child<size-1)&&(achild <achild+1)child+;if(tmp<achild)ap=achild;p=child;child=2*p+1;else break;ap=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=a0; a0=ai;ai=tmp;sift(a, i,0);void main () int i;int aMAX;cout<<"请输入"<<MAX<<"个整数"<<endl;for( i=0;i<MAX;i+)cin>>ai;heapsort(a,MAX);cout<<"经堆排序后："<<endl;for( i=0;i<MAX;i+)cout<<ai<<" "五、实验结果 /快速排序/堆排序6、 实验总结通过