Sắp xếp theo kiểu đồi (Shell Sort)

Sắp xếp theo kiểu Hill (Shell Sort) là một kiểu sắp xếp chèn. Còn được gọi là sắp xếp gia tăng giảm, đây là phiên bản cải tiến và hiệu quả hơn của thuật toán sắp xếp chèn trực tiếp. Sắp xếp theo đồi là một thuật toán sắp xếp không ổn định. Phương pháp này là do DL. Shell được đặt tên sau khi nó được đề xuất vào năm 1959. Sắp xếp theo đồi là nhóm các bản ghi theo một mức tăng nhất định của mục tiêu và sử dụng thuật toán sắp xếp chèn trực tiếp để sắp xếp từng nhóm; khi mức tăng giảm dần, mỗi nhóm chứa ngày càng nhiều từ khóa. Toàn bộ tệp được chia thành một nhóm và thuật toán kết thúc.

Quy trình phân loại đồi

Ý tưởng cơ bản của sắp xếp theo Hill là: liệt kê mảng trong bảng và chèn và sắp xếp các cột riêng biệt, lặp lại quá trình này nhưng sử dụng cột dài hơn mỗi lần (độ dài bước dài hơn, số lượng cột ít hơn) . Cuối cùng, toàn bộ bảng chỉ có một cột. Chuyển mảng thành bảng là để hiểu rõ hơn về thuật toán, và bản thân thuật toán vẫn sử dụng mảng để sắp xếp.

Ví dụ: giả sử có một bộ số như vậy [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10], nếu chúng ta bắt đầu sắp xếp với kích thước bước là 5, chúng ta có thể đặt danh sách này trong một cột 5 Để mô tả tốt hơn các thuật toán trong bảng, chúng sẽ trông như thế này (các phần tử dọc bao gồm các bước):

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

Sau đó, chúng tôi sắp xếp từng cột:

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

Khi nối bốn dãy số trên với nhau theo thứ tự, ta được: [10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45]. Tại thời điểm này, 10 đã được di chuyển đến đúng vị trí và sau đó được sắp xếp theo các bước của 3:

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

Sau khi sắp xếp, nó sẽ trở thành:

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

Cuối cùng, sắp xếp theo 1 bước (lần này là sắp xếp chèn đơn giản)

Phân tích phân loại đồi

def shell_sort(alist):
    n = len(alist)
    gap = n / 2
    while gap > 0:
        for i in range(gap, n):
            j = i
            while j>=gap and alist[j-gap] > alist[j]:
                alist[j-gap], alist[j] = alist[j], alist[j-gap]
                j -= gap
        gap = gap / 2

alist = [54,26,93,17,77,31,44,55,20]
shell_sort(alist)
print(alist)

thời gian phức tạp

• Độ phức tạp thời gian tối ưu: thay đổi theo trình tự bước

• Độ phức tạp thời gian tồi tệ nhất: O (n 2 )

• Tư duy ổn định: không ổn định

Bản demo phân loại đồi

đạn pháo