#include<iostream.h> void swap(int &a, int &b) //實現a、b兩個數據元素的簡單交換 { int t=a; a=b; b=t; } void swap(int &a, int &b, int &c) //實現三個元素最少交換次數的交換，使得a <= b <= c;其功能實現可由可由三個元素交換的分類討論中得到 { if((a>=b && b>c) || (a>b && b==c)) swap(a, c); else if(a>b && b<c) { if(a<=c) swap(a,b); else { swap(a,b); swap(b, c);} } else if(a<b && b>c) { if(a<=c) swap(b, c); else { swap(b, c); swap(a, b);} } } void swap(int A[], int a, int b, int c) //此函數實現轉換功能，將數組調用簡化為簡單三個元素的比較交換 { swap(A[a], A[b], A[c]); } int sortcheck(int A[], int n) //實現進位，並以返回值表示是否已經完成排序 { int check=0; for(int i=0; i+1<n; i+=2) { if(A[i]>A[i+1]){ swap(A[i], A[i+1]); check++;} //1步 if(i+2<n && A[i+1]>A[i+2]) check++; //2步 } return check; } void sort(int A[], int n, int r=1) //實現二叉排序，主要對2步的對應元素排序 { //其基本思想是將數組A的地址視作二叉樹，通過對二叉樹的排序實現功能，使 R <= L <= R 根節點值小於左子樹值小於右子樹值 if(2*r+1<=n) { swap(A, r-1, 2*r-1, 2*r); sort(A, n, 2*r); sort(A, n, 2*r+1); swap(A, r-1, 2*r-1, 2*r); //此步為回溯算法，在左右子樹子排序完成後對根結點重新排序 } else if(2*r==n && A[r-1]>A[2*r-1]) swap(A[r-1],A[2*r-1]); } int Sort(int A[], int n) //此函數用於將排序總體包裝方便調用 { int count=0; while(sortcheck(A, n)) //當排序未完成對1組的排序， { int r=1; sort(A, n, r); //並調用2組排序 count ++; } return count; //以count的返回值可知兩組排序一起結合工作被調用的次數 } void BinarySort(int A[], int n) { cout<<endl<<"排序前數組為："<<endl; for(int i=0; i<n; i++)cout<<A[i]<<" "; cout<<endl; cout<<endl<<"本次排序共經歷"<<Sort(A,n)<<"個周期，參與排序排序元素"<<n<<"個"<<endl; cout<<endl<<"排序後數組為："<<endl; for(i=0; i<n; i++)cout<<A[i]<<" "; cout<<endl; } void main() { int A[35]={34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0}; BinarySort(A, 35); }
