1, tim kiem tuyen tinh

Tốt nhất:1

Xấu nhất: n+1

Tb  : (n+1)/2

Giải thuật có độ phức tạp cấp n:T(n)=O(n).

-          Giải thuật không phụ thuộc vào thứ tự các phần tử trong mảng, do vậy đây là phương pháp tổng quát để tìm số bk

-          Một thuật toán có thể cài đặt theo nhiều cách khác nhau

2, tìm kiếm nhị phân

Tốt nhất :1

Xấu nhất log2 n

Trung binh long 2 (n/2)

Chỉ áp dụng được dãy đã có thứ tự

Tnp =O(log2 n) <T tt(n)=O(n).

Tuy nhiên phải xét đến thời gian sắp xếp để 1 dãy đã có thự tự, điều đó tạo nên khuyết điểm cho tìm kiêm nhị phân

3,    Phương pháp chọn trực tiếp:

ở lượt thứ I,  bao giờ cũng cần n-1  lần so sánh để xác định phần tử nhỏ nhất.

số lần so sánh= tong (i=1 tới n-1) (n-i) =n(n-1)/2

xấu nhất số lần so sánh n(n-1)/2 số phép gán : 0

tốt nhất số lần so sánh n(n-1)/2 số phép gán : 3n(n-1)/2

4,    chèn trực tiếp

Các phép ss xảy ra trong mỗi vòng lặp wile tìm vị trí poss và mỗi lần xác định vị trí không thích hợp sẽ dời chỗ phần tử aposs, giải thuật thực hiện n-1 vòng wile

Tốt nhất số lần so sánh tổng i=1 tới n-1 (1) : n-1số phép gán : tổng i=1 tới n-1 (2) :2( n-1)

Tốt nhất số lần so sánh tổng i=1 tới n-1 (i-1) : n(n-1)/2số phép gán : tổng i=1 tới n-1 (i+1) :[n( n+1)/2]-1

Có thế áp dụng tìm kiếm nhị phân để tim vị trí poss

5,   đổi chỗ trực tiếp :

Số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng dãy số ban đầu nhưng số lượng  phép hoán vị phụ thuộc vào kết quả so sánh

Tốt nhất số lần so sánh tổng i=1 tới n-1 (n-i+1) = n(n-1)/2  số lần hoán vị : 0

Xấu  nhất số  lần so sán n(n-1)/2  số lần hoán vị : tổng i=1 tới n-1 (n-i+1) = n( n-1)/2

6,   nổi bọt bubble sort

Số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng dãy số ban đầu nhưng số lượng  phép hoán vị tùy thuộc vào kết quả so sánh

Tốt nhất số lần so sánh tổng i=1 tới n-1 (n-i+1) = n(n-1)/2  số lần hoán vị : 0

Xấu  nhất số  lần so sán n(n-1)/2  số lần hoán vị : tổng i=1 tới n-1 (n-i+1) = n( n-1)/2

Khuyết điểm: không nhận dạng được dãy đã có thứ tự hay có thứ tự toàn phần, các phần tử được đưa về vị trí đúng nhanh, các phần tử lớn được đưa về vị trí đúng chậm

Shakersort dựa trên blusort nhưng có những cái tiến khắc phục bub

Trong các lần sắp xếp duyệt mảng theo 2 lượt từ 2 phía khác nhau

+lượt đi : đẩy phần tử nhỏ về đầu mảng

+lượt về đẩy phần tử lớn về cuối mảng

Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép ss thừa

7,  shell sort

Trong th chọn dãy có độ dài theo công thức hi=(hi-1)/2 và hk=1 k=log2(n-1) thì có độ phức tạp gần bằng n^1,2 <<n^2

8, quick sort

Nx: về nguyên tắc có thể chọn giá trị mốc x là phần tử tùy ý nhưng để đơn giản phần tử giữa thường được chọn k=(l+r)/2.

Giá trị mốc được chọn sẽ quyết định hiệu quả thực hiện, chi phí median

Tốt nhất : n*log(n)

Xấu nhất : nbình

Trung bình :n*log(n)

8,   merge sort

Số lần lặp mergesort ở bước 2 và 3 bằng log2(n) do sau mỗi lần lặp giá trị k tăng lên gấp đôi, chi phí thực hiện sẽ là O(nlog2(n))

Nx : nhược điểm lớn nhất của thuật toán là không tận dụng những thong tin về đặc tính của dãy cần sắp xếp. vì vậy ít khi sử dụng trong thực tế thuật toán này, người ta sử dụng phiên bản cải tiến natural merge sort

Natural merge sort khác ở chỗ thay vì luôn cứng nhắc phân hoạch theo dãy con có chiều dài là k, việc phân hoạch sẽ theo đơn vị là đường chạy, ta chỉ cần biết đến số đường chạy của a sau lần phân hoạch cuối cùng là có thể biết thời điển dừng của thuật toán vì dãy đã có thứ tự là dãy chỉ có 1 đường chạy.

Một đường chạy của một dãy số a là một dãy con không giảm của cực đại của a, nghĩa là đường chạy r=(ai,ai+1…aj) phải thỏa mãn

{ ak<=aK+1; ai<ai-1; aj>ạ+1} với mọi k thuộc (i,j)

9,   radix sort

A, Sau lần phân phối thứ k các phần tử của a vào các lô bn, b1… b9 nếu chỉ xét đến k+1 chữ số của các phần tử trong a, ta sẽ có 1 mảng tăng dần nhờ trình tự lấy ra từ 0 đến 9 nx này đảm bảo tính đúng đắn của thuật toán

B, Thuật toán có độ phức tạp tuyến tính nên hiệu quả khi xắp có rất nhiều phần tử

C, thuật toán không có th xấu nhất và tốt nhất

D, thuật toán cài đặt thuận tiện với các mảng với khóa sắp là chuỗi

E người ta cũng dùng phương pháp phân lô theo biểu diễn nhị phân của khóa sắp xếp.