直接选择排序法-直接插入排序法、快速排序法、堆排序法、冒泡排序发-实验

1、精选优质文档-倾情为你奉上#include<iostream>using namespace std;typedef int ElemType;/直接插入排序void InsertSort ( ElemType A, int n )int i, j;ElemType x;for ( i=1; i<n; i+ ) /进行n-1次插入 x = Ai; /准备插入第i个元素 for ( j=i-1; j>=0; j- ) /从第i-1个开始往前找插入点 if ( x< Aj ) Aj+1=Aj; else break; Aj+1=x; /插入/直接选择排序void Se

2、lectSort(ElemType A, int n) int i, j, k; ElemType x; for ( i=0; i<=n-2; i+ ) /每一趟选择最小元素并与Ai交换 k=i; for (j=i+1; j<=n-1; j+) /查找最小元素的下标 if (Aj<Ak) k=j; if (k!=i) /交换x=Ai; Ai=Ak; Ak=x; /堆排序void Sift(ElemType A, int n, int i);void CreatHeap(ElemType A, int n) int i; for( i = (n-2)/2; i >= 0;

3、 i-) Sift(A, n, i); /调整Ai.n-1使之为一个堆 void Sift(ElemType A, int n, int i) / 调整Ai.n-1成为一个堆（它的左右子树已是一个堆） ElemType x=Ai; int j = 2 * i + 1; / j为i的左孩子 while (j <= n-1) / i有左子树 if ( j +1 < n && Aj< Aj+1) j+; / 使j指向左右孩子中排序码大的孩子 if ( x< Aj) /将Aj上移，以便向下筛 Ai=Aj; i=j; j=2*i+1; else break; Ai

4、=x; void HeapSort(ElemType A, int n) /A为待排序表，n为表的长度 int i; ElemType x; CreatHeap(A, n); / 把A建成一个堆 for(i=n-1;i>=1;i-) x = A0; /第个元素与第i个元素交换 A0 = Ai; Ai = x; Sift(A, i, 0); /调整A0.i-1使之为一个堆 /冒泡排序void BubbleSort( ElemType A, int n )int i, j, flag; /flag为交换标记ElemType x;for (i=1; i<=n-1; i+) / 最多n-1

5、趟排序 flag=0; /假设本次没有交换 for (j=n-1; j>=i; j-) /第i 趟if ( Aj< Aj-1) flag=1; /出现交换x=Aj; Aj=Aj-1; Aj-1=x; if (flag=0) return; /快速排序void QuickSort(ElemType A, int s, int t) /递归算法，对区间As At 进行快速排序int i=s+1, j=t;ElemType temp, x = As; /第一个为基准元素while ( i<=j ) while ( i<=j && Ai<= x ) i+;

6、 /从左到右 while ( i<=j && Aj>=x) j-; /从右到左 if ( i < j ) temp=Ai; Ai=Aj; Aj=temp; i+; j-; if (s!=j) /交换基准元素 As=Aj; Aj=x; if (s<j-1) QuickSort(A, s, j-1); /处理左区间 if (j+1<t) QuickSort(A, j+1, t); /处理右区间void main() int i,j,n,N=5;cout<<"请输入个整数：" ElemType A5;for(j=0;j&l

7、t;N;j+)cin>>Aj;cout<<"排序前为："<<endl;for(i=0;i<N;i+)cout<<Ai<<endl;cout<<"直接插入排序:"<<endl;InsertSort (A, N );for(i=0;i<N;i+)cout<<Ai<<endl;运 /运行结果如右;cout<<"直接选择排序:"<<endl;SelectSort(A, N);for(i=0;i<N;i+)cout<<Ai<<endl; cout<<"堆排序:"<<endl;HeapSort(A, N); for(i=0;i<N;i+)cout<<Ai<<endl; cout<<"冒泡排序:"<<endl; BubbleSort(A, N); for(i=0;i<N;i+)cout<<Ai<