(快速、基数)排序算法的设计

实验三： （快速、基数）排序算法的设计一、实验目的和要求(1) 深刻理解排序的定义和各种排序方法的特点，并能灵活运用。(2) 掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。(3) 了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的性能的分析方法。二、实验内容和原理（1）设计直接插入排序、冒泡排序、快速排序算法。（2）设计基数排序算法。三、实验环境1. 硬件：PC机；2. 软件：Windows操作系统、Visual C+ 6.0四、算法描述及实验步骤1、 直接插入排序在要排序的一组数中，假设前面(n-1) n=2 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。2、 冒泡排序 在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。3、 快速排序算法 通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。4、 基数排序算法五、调试过程六、实验结果1、2、3、4、七、总结 通过这次实验，对于多种排序有了一定地了解，在这次实验过程中，虽然遇到挺多的困难，但是我还是认真的对待。同时意识到我对这些方面的知识还是了解的不够深刻。附录：1、#include int a100; void insertsort(int n,int a) int i,j;for(i=2;i=n;i+)if(aiai-1) a0=ai;ai=ai-1; for(j=i-2;a0n;for(i=1;iai;insertsort(n,a);for(i=1;i=n;i+)coutai ;return 0;2、#include#define swap(x,y,t)(t)=(x),(x)=(y),(y)=(t)const int N=5;void sort(int b,int count);int main() int aN; coutendl; cout请输入：; for(int i=0;iai; coutendl; cout输出过程： ; for(i=0;iN;i+) cout ai; coutendl; cout输出结果：; sort(a,N); return 0;void sort(int b,int n) int t,tempt; for(int i=0;in;i+) t=n-i-1; for(int j=0;jbj+1) swap(bj,bj+1,tempt); for(i=0;iN;i+) cout bi;3、#includetemplatevoid quick_sort(T a,int p,int r)if(pr)int q=partition(a,p,r); quick_sort(a,p,q-1); quick_sort(a,q+1,r); templateint partition(T a,int p,int r) int i=p,j=r+1;T x=ap;while(true)while(a+ix&ix);if(i=j)break;swap(ai,aj);swap(aj,ap);return j;templatevoid swap(T& a,T& b)T temp;temp=a;a=b;b=temp;int main() int *a=new int 10; cout请输入10个数：; for(int i=0 ;iai; quick_sort(a,0,9); for(int j=0 ;j10 ;j+) coutaj ; return 0;4、#includevoid jishu(int * a) int *b=new int*10; int i,k; for(i=0;i10;i+) bi=new int10; int j=0; while(j10) i=aj%10; bij=aj; j+; k=0; for(i=0;i10;i+) for(j=0;j=0 & bij=99) ak=bij; bij=-1; k+; j=0; while(j10) i=aj/10; bij=aj; j+; k=0; for(i=0;i10;i+) for(j=0;j=0 & bij=99) ak=bij; k+; for(i=0;i10;i+) deletebi; delete b;int main()