Hướng dẫn is python sorted () stable? - python được sắp xếp () ổn định không?

Question

Tài liệu không đảm bảo điều đó. Có nơi nào khác mà nó được ghi lại không?

Nội dung chính Show

Làm thế nào hiệu quả là sắp xếp () trong Python?
Sắp xếp Python phá hủy?
Cái nào được sắp xếp hoặc sắp xếp tốt hơn trong Python?
Python có được sắp xếp nhanh không?

Tôi đoán nó có thể ổn định vì phương thức sắp xếp trên danh sách được đảm bảo là ổn định (Ghi chú điểm thứ 9: "Bắt đầu với Python 2.3, phương thức Sort () được đảm bảo là ổn định") và được sắp xếp có chức năng tương tự. Tuy nhiên, tôi không thể tìm thấy bất kỳ nguồn dứt khoát nào nói như vậy.

Mục đích: Tôi cần sắp xếp dựa trên khóa chính và cũng là khóa thứ cấp trong trường hợp khóa chính bằng nhau trong cả hai bản ghi. Nếu Sắp xếp () được đảm bảo là ổn định, tôi có thể sắp xếp trên khóa thứ cấp, sau đó sắp xếp trên khóa chính và nhận kết quả tôi cần.

Tái bút: Để tránh bất kỳ sự nhầm lẫn nào, tôi đang sử dụng ổn định theo nghĩa "một loại ổn định nếu nó đảm bảo không thay đổi thứ tự tương đối của các yếu tố so sánh bằng nhau".

hỏi ngày 16 tháng 12 năm 2009 lúc 15:30Dec 16, 2009 at 15:30

Có, ý định của hướng dẫn thực sự là để đảm bảo rằng sorted ổn định và thực sự nó sử dụng chính xác cùng một thuật toán với phương thức sort. Tôi nhận ra rằng các tài liệu không rõ ràng 100% về danh tính này; Các bản vá lỗi luôn được chấp nhận vui vẻ!

Đã trả lời ngày 16 tháng 12 năm 2009 lúc 15:36Dec 16, 2009 at 15:36

Alex Martellialex MartelliAlex Martelli

827K163 Huy hiệu vàng1204 Huy hiệu bạc1383 Huy hiệu Đồng163 gold badges1204 silver badges1383 bronze badges

3

Chúng ổn định.

Nhân tiện: Đôi khi bạn có thể bỏ qua khi biết liệu sắp xếp và sắp xếp có ổn định hay không, bằng cách kết hợp một loại đa đường theo một đường đơn.

Ví dụ: nếu bạn muốn sắp xếp các đối tượng dựa trên các thuộc tính last_name, first_name của chúng, bạn có thể thực hiện nó trong một lần vượt qua:

sorted_list= sorted(
    your_sequence_of_items,
    key= lambda item: (item.last_name, item.first_name))

Tận dụng so sánh tuple.

Câu trả lời này, as-is, bao gồm các câu hỏi ban đầu. Đối với các câu hỏi liên quan đến sắp xếp thêm, có Python sắp xếp cách hướng dẫn.

Đã trả lời ngày 28 tháng 12 năm 2009 lúc 22:42Dec 28, 2009 at 22:42

Tzottzottzot

89.5K29 Huy hiệu vàng138 Huy hiệu bạc201 Huy hiệu đồng29 gold badges138 silver badges201 bronze badges

6

Tài liệu đã thay đổi trong thời gian này (cam kết có liên quan) và tài liệu hiện tại của sorted đảm bảo rõ ràng:

Hàm sorted() tích hợp được đảm bảo là ổn định. Một loại ổn định nếu nó đảm bảo không thay đổi thứ tự tương đối của các yếu tố so sánh bằng nhau - điều này rất hữu ích để sắp xếp trong nhiều lần vượt qua (ví dụ, sắp xếp theo bộ phận, sau đó theo mức lương).

Phần này của tài liệu đã được thêm vào Python 2.7 và Python 3.4 (+), vì vậy, bất kỳ triển khai tuân thủ nào của phiên bản ngôn ngữ đó cũng phải có sorted ổn định.

Lưu ý rằng đối với cpython, list.sort đã ổn định kể từ Python 2.3

Tim Peters viết lại triển khai list.sort() của anh ấy - đây là một "loại ổn định" (đầu vào bằng nhau xuất hiện theo cùng một thứ tự trong đầu ra) và nhanh hơn trước.

Tôi không chắc chắn 100% về sorted, ngày nay nó sử dụng đơn giản list.sort, nhưng tôi đã không kiểm tra lịch sử cho điều đó. Nhưng có khả năng nó "luôn luôn" sử dụng list.sort.

Đã trả lời ngày 16 tháng 5 năm 2017 lúc 22:49May 16, 2017 at 22:49

MSEifertMseifertMSeifert

Huy hiệu vàng 138K3333 gold badges320 silver badges335 bronze badges

Python 3.6 doc về việc sắp xếp hiện đang nói rằng

Các loại được đảm bảo là ổn định

Hơn nữa, trong tài liệu đó, có một liên kết đến TIMSORT ổn định, trong đó nói rằng

Timsort đã là thuật toán phân loại tiêu chuẩn của Python kể từ phiên bản 2.3

Don nở

4.7113 huy hiệu vàng29 Huy hiệu bạc46 Huy hiệu đồng3 gold badges29 silver badges46 bronze badges

Đã trả lời ngày 11 tháng 6 năm 2018 lúc 9:41Jun 11, 2018 at 9:41

Wolfgang Kuehnwolfgang KuehnWolfgang Kuehn

11.5K2 Huy hiệu vàng32 Huy hiệu bạc43 Huy hiệu đồng2 gold badges32 silver badges43 bronze badges

0

Các tài liệu "Có gì mới" cho Python 2.4 có hiệu quả đưa ra điểm được sắp xếp () lần đầu tiên tạo một danh sách, sau đó gọi Sort () trên đó, cung cấp cho bạn sự đảm bảo bạn cần mặc dù không phải là tài liệu "chính thức". Bạn cũng có thể chỉ kiểm tra nguồn, nếu bạn thực sự quan tâm.

Đã trả lời ngày 16 tháng 12 năm 2009 lúc 15:38Dec 16, 2009 at 15:38

Peter Hansenpeter HansenPeter Hansen

20.6K4 Huy hiệu vàng47 Huy hiệu bạc72 Huy hiệu đồng4 gold badges47 silver badges72 bronze badges

2

Làm thế nào hiệu quả là sắp xếp () trong Python?

Sắp xếp () phương thức.Nó sửa đổi danh sách tại chỗ (và trả về không để tránh nhầm lẫn).Thông thường nó ít thuận tiện hơn so với Sắp xếp () - nhưng nếu bạn không cần danh sách ban đầu, nó sẽ hiệu quả hơn một chút.if you don't need the original list, it's slightly more efficient.

Sắp xếp Python phá hủy?

Sắp xếp () là một phương thức loại danh sách.Sắp xếp () là một quá trình phá hoại sắp xếp danh sách ban đầu tại chỗ.sort() is a destructive process that sorts the original list in place.

Cái nào được sắp xếp hoặc sắp xếp tốt hơn trong Python?

Sự khác biệt chính giữa hai là danh sách.sort () sẽ sắp xếp danh sách tại chỗ, biến đổi các chỉ mục của nó và không trả về, trong khi Sắp xếp () sẽ trả về một danh sách được sắp xếp mới để lại danh sách ban đầu không thay đổi.Một điểm khác biệt khác là Sắp xếp () chấp nhận bất kỳ sự khác biệt trong khi danh sách.list. sort() will sort the list in-place, mutating its indexes and returning None , whereas sorted() will return a new sorted list leaving the original list unchanged. Another difference is that sorted() accepts any iterable while list.