Sắp xếp chèn Python hoạt động giống như sắp xếp các thẻ trò chơi. Để sử dụng sắp xếp chèn, bạn tạo hai danh sách:danh sách đã sắp xếp và chưa sắp xếp. Bạn so sánh từng mục trong danh sách chưa được sắp xếp cho đến khi bạn sắp xếp được mục đó. Sắp xếp chèn là một thuật toán tiêu chuẩn phổ biến trong ngôn ngữ Python.
Bạn đã bao giờ sắp xếp các quân bài trong tay mình chưa? Đó là một cách để nghĩ về khái niệm sắp xếp chèn Python. Khi bạn cần sắp xếp danh sách chỉ có một vài phần tử, sắp xếp chèn sẽ hỗ trợ bạn.
Việc sắp xếp chèn sẽ đặt một phần tử chưa được sắp xếp vào đúng vị trí của nó sau mỗi lần lặp lại trong một mảng.
Trong hướng dẫn này, chúng ta sẽ nói về các loại chèn là gì và cách chúng hoạt động. Chúng ta sẽ thảo luận về cách triển khai sắp xếp chèn trong Python, có tham chiếu đến một ví dụ, vì vậy bạn có thể bắt đầu với thuật toán sắp xếp này.
Sắp xếp chèn trong Python là gì?
Sắp xếp chèn chia danh sách thành hai danh sách con:đã sắp xếp và chưa sắp xếp. Sau đó, nó sẽ so sánh từng phần tử trong danh sách chưa được sắp xếp và tiếp tục làm như vậy cho đến khi từng mục trong danh sách được sắp xếp.
Một thuật toán sắp xếp chèn di chuyển một mục đã được sắp xếp vào danh sách con đã sắp xếp và xóa nó khỏi danh sách phụ chưa được sắp xếp. Cả hai danh sách con đều là một phần của cùng một mảng, nhưng chúng phân biệt liệu một mục có được sắp xếp hay không.
Bạn có thể nghĩ về cách sắp xếp chèn giống như cách bạn sắp xếp một bộ thẻ trong tay mình trong một trò chơi bài.
Bạn sẽ di chuyển từng thẻ một qua danh sách các thẻ và so sánh chúng với nhau. Các thẻ được sắp xếp sẽ xuất hiện ở bên trái bàn tay của bạn. Các thẻ chưa được sắp xếp sẽ xuất hiện ở bên phải cho đến khi bạn sắp xếp tất cả.
81% người tham gia cho biết họ cảm thấy tự tin hơn về triển vọng công việc công nghệ của mình sau khi tham gia một cuộc thi đào tạo. Kết hợp với bootcamp ngay hôm nay.
Sinh viên tốt nghiệp bootcamp trung bình đã dành ít hơn sáu tháng để chuyển đổi nghề nghiệp, từ khi bắt đầu bootcamp đến khi tìm được công việc đầu tiên của họ.
Cách sắp xếp chèn trong Python hoạt động như thế nào?
Hãy bắt tay vào công việc và sắp xếp một mảng bằng cách sử dụng thuật toán sắp xếp chèn. Hãy xem xét mảng không được sắp xếp sau:
| 9 | 4 | 3 | 5 |
Trong một sắp xếp chèn, phần tử đầu tiên được coi là đã được sắp xếp. Phần tử thứ hai được lưu trữ trong biến riêng của nó. Chúng tôi sẽ gọi biến này là current_number .
| Sắp xếp | current_number | | |
| 9 | 4 | 3 | 5 |
Chúng ta cần so sánh current_number với mục ở vị trí đầu tiên trong mảng. Nếu current_number lớn hơn phần tử đầu tiên, nó vẫn ở cùng một vị trí. Nếu không, current_number được chuyển lên phía trước phần tử đầu tiên.
4 không lớn hơn 9, vì vậy hai phần tử này hoán đổi vị trí cho nhau.
| 4 | 9 | 3 | 5 |
Hai yếu tố đầu tiên trong danh sách của chúng tôi được sắp xếp. Tiếp theo, chúng tôi thay đổi giá trị của current_number thành mục thứ ba trong danh sách và so sánh nó với tất cả các mục bên trái của nó.
Số current_number của chúng ta trở thành 3. Chúng ta cần so sánh:
- 3 có lớn hơn 9 không? Không, vì vậy 3 được chèn vào trước 9.
- 3 có lớn hơn 4 không? Không, vì vậy 3 được chuyển trước 4.
Danh sách của chúng tôi bây giờ trông giống như sau:
| 3 | 4 | 9 | 5 |
Quá trình này lặp lại cho đến khi danh sách được sắp xếp. Danh sách của chúng tôi chỉ có một tập hợp so sánh nữa để thực hiện vì nó chỉ chứa bốn giá trị. Trong lần lặp tiếp theo, 5 trở thành current_number.
- 5 có lớn hơn 9 không? Không, 5 nước đi trước 9.
được sử dụng t Không so sánh được nữa vì 5 là số cuối cùng trong danh sách đã sắp xếp của chúng tôi. Sau lần lặp này, mảng của chúng ta đã được sắp xếp:
| 3 | 4 | 5 | 9 |
Nó đơn giản mà! Trong sắp xếp chèn của chúng tôi, chúng tôi luôn giữ các giá trị đã sắp xếp ở bên trái danh sách. Các giá trị chưa được sắp xếp xuất hiện ở bên phải.
Đối với mỗi lần lặp trong danh sách, chúng tôi so sánh current_number với tất cả các mục chưa được sắp xếp. Quá trình này lặp lại cho đến khi danh sách của chúng tôi được sắp xếp.
Cách viết Sắp xếp Chèn bằng Python
Tất cả đều ổn và tốt khi đi qua phân loại chèn trên giấy. Bây giờ đã đến lúc đi vào thực tế và triển khai sắp xếp chèn trong Python.
Viết hàm sắp xếp
Chúng ta sẽ bắt đầu bằng cách viết một hàm Python thực hiện sắp xếp của chúng ta:
def sortNumbers(toSort): for number in range(1, len(toSort)): current_number = toSort[number] i = number - 1 while i >= 0 and current_number < toSort[i]: toSort[i + 1] = toSort[i] i -= 1 toSort[i + 1] = current_number
Hãy cùng tìm hiểu cách thức hoạt động của tính năng này. Trong sortNumbers của chúng tôi chúng ta tạo một vòng lặp Python for lặp qua mọi số trong danh sách. Sau đó, chúng tôi đặt phần tử đầu tiên trong danh sách làm giá trị được sắp xếp bằng cách gán nó cho biến Python current_number .
Chúng tôi lặp lại mọi mục trong danh sách Python chưa được sắp xếp (mọi mục sau current_number). Sau đó, chúng tôi so sánh current_number với mỗi số bên trái của nó. Sau khi điều này xảy ra, chúng tôi đặt giá trị của current_number bằng với phần tử sau nó trong danh sách.
Viết chương trình chính
Chúng tôi phải viết một chương trình chính thực thi loại chèn của chúng tôi:
numbers = [9, 4, 3, 5] sortNumbers(numbers) print(numbers)
Mã của chúng tôi trả về:
[3, 4, 5, 9]
Danh sách của chúng tôi đã được sắp xếp theo thứ tự tăng dần! Chúc mừng bạn đã đạt được điều này.
Các loại chèn Python:Thứ tự giảm dần
Sắp xếp chèn có thể sắp xếp các số theo thứ tự giảm dần. Để thực hiện điều này, bạn cần đảo ngược dấu “nhỏ hơn” (>) trong vòng lặp while và biến nó thành dấu lớn hơn:
while i> =0 and current_number> toSort [i]:
Dòng mã này, được thay thế trong ví dụ trên của chúng tôi, sẽ sắp xếp các mục trong danh sách theo thứ tự ngược lại.
Khi nào bạn nên sử dụng sắp xếp chèn?
Sắp xếp chèn được sử dụng tốt nhất khi dữ liệu trong danh sách gần như được sắp xếp hoặc khi bạn đang sắp xếp một danh sách nhỏ. Có nhiều thuật toán hiệu quả hơn mà bạn có thể sử dụng để sắp xếp các danh sách lớn. Ví dụ:sắp xếp hợp nhất hoặc sắp xếp nhanh sẽ nhanh hơn.
Sắp xếp chèn nhanh hơn sắp xếp bong bóng.
Dù sao thì các loại chèn cũng rất hữu ích. Biết cách triển khai sắp xếp chèn cung cấp cho bạn một kiểu sắp xếp khác mà bạn có thể sử dụng.
Việc sắp xếp chèn ít phức tạp hơn so với một số thuật toán sắp xếp khác. Khi bạn đã học cách viết sắp xếp chèn, bạn sẽ tiến gần hơn đến việc tìm hiểu về các kiểu phức tạp hơn như sắp xếp hợp nhất.
Sắp xếp chèn Python:Phân tích độ phức tạp
Giống như tất cả các thuật toán, điều quan trọng là phải xem xét độ phức tạp tốt nhất, kém nhất và trung bình. Điều này sẽ cung cấp cho chúng tôi cái nhìn sâu sắc về mức độ hiệu quả của thuật toán trong việc thực hiện công việc của nó:trong trường hợp này là sắp xếp danh sách.
Trường hợp xấu nhất và độ phức tạp trung bình là O (n2). Điều này có nghĩa là thuật toán sẽ phát triển chậm hơn theo cấp số nhân khi bạn thêm nhiều giá trị hơn để sắp xếp trong danh sách của mình.
Trường hợp tốt nhất là O (n). Điều này xảy ra khi chúng tôi chạy thuật toán trên một danh sách được sắp xếp. Thuật toán kiểm tra xem các mục có được sắp xếp hay không và sau đó dừng chạy.
Bạn có thể tìm hiểu thêm về cách chúng tôi thể hiện độ phức tạp của thuật toán trong loạt bài gồm hai phần về Ký hiệu Big O.
Kết luận
Việc sắp xếp chèn giống như sắp xếp một danh sách các quân bài trên tay của bạn trong một trò chơi bài. Bạn giữ hai danh sách:danh sách các mục đã sắp xếp và danh sách các mục cần sắp xếp. Sau đó, bạn duyệt qua danh sách các mục chưa được sắp xếp và xáo trộn vị trí của chúng cho đến khi chúng được sắp xếp hết.
Bạn đang tìm kiếm thêm tài nguyên về ngôn ngữ lập trình Python? Xem hướng dẫn Cách học Python đầy đủ của chúng tôi. Bạn sẽ tìm thấy các mẹo hàng đầu về cách học Python và danh sách các khóa học trực tuyến, sách và các tài nguyên khác.