Thông tin
Hỏi đáp

Các thuật toán sắp xếp - Tin học (Tin học căn bản) | Trường Đại học Nam Cần Thơ

Các thuật toán sắp xếp - Tin học (Tin học căn bản) | Trường Đại học Nam Cần Thơ được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem!

Môn:

Tin học (Tin học căn bản) 12 tài liệu

Trường:

Đại học Nam Cần Thơ 96 tài liệu

Thông tin:

2 trang 5 tháng trước

Tác giả:

Mai Nguyệt

docx.com.vn

Bình luận

Vui lòng đăng nhập hoặc đăng ký để gửi bình luận.

Các thuật toán sắp xếp - Tin học (Tin học căn bản) | Trường Đại học Nam Cần Thơ

64 32 lượt tải Tải xuống

Các thuật toán sắp xếp

1, Sắp xếp nổi bọt

For i:=1 to N-1 do

For j:=i+1 to N do

If a[i]>a[j] then

Begin

Tam:=a[i];a[i]:=a[j];a[j]:=tam;

End;

Độ phức tạp thuật toán 0(N^2)

Độ phức tạp không gian bộ nhớ 0(N)

2, Sắp xếp nhanh-Quicksort

Procedure QS(L,R:longint);

Var

Begin

If L>=R then exit;i:=L;j:=R;

Giua:=a[(L+R) div 2];

Repeat

While a[i]<giua do inc(i);

While a[j]>giua do dec(j);

If i<=j then

Begin

Tam:=a[i];a[i]:=a[j];a[j]:=tam;

I:=i+1;j:=j-1;

End;

Until i>j;

If i<R then QS(i,R);

If j>L then QS(j,L);

End;

Độ phức tạp thuật toán là 0(N.logN)~10^5

Độ phức tạp không gian bộ nhớ 0(N)

Bấm Tải xuống để xem toàn bộ.

| 1/2

| | Tải xuống

Preview text:

Các thuật toán sắp xếp 1, Sắp xếp nổi bọt For i:=1 to N-1 do For j:=i+1 to N do If a[i]>a[j] then Begin
Tam:=a[i];a[i]:=a[j];a[j]:=tam; End;
Độ phức tạp thuật toán 0(N^2)
Độ phức tạp không gian bộ nhớ 0(N)
2, Sắp xếp nhanh-Quicksort Procedure QS(L,R:longint); Var Begin
If L>=R then exit;i:=L;j:=R; Giua:=a[(L+R) div 2]; Repeat
While a[i]While a[j]>giua do dec(j); If i<=j then Begin
Tam:=a[i];a[i]:=a[j];a[j]:=tam; I:=i+1;j:=j-1; End; Until i>j; If iIf j>L then QS(j,L); End;
Độ phức tạp thuật toán là 0(N.logN)~10^5
Độ phức tạp không gian bộ nhớ 0(N)