các bạn có thể tham khảo các bài khác tại cơ sở dữ liệu và giải thuật
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...kn khóa nhỏ nhất và đổi chỗ nó với ki.


android.vn/attachments/untitled-copy-png.117481/" border="0" alt="" />



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:


Mã nguồn PHP:
[color=#000000]
package vi_du[/color][color=#007700]; public class [/color][color=#0000bb]selecton_sort [/color][color=#007700]{public static [/color][color=#0000bb]void main[/color][color=#007700]([/color][color=#0000bb]string [/color][color=#007700][] [/color][color=#0000bb]args[/color][color=#007700]){[/color][color=#0000bb]int i[/color][color=#007700], [/color][color=#0000bb]a[/color][color=#007700][] = {[/color][color=#0000bb]1[/color][color=#007700],[/color][color=#0000bb]3[/color][color=#007700],[/color][color=#0000bb]7[/color][color=#007700],[/color][color=#0000bb]2[/color][color=#007700],[/color][color=#0000bb]4[/color][color=#007700],[/color][color=#0000bb]6[/color][color=#007700],[/color][color=#0000bb]9[/color][color=#007700],[/color][color=#0000bb]8[/color][color=#007700],[/color][color=#0000bb]5[/color][color=#007700]};for([/color][color=#0000bb]i [/color][color=#007700]= [/color][color=#0000bb]0[/color][color=#007700];[/color][color=#0000bb]i[/color][color=#007700]<[/color][color=#0000bb]8[/color][color=#007700];[/color][color=#0000bb]i[/color][color=#007700]++){[/color][color=#0000bb]int m[/color][color=#007700]=[/color][color=#0000bb]i[/color][color=#007700];for([/color][color=#0000bb]int j[/color][color=#007700]=[/color][color=#0000bb]i[/color][color=#007700]+[/color][color=#0000bb]1[/color][color=#007700]; [/color][color=#0000bb]j[/color][color=#007700]<[/color][color=#0000bb]9[/color][color=#007700]; [/color][color=#0000bb]j[/color][color=#007700]++ ){ if([/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]j[/color][color=#007700]]<[/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]m[/color][color=#007700]]){[/color][color=#0000bb]m[/color][color=#007700]=[/color][color=#0000bb]j[/color][color=#007700];}if([/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]m[/color][color=#007700]]<[/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]i[/color][color=#007700]]){[/color][color=#0000bb]int x[/color][color=#007700]=[/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]m[/color][color=#007700]];[/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]m[/color][color=#007700]]=[/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]i[/color][color=#007700]];[/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]i[/color][color=#007700]]=[/color][color=#0000bb]x[/color][color=#007700];}}} for ([/color][color=#0000bb]i[/color][color=#007700]=[/color][color=#0000bb]0[/color][color=#007700];[/color][color=#0000bb]i[/color][color=#007700]<[/color][color=#0000bb]9[/color][color=#007700];[/color][color=#0000bb]i[/color][color=#007700]++){[/color][color=#0000bb]system[/color][color=#007700].[/color][color=#0000bb]out[/color][color=#007700].print([/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]i[/color][color=#007700]]);} } }[/color] 
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.
  • k[0] = - âm vô cùng
  • for i=2 to n
  • {
  • 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:


Mã nguồn PHP:
[color=#000000]
package vi_du[/color][color=#007700]; public class [/color][color=#0000bb]insertion_sort [/color][color=#007700]{public static [/color][color=#0000bb]void main[/color][color=#007700]([/color][color=#0000bb]string [/color][color=#007700][] [/color][color=#0000bb]args[/color][color=#007700]){[/color][color=#0000bb]int i[/color][color=#007700], [/color][color=#0000bb]a[/color][color=#007700][] = {[/color][color=#0000bb]0[/color][color=#007700],[/color][color=#0000bb]1[/color][color=#007700],[/color][color=#0000bb]3[/color][color=#007700],[/color][color=#0000bb]7[/color][color=#007700],[/color][color=#0000bb]2[/color][color=#007700],[/color][color=#0000bb]4[/color][color=#007700],[/color][color=#0000bb]6[/color][color=#007700],[/color][color=#0000bb]9[/color][color=#007700],[/color][color=#0000bb]8[/color][color=#007700],[/color][color=#0000bb]5[/color][color=#007700],}; for([/color][color=#0000bb]i [/color][color=#007700]= [/color][color=#0000bb]2[/color][color=#007700];[/color][color=#0000bb]i[/color][color=#007700]<[/color][color=#0000bb]10[/color][color=#007700];[/color][color=#0000bb]i[/color][color=#007700]++){[/color][color=#0000bb]int x [/color][color=#007700]= [/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]i[/color][color=#007700]]; [/color][color=#0000bb]int j [/color][color=#007700]= [/color][color=#0000bb]i[/color][color=#007700]-[/color][color=#0000bb]1[/color][color=#007700]; while([/color][color=#0000bb]x [/color][color=#007700]< [/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]j[/color][color=#007700]]){[/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]j[/color][color=#007700]+[/color][color=#0000bb]1[/color][color=#007700]] = [/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]j[/color][color=#007700]];[/color][color=#0000bb]j[/color][color=#007700]= [/color][color=#0000bb]j[/color][color=#007700]-[/color][color=#0000bb]1[/color][color=#007700]; }[/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]j[/color][color=#007700]+[/color][color=#0000bb]1[/color][color=#007700]]=[/color][color=#0000bb]x[/color][color=#007700];} for ([/color][color=#0000bb]i[/color][color=#007700]=[/color][color=#0000bb]1[/color][color=#007700];[/color][color=#0000bb]i[/color][color=#007700]<[/color][color=#0000bb]10[/color][color=#007700];[/color][color=#0000bb]i[/color][color=#007700]++){[/color][color=#0000bb]system[/color][color=#007700].[/color][color=#0000bb]out[/color][color=#007700].print([/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]i[/color][color=#007700]]);} } }[/color] 
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:
  • for i=0 to n{
  • for j=1 to n{
  • 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:


Mã nguồn PHP:
[color=#000000]
package vi_du[/color][color=#007700]; public class [/color][color=#0000bb]bubble_sort [/color][color=#007700]{public static [/color][color=#0000bb]void main[/color][color=#007700]([/color][color=#0000bb]string [/color][color=#007700][] [/color][color=#0000bb]args[/color][color=#007700]){[/color][color=#0000bb]int i[/color][color=#007700], [/color][color=#0000bb]a[/color][color=#007700][] ={[/color][color=#0000bb]1[/color][color=#007700],[/color][color=#0000bb]3[/color][color=#007700],[/color][color=#0000bb]7[/color][color=#007700],[/color][color=#0000bb]2[/color][color=#007700],[/color][color=#0000bb]4[/color][color=#007700],[/color][color=#0000bb]6[/color][color=#007700],[/color][color=#0000bb]9[/color][color=#007700],[/color][color=#0000bb]8[/color][color=#007700],[/color][color=#0000bb]5[/color][color=#007700]}; for([/color][color=#0000bb]i [/color][color=#007700]= [/color][color=#0000bb]0[/color][color=#007700];[/color][color=#0000bb]i[/color][color=#007700]<[/color][color=#0000bb]9[/color][color=#007700];[/color][color=#0000bb]i[/color][color=#007700]++){for([/color][color=#0000bb]int j[/color][color=#007700]=[/color][color=#0000bb]1[/color][color=#007700];[/color][color=#0000bb]j[/color][color=#007700]<[/color][color=#0000bb]9[/color][color=#007700];[/color][color=#0000bb]j[/color][color=#007700]++){if([/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]j[/color][color=#007700]-[/color][color=#0000bb]1[/color][color=#007700]]>[/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]j[/color][color=#007700]]){[/color][color=#0000bb]int x[/color][color=#007700]=[/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]j[/color][color=#007700]];[/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]j[/color][color=#007700]]=[/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]j[/color][color=#007700]-[/color][color=#0000bb]1[/color][color=#007700]];[/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]j[/color][color=#007700]-[/color][color=#0000bb]1[/color][color=#007700]]=[/color][color=#0000bb]x[/color][color=#007700];}}} for ([/color][color=#0000bb]i[/color][color=#007700]=[/color][color=#0000bb]0[/color][color=#007700];[/color][color=#0000bb]i[/color][color=#007700]<[/color][color=#0000bb]9[/color][color=#007700];[/color][color=#0000bb]i[/color][color=#007700]++){[/color][color=#0000bb]system[/color][color=#007700].[/color][color=#0000bb]out[/color][color=#007700].print([/color][color=#0000bb]a[/color][color=#007700][[/color][color=#0000bb]i[/color][color=#007700]]);} } }[/color] 
bài tập: 1. tính số lượng phép chuyển chỗ trong trong hai truowng hợp thuận lợi nhất và xấu nhất đối với 3 giải thuật sắp xếp cơ bản trên
2. thay đổi 3 giải thuật trên với sắp xếp theo thứ tự số giảm dần.

các bạn nên tìm hiểu nhiều bài tập để nâng cao thêm trình độ
chúc các bạn thành công.

có gì thắc mắc các bạn có thể liên hệ facebook mình:http://www.facebook.com/linh193