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!

50 25 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Tin học (Tin học căn bản)

Trường: Đại học Nam Cần Thơ

Thông tin:

2 trang 4 tháng trước

Tác giả:

Profile Mai Nguyệt
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)
| 1/2
| | Tải xuống

Có thể bạn quan tâm:

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)