按照自己的理解寫的堆排序。感覺和二分有點像。時間復雜度n*log n。

#include <iostream> ? ?
using namespace std;
int n,arr[101];

void creatstack(int i) ? ? ?//大根堆。邊界問題。?
{
?? ?while(i!=1)
?? ?{
?? ??? ?if( arr[i]>arr[i/2] )
?? ??? ?{
?? ??? ??? ?swap(arr[i],arr[i/2]);
?? ??? ??? ?i=i/2;
?? ??? ?}?? ?
?? ??? ?else
?? ??? ??? ?break;
?? ?}
}
void stacksort(int N)
{
?? ?swap(arr[1],arr[N]); ? ?//之后就是從上往下了。?
?? ?int p=1;
?? ?while(p*2+1<N) ? ? ? ? ? ? ?//這里的問題。?
?? ?{
?? ??? ?if(arr[p*2]>arr[p*2+1]&&arr[p]<arr[p*2])
?? ??? ?{
?? ??? ??? ?swap(arr[p*2],arr[p]);
?? ??? ??? ?p=p*2;
?? ??? ?}
?? ??? ?else if(arr[p*2]<=arr[p*2+1]&&arr[p]<arr[p*2+1]) ? //這是進行保證了啊。?
?? ??? ?{
?? ??? ??? ?swap(arr[p*2+1],arr[p]);?? ??? ??? ??? ??? ??
?? ??? ??? ?p=p*2+1;
?? ??? ?}
?? ??? ?else
?? ??? ??? ?break; ?? ??? ??? ??? ??? ??? ??? ?//僅僅只是通過兩種可能來實現所有的情況。?
?? ??? ?if(arr[p]<arr[p*2]&&p*2+1==N)swap(arr[p],arr[p*2]);
?? ?}
?? ?if(arr[p]<arr[p*2]&&p*2+1==N)swap(arr[p],arr[p*2]);
}

int main()
{?
?? ?cout<<"請輸入數組的大小"<<endl;
?? ?cin>>n;
?? ?cout<<"請輸入數組中的值"<<endl;
?? ?for(int i=1;i<=n;i++)
?? ??? ?cin>>arr[i];
?? ?//初建堆。
?? ?for(int i=2;i<=n;i++)
?? ??? ?creatstack(i);
?? ?//堆排序。(從小到大進行排序)
?? ?for(int i=n;i>=2;i--) ? ??
?? ??? ?stacksort(i);?? ??? ??? ??? ?
?? ?for(int i=1;i<=n;i++)
?? ??? ?cout<<arr[i]<<" "; ? //大根堆，那就是從小到大進行排序吧。?? ??? ??? ??? ??? ??? ?
?? ?cout<<endl;
?? ?return 0;?? ?
}?

?

還有一種寫法，不過不太好。

#include <iostream> ? ? ?
using namespace std; ??
const int inf=101,themax=100;
int arr[inf];
int n;

void creatstack(int i) ? //小根堆.
{
?? ?while(i!=1)
?? ?{
?? ??? ?if( arr[i]<arr[i/2] ) ? //不對，就是一個的。所以是沒啥問題的。 ? ? ??
?? ??? ??? ?swap( arr[i],arr[i/2] );
?? ??? ?else
?? ??? ??? ?break;
?? ??? ?i=i/2;
?? ?}
}
int stacksort() ? ?//也許你可以從這方面來進行推導。用一共有幾層來進行約束應該好一點吧。?
{
?? ?arr[1]=themax;?? ??? ??? ?//對啊，既然通過層次不行，那就直接通過其他的方向吧。?? ? ?? ??? ?
?? ?int i=1;?? ??? ??? ??? ?//其實直接通過個數來限定會更好一點。?? ??? ??? ??
?? ?while(1)
?? ?{
?? ??? ?if(arr[i]==arr[i*2] && arr[i]==arr[i*2+1]) ??
?? ??? ??? ?break;
?? ??? ?if(arr[i*2]>arr[i*2+1])
?? ??? ?{
?? ??? ??? ?swap(arr[i],arr[i*2+1]);
?? ??? ??? ?i=i*2+1;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?swap(arr[i],arr[i*2]);
?? ??? ??? ?i=i*2;
?? ??? ?}?? ??? ?
?? ?}
?? ?return arr[1];?? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ?
}

int main()
{
?? ?for(int i=0;i<inf;i++)
?? ??? ?arr[i]=themax;
?? ?cout<<"請輸入數組的大小"<<endl;
?? ?cin>>n;?? ?
?? ?cout<<"請輸入數組中的值"<<endl;
?? ?for(int i=1;i<=n;i++) ? ??? ? ? ??? ?
?? ?{
?? ??? ?cin>>arr[i];?? ?
?? ?}?? ??
?? ?for(int i=2;i<=n;i++)
?? ?{
?? ??? ?creatstack(i);?? ?
?? ?}?
?? ?//初建堆應該是可以的，之后就是進行排序了。
?? ?int ans[inf],k=1,tran=arr[1];?? ?//是最小的。?
?? ?for(int i=1;i<=n;i++)
?? ?{
?? ??? ?ans[k++]=tran;
?? ??? ?tran=stacksort();
?? ?}
?? ?for(int i=1;i<=n;i++)
?? ??? ?cout<<ans[i]<<" ";
?? ?cout<<endl;
?? ?return 0;?? ?
}?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的堆排序(二分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。