thucnq

Ý tưởng
Ta chọn một phần tử bất kỳ của mảng A giả sử đó là x
Lọc và chia mảng đó thành 3 mảng con:
- mảng A1: A1(i) < x với mọi i
- mảng A2: A2(i) = x với mọi i
- mảng A3: A3(i) > x với mọi i
Sau đó ta lại tiếp tục các bước trên với mảng A1 và A3. Công việc này còn được gọi là phân hoạch nên Quick Sort còn được gọi là sắp xếp theo phương pháp phân hoạch
Giải thuật này sẽ được cài đặt theo phương pháp đệ qui
Mô tả thuật toán
- Input: Mảng A[1..n]
- Output: Mảng A có thứ tự tăng dần
- Method: Mã:
function quickSort(A, lower, upper){
x = A[(lower + upper) / 2];
i = lower;
j = upper;
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 (j > lower)
quickSort(A, lower, j);
if (i < upper)
quickSort(A, i, upper);
}

Độ phức tạp tính toán: O(nlnn)
Thuật toán Quick Sort tốt nhất trong trường hợp dãy hầu như được sắp xếp và với n khá lớn. Vì vậy ta thường dung Quick Sort trong giai đoạn đầu để phân hoạch, khi đoạn con đủ nhỏ ta sẽ dùng các phương pháp khác để sắp xếp

bài này sưu tầm lại của My Love, đã post trong mục VB.Net : http://www.laptrinhviet.com/vb-net/1...hong-dung.html

Copy this link and send via YM,MSN,AOL,ICQ..... Thuật toán sắp xếp nhanh Quick sort http://www.laptrinhviet.com/showthread.php?t=19827 Hãy gửi link này cho bạn bè trong list của bạn giúp mình nhé ;) thank nhiều

Super Chicken

Ke ke, My love là ai thế nhỉ

Copy this link and send via YM,MSN,AOL,ICQ..... Thuật toán sắp xếp nhanh Quick sort http://www.laptrinhviet.com/showthread.php?t=19827 Hãy gửi link này cho bạn bè trong list của bạn giúp mình nhé ;) thank nhiều

__________________

thucnq

my love vô danh mất tiêu rồi

Copy this link and send via YM,MSN,AOL,ICQ..... Thuật toán sắp xếp nhanh Quick sort http://www.laptrinhviet.com/showthread.php?t=19827 Hãy gửi link này cho bạn bè trong list của bạn giúp mình nhé ;) thank nhiều