|
|
cập nhật lúc 04:38 ngày 22/05
|
|
|
|
|
|
| Anh em ơi, ai có trình DEMO sắp xếp nhanh của C++ ko? |
 |
thanhnhung
Bài viết: 64
|
| Ngày gởi: 24/11/2009 | Số lần xem: 3078 | Trả lời: 11 |
|
|
|
|
anh em ơi, ai có trình DEMO sắp xếp nhanh của C++ ko? em cần gấp |
|
|
10 |
 Bạn vui lòng chờ trong giây lát
Bài viết đã bị đóng.
|
|
|
|
 |
buncha
Bài viết: 340
|
Ngày gởi: 25/11/2009 02:00 AM
|
|
giải thuật quick sort đây
Code Mẫu:
//biến toàn cục
int a[8]={12,2,8,5,1,6,4,15};
int n=8;
//chương trình con
void QuickSort(int a[],int l,int r)
{
int i,j,x;
int temp;
i=l;j=r;
x=a[(l+r)/2];
while (i<j)
{
while (a[i]<=x) i++;
while (a[j]>x) j--;
if (i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++; j--;
}
}
if (l<j) QuickSort(a,l,j);
if (i<r) QuickSort(a,i,r);
}
|
|
|
|
| Bài phản hồi |
cam on, you looooooooooooooooveeeeeeeeeelyyyyyyyyyy qua. cam on rat nhieu
bạn nên cám ơn người trả lời đúng bằng cách chọn câu trả lời đúng, như vậy mới đúng công sức của họ bỏ ra, hơn nữa là khi chọn câu trả lời đúng thì câu trả lời đó sẽ nằm ngay dưới câu hỏi của bạn, như thế người đến sau sẽ tìm thấy câu trả lời đúng sớm hơn
|
|
| Câu Trả lời |
|
Chào bạn,
Theo mình hiểu thì ý bạn có phải là muốn hệ thống có nhiều đối tượng hỗ trợ việc sắp xếp, và số đối tượng này có thể thay đổi, nâng cấp ?
=> với ý này mình cũng nghĩ như bạn là dùng Factory
Ngoài ra, mình nghĩ có nên thêm phần đối tượng điều kiện sắp xếp nữa không: ví như theo thứ tự tăng/giảm của giá trị trả về từ một hàm nào đó của lớp "điều kiện", và việc so sánh "giá trị" này cũng được qui định bởi "lớp điều kiện" này
=> với ý này mình nghĩ có thể áp dụng mẫu Command - mới chỉ là ý định, mình chưa phân tích kỹ đc :-) bạn xem có đc ko
|
|
|
|
| Câu Trả lời |
 |
satan
Bài viết: 232
|
Ngày gởi: 29/11/2009 11:39 PM
|
|
|
|
|
|
| Câu Trả lời |
|
tienluc
Bài viết: 754
|
Ngày gởi: 29/11/2009 10:21 AM
|
|
|
|
|
|
| Câu Trả lời |
 |
salampo
Bài viết: 399
|
Ngày gởi: 28/11/2009 07:12 PM
|
|
Thuật toán sắp xếp nhanh QuickSort cũng nhiều kiểu thật.
Kiểu như bạn đã post lên thì dễ hiểu và dễ cài đặt.
Nhưng về đánh giá độ phức tạp thuật toán thì mình ko hẳn đồng ý.
Xét trường hợp xấu nhất: Phần tử x bạn chọn luôn là phần tử lớn nhất,khi đó sẽ tách thành 2 mảng (=x & Độ phức tạp thuật toán:
T(n)= n + T(1) + T(n-1)
=> T(n)= O(n^2)
Xét trường hợp tốt nhất: Chọn đc x sao cho chia thành 2 mảng con bằng nhau và bằng n/2
=> Độ phức tạp thuật toán:
T(n) = 2T(n/2) + n
=> T(n) = O(nlnn)
|
|
|
|
| Câu Trả lời |
|
tienluc
Bài viết: 754
|
Ngày gởi: 24/11/2009 11:46 PM
|
|
|
|
|
|
|
_1210.jpg)
Danh sách thành viên bình chọn