4 sorft
1 Thuật giải nổi bọt (Bubble Sort)
+ Bước 1: Gán i=0;
+ Bước 2: Gán j= n-1;
+ Bước 3: Trong khi j > i thực hiện:
- Nếu a [ j ] < a [ j-1 ] : đổi chổ a [ j ] a[ j-1] ;
- Gán j = j -1;
+ Bước 4:
- Nếu i<=n thì i = i +1.
Quay lại bước 2.
- Ngược lại thì dừng.
void BubbleSort ( int a[ ], int n)
{
int i,j;
for ( i = 0; i<n-1; i++)
for ( j=n-1; j>i; j--)
if ( a [ j ] < a [ j-1] )
DoiCho( a[ j ] , a[ j-1] );
}
2 Thuật giải đổi chổ trực tiếp (Interchange Sort)
+ Bước 1: Gán i=0;
+ Bước 2: Gán j= i + 1;
+ Bước 3: Trong khi j <= n thực hiện:
- Nếu a [ j ] < a [ i ] : đổi chổ a [ j ] a[ i ] ;
- Gán j = j +1;
+ Bước 4:
- Nếu i<n thì i = i +1.
Quay lại bước 2.
- Ngược lại thì dừng.
void InterchangeSort ( int a[ ], int n)
{
int i,,j;
for ( i = 0; i<n-1; i++)
for ( j=i+1; j<n; j++)
if ( a [ j ] < a [ i] )
DoiCho( a[ i ] , a[ j ] );
}
3 Thuật giải chọn trực tiếp (Selection Sort)
+ Bước 1: Gán i=0;
+ Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy từ
a[ i ] a[n-1];
+ Bước 3: Đổi chổ a [min] a[ i ];
+ Bước 4:
- Nếu i<=n thì i = i +1.
Quay lại bước 2.
- Ngược lại thì dừng.
void SelectionSort ( int a[ ], int n)
{
int min;
for(int i=0;i<n-1;i++)
{
min =i;
for(int j=i+1;j<n;j++)
if(a[ j ]<a[min])
min = j;
DoiCho(a[min],a[ i ]);
}
}
4 Thuật giải chèn trực tiếp (Insertion Sort)
+ Bước 1: Gán i=1;
+ Bước 2: Gán x = a[ i ]. Tìm vị trí pos thích hợp trong đoạn từ a[ 0 ] a[i-1] để chèn x vào;
+ Bước 3: Tiến hành dời chổ các phần tử lớn hơn x sang phải 1 vị trí để chèn x vào, a [pos] = x. Tiến hành chèn x;
+ Bước 4:
- Nếu i<=n thì i = i +1.
Quay lại bước 2.
- Ngược lại thì dừng.
void InsertionSort ( int a[ ], int n)
{
int x,pos;
for ( int i = 1; i<n; i++)
{
x = a[ i ];
pos = i -1;
while( pos>=0 && a[pos]>x)
{
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x;
}
}
Bạn đang đọc truyện trên: Truyen2U.Com