【文章內容簡介】 include includeiomanip//包含列表的函數 using namespace std。 int a[5],b[5],c[5]。//a[],b[],c[]分別記錄比較次數，交換次數，移動次數 ifstream outfile。 class SortableSList { public: SortableSList()。 void InsertSort()。 void SelectSort()。 void BubbleSort()。 void QuickSort()。 void MergeSort()。 void QuickSort(int left,int right)。 int QSort(int left,int right)。 void Merge(int left,int right1,int right2)。 int *I,*S,*Q,*B,*M。 int n。 }。 SortableSList::SortableSList() { printf( 輸入排序數字的個數 :\n)。 scanf(%d,amp。n)。 I=new int[n]。 //創(chuàng)建一個指向整型數據的數組 ,并將地址賦給指向整型數據的指針 S=new int[n]。 Q=new int[n]。 B=new int[n]。 M=new int[n]。 for(int i=0。in。i++) I[i]=S[i]=Q[i]=B[i]=M[i]=rand()。 //將隨機生成的資料寫入文件 ofstream infile。 ()。//將對象與文件關聯(lián) for(i=0。in。i++) { double w=I[i]。 infilew 。 } ()。 } void Swap(intamp。a,intamp。b)//交換函數 { int T=a。a=b。b=T。 } void SortableSList::InsertSort()//直接插入排序 { for(int i=1。in。i++) { int j=i。 int temp=I[i]。//將待插入元素存入 temp c[0]++。 while(j0amp。amp。tempI[j1]){//從后往前查找插入位置 a[0]++。 I[j]=I[j1]。j。 c[0]++。 } a[0]++。 I[j]=temp。//將待插入的元素存入找到的插入位置 } } void SortableSList::SelectSort()//簡單選擇排序 { int s。 for(int i=0。in1。i++){ s=i。 //假定待排序序列中的第一個元素最小 for(int j=i+1。jn。j++)//每趟掃描 ni1 次 a[1]++。 if(S[j]S[s]) s=j。//記下每次比較的較小元素的下標 Swap(S[i],S[s])。//最小元素與待排序序列的第一個交換 c[1]=c[1]+3,b[1]++。 } } void SortableSList::QuickSort()//快速排序 { QuickSort(0,n1)。 //以初始序列為待排序序列開始快速排序 } int SortableSList::QSort(int left,int right) { int i=left,j=right+1。 do{ //開始一趟快速排序， Q[left]作為分割元素 do { i++。 a[3]++。 }while(Q[i]Q[left])。 do { j。 a[3]++。 }while(Q[j]Q[left])。 if(ij) Swap(Q[i],Q[j]),b[3]++。 }while(ij)。 Swap(Q[left],Q[j])。 //交換分割元素 Q[left]和 Q[j]的位置 c[3]=c[3]+3,b[3]++。 return j。 } void SortableSList::QuickSort(int left,int right) { if(leftright){ int j=QSort(left,right)。 QuickSort(left,j1)。 //對低端序列快速排序 QuickSort(j+1,right)。 //對高端序列快速排序 } } void SortableSList::BubbleSort()//冒泡排序 { int i,j,last。 i=n1。 while(i0) { //最多進行 n1 趟 last=0。 //進入循環(huán)就將 last 置為 0 for(j=0。ji。j++)//從上往下進行比較 { if(B[j+1]B[j]) { Swap(B[j],B[j+1])。 c[2]=c[2]+3。 b[2]++。 last=j。 } a[2]++。 } i=last。 //如果沒有交換元素，則 last=0,退出循環(huán) } } //兩路合并排序 void SortableSList::Merge(int left,int right1,int right2)//兩路合并 { //right1,right2 分別為兩個子序列的上界 int*temp=new int[right2left+1]。 //創(chuàng)建存放兩個子序列的臨時數組 int i=left,j=right1+1,k=0。 //i,j 是兩個子序列的游動指針， k 是 temp 的游動指針 while((i=right1)amp。amp。(j=right2))//若兩個子序都不空，則循環(huán) { a[4]++。 if(M[i]=M[j]) //將 M[i],M[j]中較小的存入 temp[k] temp[k++]=M[i++],b[4]++。 else temp[k++]=M[j++],c[4]++,b[4]++。 } while(i=right1) //若第一個子序列還有剩余的就存入 temp temp[k++]=M[i++],c[4]++,b[4]++。 while(j=right2) //若第二個子序列還有剩余的就存入 temp temp[k++]=M[j++],c[4]++,b[4]++。 for(i=0,k=left。k=right2。) //將 temp 中的元素放回 M[k++]=temp[i++],c[4]++,b[4]++。 } void SortableSList::MergeSort()//合并排序 { int left,right2,right1。 int si