【c++版】直接选择排序法-直接插入排序法、快速排序法、堆排序法、冒泡排序发-实验

#includeiostreamusingnamespacestd;typedefintElemType;//直接插入排序voidInsertSort(ElemTypeA[],intn){inti,j;ElemTypex;for(i=1;in;i++){//进行n-1次插入x=A[i];//准备插入第i个元素for(j=i-1;j=0;j--){//从第i-1个开始往前找插入点if(xA[j])A[j+1]=A[j];elsebreak;}A[j+1]=x;//插入}}//直接选择排序voidSelectSort(ElemTypeA[],intn){inti,j,k;ElemTypex;for(i=0;i=n-2;i++){//每一趟选择最小元素并与A[i]交换k=i;for(j=i+1;j=n-1;j++)//查找最小元素的下标if(A[j]A[k])k=j;if(k!=i){//交换x=A[i];A[i]=A[k];A[k]=x;}}}//堆排序voidSift(ElemTypeA[],intn,inti);voidCreatHeap(ElemTypeA[],intn){inti;for(i=(n-2)/2;i=0;i--)Sift(A,n,i);//调整A[i..n-1]使之为一个堆}voidSift(ElemTypeA[],intn,inti){//调整A[i..n-1]成为一个堆（它的左右子树已是一个堆）ElemTypex=A[i];intj=2*i+1;//j为i的左孩子while(j=n-1){//i有左子树if(j+1n&&A[j]A[j+1])j++;//使j指向左右孩子中排序码大的孩子if(xA[j]){//将A[j]上移，以便向下筛A[i]=A[j];i=j;j=2*i+1;}elsebreak;}A[i]=x;}voidHeapSort(ElemTypeA[],intn){//A为待排序表，n为表的长度inti;ElemTypex;CreatHeap(A,n);//把A建成一个堆for(i=n-1;i=1;i--){x=A[0];//第个元素与第i个元素交换A[0]=A[i];A[i]=x;Sift(A,i,0);//调整A[0..i-1]使之为一个堆}}//冒泡排序voidBubbleSort(ElemTypeA[],intn){inti,j,flag;//flag为交换标记ElemTypex;for(i=1;i=n-1;i++){//最多n-1趟排序flag=0;//假设本次没有交换for(j=n-1;j=i;j--)//第i趟if(A[j]A[j-1]){flag=1;//出现交换x=A[j];A[j]=A[j-1];A[j-1]=x;}if(flag==0)return;}}//快速排序voidQuickSort(ElemTypeA[],ints,intt){//递归算法，对区间A[s]～A[t]进行快速排序inti=s+1,j=t;ElemTypetemp,x=A[s];//第一个为基准元素while(i=j){while(i=j&&A[i]=x)i++;//从左到右while(i=j&&A[j]=x)j--;//从右到左if(ij){temp=A[i];A[i]=A[j];A[j]=temp;i++;j--;}}if(s!=j){//交换基准元素A[s]=A[j];A[j]=x;}if(sj-1)QuickSort(A,s,j-1);//处理左区间if(j+1t)QuickSort(A,j+1,t);//处理右区间}voidmain(){inti,j,n,N=5;cout请输入个整数：;ElemTypeA[5];for(j=0;jN;j++)cinA[j];cout排序前为：endl;for(i=0;iN;i++)coutA[i]endl;cout直接插入排序:endl;InsertSort(A,N);for(i=0;iN;i++)coutA[i]endl;运//运行结果如右;cout直接选择排序:endl;SelectSort(A,N);for(i=0;iN;i++)coutA[i]endl;cout堆排序:endl;HeapSort(A,N);for(i=0;iN;i++)coutA[i]endl;cout冒泡排序:endl;BubbleSort(A,N);for(i=0;iN;i++)coutA[i]endl;cout快速排序:endl;QuickSort(A,0,1);for(i=0;iN;i++)coutA[i]endl;}