truclinhcao2008 Nhập Môn
Tổng số bài gửi : 12 Join date : 20/10/2009
| Tiêu đề: Thuật toán sắp xếp nâng cao Mon Nov 23, 2009 7:42 am | |
| | | | | // Thuật toán HeapSort #include<stdio.h> #include<conio.h> #include<stdlib.h> void Hoanvi(int &a,int &b) { int tmp=a; a=b; b=tmp; } void Shift (int a[ ], int l, int r ) { int x,i,j; i = l; j =2*i; // (ai , aj ), (ai , aj+1) là các phan tu lien doi int isHeap=0; x = a[i]; while ((j<=r) && !isHeap)//&&(cont)) {
if (j<r) // neu co du 2 phan tu lien doi if (a[j]<a[j+1])// xac dinh phan tu lien doi lon nhat j = j+1; if (a[j]<=x) isHeap=1;//return;//exit(1);// thoa quan he lien doi else { a[i] = a[j]; i = j; // xet tiep kha nang hieu chinh lan truyen j = 2*i; a[i] = x; }
} }
void CreateHeap(int a[], int N ) { int l; l = (N-1)/2; // a[l] la phan tu ghep them while (l >= 0) { Shift(a,l,N-1); l = l -1; } }
void HeapSort (int a[], int N) { int r;
CreateHeap(a,N); r = N-1; // r là v? trí dúng cho ph?n t? nh? nh?t while(r > 0) //do { Hoanvi(a[0],a[r]); r = r -1; Shift(a,0,r); } }
void Xuat(int a[], int n) { for(int i=0;i<n;i++) printf("%d \t",a[i]); }
void main() { clrscr(); //int a[]={12,2,8,5,1,6,4,15}; // int a[]={62,22,8,5,1,16,54,15}; int a[]={3,2,7,6}; int n=4; HeapSort(a,n); Xuat(a,n); getch();
}
// thuật toán quicksort #include<iostream.h> #include<conio.h> #define max 100 void NhapMang(int A[max],int n){ for(int i=0;i<n;i++){ cout<<"nhap Phan tu thu A["<<i<<"] ="; cin>>A[i]; } } void XuatMang(int A[max],int n){ cout<<endl; for(int i=0;i<n;i++) cout<<A[i]<<"\t"; } void Swap(int &a,int &b){ int temp; temp=a; a=b; b=temp; return; } void QuickSort(int A[max],int l,int r){ int i,j; int x; x=A[(l+r)/2]; i=l; j=r; do{ while(A[i]<x) i++; while(A[j]>x) j--; if(i<=j){ Swap(A[i],A[j]); i++; j--; } }while(i<j); if(l<j) QuickSort(A,l,j); if(i<r) QuickSort(A,i,r); } void main(){ int A[max],n; clrscr(); cout<<"Nhap so phan tu:"; cin>>n; cout<<endl; NhapMang(A,n); cout<<endl; cout<<"mang vua nhap la:"; XuatMang(A,n); cout<<endl; QuickSort(A,0,n-1); cout<<"\n mang vua sap xep la:"; cout<<endl; XuatMang(A,n); getch(); } | | | | |
|
|