dokylan
Đại Tướng
Posts : 1456
Điểm Số : 4289
Join date : 24/08/2010
Age : 32
Đến từ : Cà Mau
 |  Tiêu đề: Các thuật toán sắp xếp mảng thông dụng  18/09/10, 04:06 pm | |
|
- Selection Sort - Sắp xếp kiểu chọn
Giải thuật:
Đây là phương pháp sắp xếp đơn giản nhất được tiến hành như sau:
-
Đầu tiên chọn phần tử nhỏ nhất trong n phần tử từ danh sách X[1]…X[n] và hoán vị nó với phần tử X[1].
-
Chọn phần tử có khóa nhỏ nhất trong n-1phần tử từ danh sách X[2]… X[n] và hoán vị nó với X[2].
-
Tổng quát ở bước thứ i, chọn phần tử có khoá nhỏ nhất trong n-i+1 phần tử từ danh sách X(i)… X(n) và hoán vị nó với X(i).
Sau n-1 bước này thì mảng đã được sắp xếp.
Phươngpháp này được gọi là phương pháp chọn bởi vì nó lặp lại quá trình chọnphần tử nhỏ nhất trong số các phần tử chưa được sắp.
Dưới đây là mã VB.NET
Sub SelectionSort(ByRef X() As Integer)Dim i, j,SmallPos, Smallest As IntegerFor i = 0 To X.Length - 2'Chon phan tu Mintrong danh sach con X(i)..X(n)SmallPos = iSmallest = X(i)For j = i + 1To X.Length - 1If X(j) < Smallest ThenSmallPos = jSmallest =X(SmallPos)End IfNext'Doi cho phan tu dau tien cua ds con voiMinX(SmallPos) = X(i)X(i) = SmallestNextEnd Sub
- Insertion Sort - Sắp xếp kiểu chèn
Vấn đề:
Sắp thứ tự các phần tử của một danh sách:
X1, X2,…, Xn
Sao cho (theo một trường khóa nào đó) chúng có thứ tự tăng dần:
X1 ≤ X2 ≤ … ≤ Xn
Hoặc có thứ tự giảm dần:
X1 ≥ X2 ≥ … ≥ Xn
Giải thuật :
- Bước 1, xen phần tử X[2] vào danh sách đã có thứ tự X[1] sao cho X[1], X[2] là một danh sách có thứ tự.
- Bước 2, xen phần tử X[3] vào danh sách đã có thứ tự X[1], X[2] sao cho X[1], X[2], X[3] là một danh sách có thứ tự.
- Tổng quát, bước i, xen phần tử X[i+1] vào danh sách đã có thứ tự X[1],X[2],..X sao cho X[1], X[2],.. X[i+1] là một danh sách có thứ tự.
- Phần tử đang xét X[j] sẽ được xen vào vị trí thích hợp trongdanh sách các phần tử đã được sắp trước đó X[1],X[2],..X[j-1] bằng cáchso sánh khoá của X[j] với khoá của X[j-1] đứng ngay trước nó. Nếu khoácủa X[j] nhỏ hơn khoá của X[j-1] thì hoán đổi X[j-1] và X[j] cho nhauvà tiếp tục so sánh khoá của X[j-1] (lúc này X[j-1] chứa nội dung củaX[j]) với khoá của X[j-2] đứng ngay trước nó...
[i]Dưới đây là mã VB.NET:
Sub InsertionSort(ByRef X() As Integer)Dim j As IntegerDimNextElement As IntegerFor i As Integer = 1 To X.Length - 1NextElement =X(i)j = i - 1While j >= 0 AndAlso NextElement < X(j)X(j + 1) =X(j)j -= 1End WhileX(j + 1) = NextElementNextEnd Sub
- Bubble Sort - Sắp xếp nỗi bọt
Vấn đề:
Sắp thứ tự các phần tử của một danh sách:
X1, X2,…, Xn
Sao cho (theo một trường khóa nào đó) chúng có thứ tự tăng dần:
X1 ≤ X2 ≤ … ≤ Xn
Hoặc có thứ tự giảm dần:
X1 ≥ X2 ≥ … ≥ Xn
Sắpxếp kiểu Nổi bọt (bubble sort) là một giải thuật sắp xếp đơn giản. Nólặp đi lặp lại quá trình duyệt danh sách cần sắp xếp, so sánh hai phầntử và đổi vị trí nếu chúng đứng sai vị trí.
Giải thuật như sau:
1.So sánh 2 phần tử cạnh nhau. Nếu phần tử trước lớn hơn phần tử sau thì đổi vị trí (swap) của chúng cho nhau.
2.Thựchiện việc đó với mỗi cặp phần tử., từ cặp đầu tiên tới cặp cuối cùng.Tới thời điểm này, phần tử cuối cùng sẽ là phần tử có giá trị lớn nhất.
3.Lặp lại các bước trên với các phần tử trừ phần tử cuối cùng. Cho tới khi không còn cặp nào cần so sánh. function bubblesort (A : list[1..n]) {var int i, j;for i from ndownto 1 {for j from 1 to i-1 { if (A[j] > A[j+1])swap(A[j],A[j+1])}}}
Bubble Sort thực hiện tối đa (n-1) lần duyệt danhsách. Lần đầu tiên nó so sánh (n-1) cặp phần tử và kq là phần tử lớnnhất di chuyển về cuối danh sách. Lần thứ hai nó thực hiện (n-2) phépso sánh.
Do đó, trong trường hợp tồi nhất giải thuật thực hiện số lần là
(n-1)+(n-2) + . . . . . . . .+2+1 = n*(n-2)/2=O(n2)
Độ phức tạp của giải thuật là O(n2)
Dưới đây là mã VB.NET
Sub BubbleSort(ByRef arr() As Integer)Dim i, j AsIntegeri = arr.Length While i > 0For j = 0 To i - 2If arr(j) >arr(j + 1) ThenSwap(arr(j), arr(j + 1))End IfNexti -= 1End WhileEndSub'This will swap a and b. We pass By Reference because we want toaffect a and b.Sub Swap(ByRef a As Integer, ByRef b As Integer)Dim tempAs Integertemp = aa = bb = tempEnd Sub | |
|
