Một số phương pháp sắp xếp cơ bản

Trong bài này tôi sẽ hướng dẫn các bạn học lập trình java một số cách sắp xếp cơ bản

1.Sắp xếp:

- Sắp xếp(sorting): Quá trình bố trí lại các phần tử theo một thứ tự ấn định.
- bài toán đặt ra ở đây là sắp xếp với một bảng gồm n Records(bản ghi: gồm nhiều trường dữ liệu tương ứng với nhiều thuộc tính khác nhau) R1, R2,...Rn.
- Trong sắp xếp chỉ có một trường nào đó của dữ liệu được để ý đến, và ta sẽ gọi trường này là các khóa, sắp sếp tiến hành dựa vào giá trị của các khóa này. Do trong quá trình sắp xêp chỉ thao tác trên một trường các trường khác phải giữ nguyên nên ta sẽ sao chép các khóa vào trong một bảng mỗi khóa tương ứng với một bản ghi của nó.Như vậy trong quá trình sắp xếp, bản ghi chính sẽ không có vấn đề gì.

2.Một số phương pháp sắp xếp cơ bản:

1.Sắp xếp kiểu lựa chọn:
- Ta có một bảng gồm 9 khóa: 1,3,7,2,4,6,9,8,5.
- Nguyên tắc của việc sắp xếp này là ở lượt thứ i ( 1<= i <= n) ta sẽ chọn trong dãy khóa Ki,Ki+1...Knkhóa nhỏ nhất và đổi chỗ nó với Ki.
 

Giải thuật để sắp xếp:
1.For i = 1 to n-1 do
m=i (M là chỉ số phần tử bé nhất)
2 For j=i+1 to n
if K[m]>K[j] m=j;
if K[m]<K then (đổi chỗ)
X=K
K=K[m]
K[m]=X.

- Đây là code ví dụ viết bằng java:

PHP:

package VI_DU;



public class Selecton_sort {
public static void main(String [] args){int i, a[] = {1,3,7,2,4,6,9,8,5};
for(i = 0;i<8;i++){int m=i;
for(int j=i+1; j<9; j++ ){

if(a[j]<a[m]){m=j;
}
if(a[m]<a[i]){int X=a[m];a[m]=a[i];a[i]=X;
}
}
}



for (i=0;i<9;i++){System.out.print(a[i]);
}

}


}

2.Sắp xếp kiểu thêm dần:

- Nguyên tắc: Coi phần tử K1 là khóa sau đó xét thêm các phần tử K2 để so sánh và tìm chỗ chèn đằng trước hay sau K1, đối với K3 thì so sánh vs K2 K1 cứ tiếp tục với K4,K5...
- Thuật toán:
Dùng X làm ô nhớ phụ chứa khóa được xét đến, Ta có một khóa là K[0] nhở hơn tất cả các phần tử của mảng.

1. K[0] = - âm vô cùng
2. For i=2 to n
3. {
4. X= K; j = i-1;
   [*]While X < K[j]
   [*]{
   [*]K[j+1] = K[j]
   [*]j=j-1
   [*]}
   [*]K[j+1] = X
   [*]}

Dưới đây là code viết bằng java:

PHP:

package VI_DU;



public class Insertion_Sort {
public static void main(String [] args){int i, a[] = {0,1,3,7,2,4,6,9,8,5,};

for(i = 2;i<10;i++){int X = a[i];
    int j = i-1;

while(X < a[j]){a[j+1] = a[j];j= j-1;

}a[j+1]=X;
}



for (i=1;i<10;i++){System.out.print(a[i]);
}

}


}

3.Sắp xếp kiểu đổi chỗ (nổi bọt)

- Nguyên tắc khi hai khóa kế cận ngược thứ tự thì đổi chỗ cho nhau

Đây là thuật toán:

1. for i=0 to n{
2. for j=1 to n{
3. if K[j-1]>K then
   [*]X=K[j]
   [*]K[j]=K[j+1]
   [*]K[j+1]=X
   [*]}
   [*]}

- Đây là phương pháp sắp xếp hay dùng.
Code java:

PHP:

package VI_DU;



public class Bubble_Sort {
public static void main(String [] args){int i, a[] ={1,3,7,2,4,6,9,8,5};

for(i = 0;i<9;i++){
for(int j=1;j<9;j++){
if(a[j-1]>a[j]){int X=a[j];a[j]=a[j-1];a[j-1]=X;
}
}
}

for (i=0;i<9;i++){System.out.print(a[i]);
}

}


}