#include<iostream> using namespace std; #define n 5 //代排序的个数 typedef int AnyType;//数据类型 struct RecType { int key; AnyType other;//记录其他数据域 }; RecType R[n+1];//R[0]用作监视哨 void CreateRecType(RecType R[]) { cout<<"最多输入"<<n<<"个数"<<endl; cout<<"请输入键值与对应数据"<<endl; int key,other,i=1; while(i<n+1) { cin>>key>>other; R[i].key=key; R[i].other=other; i++; } cout<<"输入成功！！"<<endl; } void showData(RecType R[]) { for(int i=1;i<n+1;i++) { cout<<R[i].key<<" "<<R[i].other<<endl; } } //1.冒泡排序 void MaopaoSort(RecType R[],int num) { int i=num,lastExchange; RecType temp; while(i>1) { lastExchange=1; for(int j=0;j<i;j++) { if(R[j].key>R[j+1].key) { temp=R[j]; R[j]=R[j+1]; R[j+1]=temp; lastExchange=j; } } i=lastExchange; } } //2. 快速排序 //a.分块 int Partition(RecType R[],int low,int high) { R[0]=R[low]; int pivotkey=R[low].key; while(low<high) { while(low<high && R[high].key>=pivotkey) high--; R[low]=R[high]; while(low<high && R[low].key<=pivotkey) low++; R[high]=R[low]; } R[low]=R[0]; return low; } //b.Qsort void QSort(RecType R[],int low,int high) { if(low<high-1) { int location=Partition(R,low,high); QSort(R,low,location-1); QSort(R,location+1,high); } } void QuickSort(RecType R[] ,int num) { QSort(R,1,num); } //3.直接选择排序 void SelectSort(RecType R[],int num) { RecType temp; for(int i=1;i<num;i++) { int k=i; for(int j=i+1;j<=num;j++) { if(R[j].key<R[k].key) k=j; if(i!=k) { temp=R[i]; R[i]=R[k]; R[k]=temp; } } } } //4.直接插入排序 void InsertSort(RecType R[] ,int num) { for(int i=2;i<=num;i++)//假定第一个记录有序 { R[0]=R[i]; int j=i-1; while(R[0].key<R[j].key) { R[j+1]=R[j]; j--; } R[j+1]=R[0]; } } int main() { CreateRecType(R); showData(R); InsertSort(R,n); cout<<"排序后的结果："<<endl; showData(R); return 0; }
