Shell sort có tốt không?
Trong sắp xếp, chúng ta có một số loại thuật toán cơ bản có thể sắp xếp các phần tử theo một thứ tự cụ thể. Chúng ta thường sử dụng một mảng và sắp xếp các phần tử của nó theo thứ tự số và từ điển Show Shell sort là phiên bản mở rộng và cải tiến của sắp xếp chèn. Trong sắp xếp chèn, chúng ta lấy một phần tử và so sánh nó với các phần tử trước đó để kiểm tra xem nó nhỏ hơn hay lớn hơn. Sau đó, chúng tôi hoán đổi các số tương ứng nơi diễn ra việc hoán đổi giữa hai phần tử liền kề Vì sắp xếp hệ vỏ là một biến thể của sắp xếp chèn, ở đây, chúng tôi thực hiện mọi thứ hơi khác một chút cho đến khi cuối cùng chúng tôi có thể áp dụng sắp xếp chèn Shell Sắp xếp là gì?Sắp xếp vỏ là một thuật toán sắp xếp và một biến thể mở rộng của sắp xếp chèn với độ phức tạp thời gian trung bình được cải thiện. Trong thuật toán sắp xếp này, chúng tôi so sánh các giá trị ngoài cùng bên phải với các giá trị ngoài cùng bên trái và cố gắng dịch chuyển các giá trị nhỏ hơn ở phía bên trái và các giá trị lớn hơn ở phía bên phải Vì thuật toán này là một phần mở rộng của sắp xếp chèn, nên nó cũng sử dụng sắp xếp chèn. Ở đây chúng tôi so sánh các giá trị bên trái với các giá trị bên phải dựa trên khoảng cách hoặc khoảng thời gian. Khi chúng ta sử dụng khoảng cách để so sánh các phần tử ở xa, với mỗi bộ so sánh, chúng ta sẽ giảm giá trị của khoảng cách. Khi thuật toán đạt đến điểm có giá trị khoảng cách là 1, nó sẽ sử dụng sắp xếp chèn Độ phức tạp về thời gian của Shell SortĐộ phức tạp thời gian tồi tệ nhất O(n 2 ) Độ phức tạp thời gian trung bình O(n 5/4 ) Độ phức tạp thời gian tốt nhất O(n 3/2 )Điểm quan trọng
Một ví dụ về Shell Sort. Giả sử chúng ta có một ARRAY = [34, 32, 41, 9, 13, 18, 26, 43]
Thuận lợi
Nhược điểm
Triển khai bằng Pythondef shellSort(alist): sublistcount = len(alist)//2 while sublistcount > 0: for startposition in range(sublistcount): gapInsertionSort(alist,startposition,sublistcount) print("After increments of size",sublistcount, "The list is",alist) sublistcount = sublistcount // 2 def gapInsertionSort(alist,start,gap): for i in range(start+gap,len(alist),gap): currentvalue = alist[i] position = i while position>=gap and alist[position-gap]>currentvalue: alist[position]=alist[position-gap] position = position-gap alist[position]=currentvalue alist = [54,26,93,17,77,31,44,55,20] shellSort(alist) print(alist) đầu ra After increments of size 4 The list is [20, 26, 44, 17, 54, 31, 93, 55, 77] After increments of size 2 The list is [20, 17, 44, 26, 54, 31, 77, 55, 93] After increments of size 1 The list is [17, 20, 26, 31, 44, 54, 55, 77, 93] [17, 20, 26, 31, 44, 54, 55, 77, 93] Triển khai trong C++#include |