Trong khoa học máy tính, thuật toán sắp xếp là thuật toán sắp xếp các phần tử của danh sách theo thứ tự. Các thứ tự được sử dụng thường xuyên nhất là thứ tự số và thứ tự từ điển, tăng dần hoặc giảm dần. Sắp xếp hiệu quả rất quan trọng để tối ưu hóa hiệu quả của các thuật toán khác (chẳng hạn như thuật toán tìm kiếm và hợp nhất) yêu cầu dữ liệu đầu vào phải nằm trong danh sách được sắp xếp. Sắp xếp cũng thường hữu ích để chuẩn hóa dữ liệu và để tạo đầu ra mà con người có thể đọc được Show
Về hình thức, đầu ra của bất kỳ thuật toán sắp xếp nào cũng phải thỏa mãn hai điều kiện
Để có hiệu quả tối ưu, dữ liệu đầu vào phải được lưu trữ trong cấu trúc dữ liệu cho phép truy cập ngẫu nhiên thay vì cấu trúc chỉ cho phép truy cập tuần tự Lịch sử và khái niệm[sửa | sửa mã nguồn]Ngay từ khi bắt đầu có máy tính, bài toán sắp xếp đã thu hút rất nhiều nghiên cứu, có lẽ do tính phức tạp của việc giải nó một cách hiệu quả mặc dù cách phát biểu đơn giản, quen thuộc của nó. Trong số các tác giả của thuật toán sắp xếp sớm vào khoảng năm 1951 có Betty Holberton, người đã làm việc trên ENIAC và UNIVAC. Sắp xếp bong bóng được phân tích sớm nhất là vào năm 1956. Các thuật toán tối ưu tiệm cận đã được biết đến từ giữa thế kỷ 20 – các thuật toán mới vẫn đang được phát minh, với thuật toán Timsort được sử dụng rộng rãi từ năm 2002 và thuật toán sắp xếp thư viện được xuất bản lần đầu vào năm 2006 Các thuật toán sắp xếp so sánh có yêu cầu cơ bản là so sánh Ω(n log n) (một số chuỗi đầu vào sẽ yêu cầu bội số của n log n so sánh, trong đó n là số phần tử trong mảng được sắp xếp). Các thuật toán không dựa trên so sánh, chẳng hạn như sắp xếp đếm, có thể có hiệu suất tốt hơn Các thuật toán sắp xếp phổ biến trong các lớp khoa học máy tính nhập môn, trong đó sự phong phú của các thuật toán cho vấn đề cung cấp phần giới thiệu nhẹ nhàng về nhiều khái niệm thuật toán cốt lõi, chẳng hạn như ký hiệu O lớn, thuật toán chia để trị, cấu trúc dữ liệu như đống và nhị phân. Sắp xếp các mảng nhỏ một cách tối ưu (trong ít phép so sánh và hoán đổi nhất) hoặc nhanh (i. e. có tính đến các chi tiết cụ thể của máy) vẫn là một vấn đề nghiên cứu mở, với các giải pháp chỉ được biết đến với các mảng rất nhỏ (<20 phần tử). Sắp xếp tối ưu tương tự (theo các định nghĩa khác nhau) trên một máy song song là một chủ đề nghiên cứu mở Các thuật toán sắp xếp có thể được phân loại theo
Tính ổn định[sửa] Một ví dụ về sắp xếp ổn định trên thẻ chơi. Khi các thẻ được sắp xếp theo thứ hạng với một sắp xếp ổn định, hai số 5 phải giữ nguyên thứ tự trong đầu ra được sắp xếp ban đầu của chúng. Khi chúng được sắp xếp với cách sắp xếp không ổn định, 5s có thể kết thúc theo thứ tự ngược lại trong đầu ra được sắp xếp Các thuật toán sắp xếp ổn định sắp xếp các phần tử bằng nhau theo cùng thứ tự mà chúng xuất hiện trong đầu vào. Ví dụ: trong ví dụ sắp xếp quân bài ở bên phải, quân bài đang được sắp xếp theo thứ hạng và chất của chúng bị bỏ qua. Điều này cho phép khả năng có nhiều phiên bản được sắp xếp chính xác khác nhau của danh sách gốc. Các thuật toán sắp xếp ổn định chọn một trong các thuật toán này, theo quy tắc sau. nếu hai mục so sánh bằng nhau (chẳng hạn như hai thẻ 5), thì thứ tự tương đối của chúng sẽ được giữ nguyên, tôi. e. nếu cái này đến trước cái kia ở đầu vào, nó sẽ đến trước cái kia ở đầu ra Tính ổn định rất quan trọng để duy trì thứ tự trên nhiều loại trên cùng một tập dữ liệu. Ví dụ: giả sử rằng các bản ghi sinh viên bao gồm phần tên và lớp được sắp xếp động, đầu tiên theo tên, sau đó theo phần lớp. Nếu sử dụng thuật toán sắp xếp ổn định trong cả hai trường hợp, thao tác sắp xếp theo từng lớp sẽ không làm thay đổi thứ tự tên; Chính thức hơn, dữ liệu được sắp xếp có thể được biểu diễn dưới dạng bản ghi hoặc bộ giá trị và phần dữ liệu được sử dụng để sắp xếp được gọi là khóa. Trong ví dụ về quân bài, các quân bài được biểu diễn dưới dạng một bản ghi (thứ hạng, chất) và khóa là thứ hạng. Một thuật toán sắp xếp ổn định nếu mỗi khi có hai bản ghi R và S có cùng khóa và R xuất hiện trước S trong danh sách ban đầu thì R luôn xuất hiện trước S trong danh sách đã sắp xếp Khi các phần tử bằng nhau không thể phân biệt được, chẳng hạn như với số nguyên hoặc nói chung hơn là bất kỳ dữ liệu nào trong đó toàn bộ phần tử là chính, thì tính ổn định không phải là vấn đề. Tính ổn định cũng không phải là vấn đề nếu tất cả các phím khác nhau Các thuật toán sắp xếp không ổn định có thể được triển khai đặc biệt để ổn định. Một cách để làm điều này là mở rộng phép so sánh khóa một cách giả tạo, sao cho phép so sánh giữa hai đối tượng có các khóa bằng nhau được quyết định bằng cách sử dụng thứ tự của các mục nhập trong danh sách đầu vào ban đầu làm bộ ngắt kết nối. Tuy nhiên, việc ghi nhớ thứ tự này có thể cần thêm thời gian và không gian Một ứng dụng cho thuật toán sắp xếp ổn định là sắp xếp danh sách bằng khóa chính và khóa phụ. Ví dụ: giả sử chúng ta muốn sắp xếp một bộ bài sao cho các bộ bài theo thứ tự gậy (♣), kim cương (♦), trái tim (♥), bích (♠) và trong mỗi bộ, các quân bài được sắp xếp theo . Điều này có thể được thực hiện bằng cách trước tiên sắp xếp các thẻ theo thứ hạng (sử dụng bất kỳ cách sắp xếp nào), sau đó thực hiện sắp xếp ổn định theo chất Trong mỗi bộ đồ, sắp xếp ổn định duy trì thứ tự theo thứ hạng đã được thực hiện. Ý tưởng này có thể được mở rộng cho bất kỳ số lượng khóa nào và được sử dụng theo sắp xếp cơ số. Có thể đạt được hiệu quả tương tự với cách sắp xếp không ổn định bằng cách sử dụng phép so sánh khóa từ điển, trong đó, e. g. , trước tiên so sánh theo bộ, sau đó so sánh theo thứ hạng nếu các bộ giống nhau So sánh các thuật toán[sửa | sửa mã nguồn]Trong các bảng này, n là số bản ghi được sắp xếp. Các cột "Tốt nhất", "Trung bình" và "Tệ nhất" đưa ra độ phức tạp về thời gian trong từng trường hợp, với giả định rằng độ dài của mỗi khóa là không đổi và do đó, tất cả các phép so sánh, hoán đổi và các hoạt động khác có thể tiến hành trong thời gian không đổi. "Bộ nhớ" biểu thị dung lượng lưu trữ bổ sung cần thiết bổ sung cho dung lượng được sử dụng bởi chính danh sách, theo cùng một giả định. Thời gian chạy và các yêu cầu bộ nhớ được liệt kê nằm trong ký hiệu O lớn, do đó cơ số của logarit không thành vấn đề. Ký hiệu log2 n có nghĩa là (log n)2 Các loại so sánh [ chỉnh sửa ]Dưới đây là bảng so sánh các loại. Một loại so sánh trung bình không thể hoạt động tốt hơn O(n log n) So sánh sắp xếpNameBestAverageWorstMemoryStableMethodCác ghi chú khácQuicksortnlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n}n2{\displaystyle n^{2}}logn{\displaystyle . Hợp nhất sortnlogn{\displaystyle n\log n}NoPartitioningQuicksort is usually done in-place with O(log n) stack space.Merge sortnlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n}nlogn{\displaystyle n\log . Sắp xếp hợp nhất tại chỗ——nlog2n{\displaystyle n\log ^{2}n}nYesMerging (up to O(log n) using the Three Hungarians' Algorithm).In-place merge sort——nlog2n{\displaystyle n\log ^{2}n}1YesMergingCó thể được triển khai dưới dạng sắp xếp ổn định dựa trên việc hợp nhất tại chỗ ổn định. Introsortnlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n . Heapsortnlogn{\displaystyle n\log n}logn{\displaystyle \log n}NoPartitioning & SelectionUsed in several STL implementations.Heapsortnlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n . Sắp xếp khốinnlogn{\displaystyle n\log n}1NoSelectionInsertion sortnn2{\displaystyle n^{2}}n2{\displaystyle n^{2}}1YesInsertionO(n + d), in the worst case over sequences that have d inversions.Block sortnnlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n}1YesInsertion & MergingKết hợp O( dựa trên khối) . Timsortnnlogn{\displaystyle n\log n} in-place merge algorithm with a .Timsortnnlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n}nYesChèn & Hợp nhấtThực hiện so sánh n-1 khi dữ liệu . Sắp xếp lựa chọnn2{\displaystyle n^{2}}n2{\displaystyle n^{2}}n2{\displaystyle n^{2}}< . Cubesortnnlogn{\displaystyle n\log n}1NoSelectionStable with O(n){\displaystyle O(n)} extra space, when using linked lists, or when made as a variant of Insertion Sort instead of swapping the two items.Cubesortnnlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n}nYesInsertionThực hiện so sánh n-1 khi dữ liệu đã có . Shellsortnlogn{\displaystyle n\log n}n4/3{\displaystyle n^{4/3}}n3/2{\displaystyle n . Sắp xếp bong bóngnn2{\displaystyle n^{2}}1NoInsertionSmall code size.Bubble sortnn2{\displaystyle n^{2}}n2{\displaystyle n^{2}}1YesExchangeKích thước mã nhỏ. n2{\displaystyle n^{2}}n2{\displaystyle n^{2}}n2{\displaystyle n^{2}}1NoExchangingTiny code size.Tree sortnlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n}nlogn{\displaystyle n\log . Sắp xếp theo chu kỳn2{\displaystyle n^{2}}(balanced)nYesInsertionWhen using a self-balancing binary search tree.Cycle sortn2{\displaystyle n^{2}}n2{\displaystyle n^{2}}n2{\displaystyle n^{2}}< . Thư viện sortnlogn{\displaystyle n\log n}1NoSelectionIn-place with theoretically optimal number of writes.Library sortnlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n}n2{\displaystyle n^{2} . Nó yêu cầu hoán vị ngẫu nhiên đầu vào để đảm bảo giới hạn thời gian có xác suất cao, khiến nó không ổn định. Sắp xếp kiên nhẫnnnlogn{\displaystyle n\log n}nNoInsertionSimilar to a gapped insertion sort. It requires randomly permuting the input to warrant with-high-probability time bounds, which makes it not stable.Patience sortingnnlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n}nNoInsertion & SelectionTìm tất cả các dãy con tăng dài nhất trong . Smoothsortnnlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n}1NoSelectionMột biến thể thích ứng của heapsort dựa trên trình tự Leonardo . Strand sortnn2{\displaystyle n^{2}}n2{\displaystyle n^{2}}nYesSelectionTournament sortnlogn{\displaystyle n\log n . Bình lắc cocktail sortnn2{\displaystyle n^{2}}nlogn{\displaystyle n\log n}nlogn{\displaystyle n\log n}nNoSelectionVariation of Heapsort.Cocktail shaker sortnn2{\displaystyle n^{2}}n2{\displaystyle n^{2}}1YesEx ExchangeMột biến thể của Bubblesort xử lý tốt với các giá trị nhỏ . Gnome sortnn2{\displaystyle n^{2}}n2{\displaystyle n^{2}}n2{\displaystyle n^{2}}1NoExchangingFaster than bubble sort on average.Gnome sortnn2{\displaystyle n^{2}}n2{\displaystyle n^{2}}1YesExchangeKích thước mã nhỏ. Sắp xếp lẻ–chẵnnn2{\displaystyle n^{2}}n2{\displaystyle n^{2}}1YesEx ExchangeCó thể dễ dàng chạy trên các bộ xử lý song song.Các loại không so sánh [ chỉnh sửa ]Bảng sau mô tả các thuật toán sắp xếp số nguyên và các thuật toán sắp xếp khác không phải là sắp xếp so sánh. Như vậy, chúng không bị giới hạn ở Ω(n log n). Độ phức tạp bên dưới giả sử có n phần tử được sắp xếp, với các khóa có kích thước k, kích thước chữ số d và r phạm vi số được sắp xếp. Nhiều trong số chúng dựa trên giả định rằng kích thước khóa đủ lớn để tất cả các mục có giá trị khóa duy nhất và do đó n ≪ 2k, trong đó ≪ có nghĩa là "ít hơn nhiều". Trong mô hình máy truy cập ngẫu nhiên có chi phí đơn vị, các thuật toán có thời gian chạy n⋅kd{\displaystyle \scriptstyle n\cdot {\frac {k}{d}}}, chẳng hạn như . , and a larger number of elements to sort would require a bigger k in order to store them in the memory. Sắp xếp không so sánhNameBestAverageWorstMemoryStablen ≪ 2kNotesPigeonhole sort—n+2k{\displaystyle n+2^{k}}n+2k{\displaystyle n+2^{k}} . Sắp xếp nhóm (phím thống nhất)—n+k{\displaystyle n+k}2k{\displaystyle 2^{k}}YesYesCannot sort non-integers.Bucket sort (uniform keys)—n+k{\displaystyle n+k}n2⋅k{\displaystyle n^{2}\cdot k} . YesNoAssumes uniform distribution of elements from the domain in the array.Cũng không thể sắp xếp các số nguyên Sắp xếp nhóm (phím số nguyên)—n+r{\displaystyle n+r}n+r{\displaystyle n+r} . Sắp xếp đếm—n+r{\displaystyle n+r}YesYesIf r is O(n){\displaystyle O(n)}, then average time complexity is O(n){\displaystyle O(n)}.Counting sort—n+r{\displaystyle n+r}n+r{\displaystyle n+r}n+r{\displaystyle n+r . n{\displaystyle n}YesYesIf r is O(n){\displaystyle O(n)}, then average time complexity is O(n){\displaystyle O(n)}.n{\displaystyle n}n⋅kd{\displaystyle n\cdot {\frac {k}{d}}}n⋅kd{\displaystyle . n+2d{\displaystyle n+2^{d}}YesNokd{\displaystyle {\frac {k}{d}}} recursion levels, 2d for count array.Không giống như hầu hết các loại phân phối, điều này có thể sắp xếp các số Dấu phẩy động, số âm, v.v. —n⋅kd{\displaystyle n\cdot {\frac {k}{d}}}n⋅kd{\displaystyle n\cdot {\frac {k} . n+2d{\displaystyle n+2^{d}}YesNoStable version uses an external array of size n to hold all of the bins.Giống như biến thể LSD, nó có thể sắp xếp các số không phải số nguyên (tại chỗ)—n⋅k1{\displaystyle n\cdot {\frac {k}{1}}}n⋅k1{\displaystyle n\cdot { . Spreadsortnn⋅kd{\displaystyle n\cdot {\frac {k}{d}}}21{\displaystyle 2^{1}}NoNod=1 for in-place, k/1{\displaystyle k/1} recursion levels, no count array.Spreadsortnn⋅kd{\displaystyle n\cdot {\frac {k}{d}}}n⋅(ks+d){\displaystyle n\cdot \left({{\frac { . Burstsort—n⋅kd{\displaystyle n\cdot {\frac {k}{d}}}kd⋅2d{\displaystyle {\frac {k}{d}}\cdot 2^{d}}NoNoAsymptotic are based on the assumption that n ≪ 2k, but the algorithm does not require this.Burstsort—n⋅kd{\displaystyle n\cdot {\frac {k}{d}}}n⋅kd{\displaystyle n\cdot {\frac {k}{d}} . Mặc dù phần nào dựa vào chi tiết cụ thể của các chuỗi thường gặp. Flashsortnn+r{\displaystyle n+r}n⋅kd{\displaystyle n\cdot {\frac {k}{d}}}NoNoHas better constant factor than radix sort for sorting strings. Though relies somewhat on specifics of commonly encountered strings.Flashsortnn+r{\displaystyle n+r}n2{\displaystyle n^{2}}nNoNoYêu cầu phân phối đồng đều các phần tử từ miền trong mảng đến . Nếu phân phối cực kỳ sai lệch thì nó có thể chuyển sang bậc hai nếu sắp xếp cơ bản là bậc hai (nó thường là sắp xếp chèn). Phiên bản tại chỗ không ổn định. Người đưa thư sắp xếp—n⋅kd{\displaystyle n\cdot {\frac {k}{d}}}n⋅kd{\displaystyle n\cdot {\frac {k}{d} . Cụ thể để gửi nhu cầu dịch vụ. n+2d{\displaystyle n+2^{d}}—NoA variation of bucket sort, which works very similarly to MSD Radix Sort. Specific to post service needs.Sắp xếp mẫu có thể được sử dụng để song song hóa bất kỳ cách sắp xếp không so sánh nào, bằng cách phân phối hiệu quả dữ liệu vào một số nhóm và sau đó chuyển quá trình sắp xếp xuống một số bộ xử lý mà không cần hợp nhất vì các nhóm đã được sắp xếp lẫn nhau Một số thuật toán chậm so với các thuật toán đã thảo luận ở trên, chẳng hạn như thuật toán bogosort với thời gian chạy không giới hạn và thuật toán sắp xếp có O(n2. 7) thời gian chạy. Những loại này thường được mô tả cho mục đích giáo dục để chứng minh thời gian chạy của thuật toán được ước tính như thế nào. Bảng sau đây mô tả một số thuật toán sắp xếp không thực tế để sử dụng thực tế trong bối cảnh phần mềm truyền thống do hiệu suất cực kỳ kém hoặc yêu cầu phần cứng chuyên dụng NameBestAverageWorstMemoryStableComparisonCác ghi chú khácBead sortnSSn2{\displaystyle n^{2}}—NoWorks chỉ với số nguyên dương. Yêu cầu phần cứng chuyên dụng để nó chạy trong thời gian O(n){\displaystyle O(n)} được đảm bảo. Có khả năng triển khai phần mềm, nhưng thời gian chạy sẽ là O(S){\displaystyle O(S)}, trong đó S là tổng của tất cả các số nguyên cần sắp xếp, trong trường hợp nhỏ . Sắp xếp bánh kếp đơn giản—n2{\displaystyle n^{2}}n2{\displaystyle n^{2}}logn{\displaystyle \log . "Tôi không thể tin là nó có thể sắp xếp"n2{\displaystyle n^{2}}NoYesCount is number of flips."I Can't Believe It Can Sort"n2{\displaystyle n^{2}}n2{\displaystyle n^{2}}n2{ . Spaghetti (Thăm dò ý kiến) sortnnnn2{\displaystyle n^{2}}1NoYesNotable primarily for appearing to be an erroneous implementation of either Insertion Sort or .Spaghetti (Poll) sortnnnn2{\displaystyle n^{2}}YesPollingĐây là thuật toán tương tự, thời gian tuyến tính để sắp xếp một chuỗi các mục, yêu cầu không gian ngăn xếp O(n) và sắp xếp . Điều này yêu cầu n bộ xử lý song song. Nhìn thấy. Mạng sắp xếpVariesVariesVariesVaries (mạng sắp xếp ổn định yêu cầu nhiều phép so sánh hơn)CóThứ tự so sánh được đặt trước dựa trên kích thước mạng cố định. [tranh cãi – thảo luận]Bitonic sorterlog2n{\displaystyle \log ^{2}n} parallellog2n{\displaystyle \log ^{2}n} parallelnlog2n{\displaystyle n\log ^{2}n} non-parallel1NoYesAn effective variation of Sorting networks.[disputed – discuss]Bogosortn(n×n!){\displaystyle (n\times n!)}không giới hạn (nhất định), (n×n. ){\displaystyle (n\lần n. )} (dự kiến)1KhôngCóXáo trộn ngẫu nhiên. Chỉ được sử dụng cho mục đích ví dụ, vì ngay cả thời gian chạy trong trường hợp tốt nhất dự kiến cũng rất tệ. Stooge sortnlog3/log1. 5{\displaystyle n^{\log 3/\log 1. 5}}nlog3/log1. 5{\displaystyle n^{\log 3/\log 1. 5}}nlog3/log1. 5{\displaystyle n^{\log 3/\log 1. 5}}nNoYesChậm hơn hầu hết các thuật toán sắp xếp (ngay cả những thuật toán ngây thơ) với độ phức tạp về thời gian là O(nlog 3 / log 1. 5 ) = O(n2. 7095. ) Có thể được làm ổn định và cũng là một mạng phân loại. Slowsortnlogn{\displaystyle n^{\log n}}nlogn{\displaystyle n^{\log n}}nlogn{ . nNoYesA multiply and surrender algorithm, antonymous with divide-and-conquer algorithm.Các nhà khoa học máy tính lý thuyết đã trình bày chi tiết các thuật toán sắp xếp khác cung cấp độ phức tạp thời gian tốt hơn O(n log n) giả định các ràng buộc bổ sung, bao gồm
Các thuật toán sắp xếp phổ biến[sửa | sửa mã nguồn]Mặc dù có một số lượng lớn các thuật toán sắp xếp, nhưng trong triển khai thực tế, một số thuật toán chiếm ưu thế. Sắp xếp chèn được sử dụng rộng rãi cho các tập dữ liệu nhỏ, trong khi đối với các tập dữ liệu lớn, sắp xếp tiệm cận hiệu quả được sử dụng, chủ yếu là sắp xếp heapsort, sắp xếp hợp nhất hoặc sắp xếp nhanh. Các triển khai hiệu quả thường sử dụng thuật toán kết hợp, kết hợp thuật toán tiệm cận hiệu quả cho sắp xếp tổng thể với sắp xếp chèn cho các danh sách nhỏ ở cuối đệ quy. Việc triển khai được điều chỉnh cao sử dụng các biến thể phức tạp hơn, chẳng hạn như Timsort (sắp xếp hợp nhất, sắp xếp chèn và logic bổ sung), được sử dụng trong Android, Java và Python và introsort (sắp xếp nhanh và sắp xếp theo khối), được sử dụng (ở dạng biến thể) trong một số sắp xếp C++ . BỌC LƯỚI Đối với dữ liệu hạn chế hơn, chẳng hạn như các số trong một khoảng thời gian cố định, chẳng hạn như sắp xếp đếm hoặc sắp xếp cơ số được sử dụng rộng rãi. Sắp xếp bong bóng và các biến thể hiếm khi được sử dụng trong thực tế, nhưng thường thấy trong giảng dạy và thảo luận lý thuyết Khi sắp xếp vật lý các đối tượng (chẳng hạn như sắp xếp theo thứ tự bảng chữ cái, bài kiểm tra hoặc sách), mọi người thường sử dụng sắp xếp chèn cho các tập hợp nhỏ theo trực giác. Đối với các tập hợp lớn hơn, mọi người thường phân nhóm trước, chẳng hạn như bằng chữ cái đầu tiên và việc phân nhóm nhiều lần cho phép sắp xếp thực tế các tập hợp rất lớn. Thường thì không gian tương đối rẻ, chẳng hạn như bằng cách trải các đồ vật trên sàn nhà hoặc trên một khu vực rộng lớn, nhưng các thao tác rất tốn kém, đặc biệt là di chuyển một đồ vật ở một khoảng cách lớn – vị trí tham chiếu là quan trọng. Hợp nhất các loại cũng rất thiết thực đối với các đối tượng vật lý, đặc biệt là khi có thể sử dụng hai tay, một tay cho mỗi danh sách để hợp nhất, trong khi các thuật toán khác, chẳng hạn như heapsort hoặc quicksort, không phù hợp cho việc sử dụng của con người. Các thuật toán khác, chẳng hạn như sắp xếp thư viện, một biến thể của sắp xếp chèn để lại khoảng trắng, cũng rất thiết thực cho việc sử dụng vật lý Sắp xếp đơn giản[sửa]Hai trong số các cách sắp xếp đơn giản nhất là sắp xếp chèn và sắp xếp lựa chọn, cả hai đều hiệu quả trên dữ liệu nhỏ, do chi phí thấp, nhưng không hiệu quả trên dữ liệu lớn. Sắp xếp chèn thường nhanh hơn so với sắp xếp lựa chọn trong thực tế, do ít so sánh hơn và hiệu suất tốt trên dữ liệu được sắp xếp gần hết, do đó được ưa thích hơn trong thực tế, nhưng sắp xếp lựa chọn sử dụng ít thao tác ghi hơn và do đó được sử dụng khi hiệu suất ghi là một yếu tố hạn chế Sắp xếp chèn[sửa]Sắp xếp chèn là một thuật toán sắp xếp đơn giản tương đối hiệu quả đối với các danh sách nhỏ và hầu hết các danh sách được sắp xếp và thường được sử dụng như một phần của các thuật toán phức tạp hơn. Nó hoạt động bằng cách lấy từng phần tử từ danh sách và chèn chúng vào đúng vị trí của chúng vào danh sách được sắp xếp mới tương tự như cách chúng ta bỏ tiền vào ví của mình. Trong mảng, danh sách mới và các phần tử còn lại có thể chia sẻ không gian của mảng, nhưng việc chèn rất tốn kém, đòi hỏi phải thay đổi tất cả các phần tử sau từng phần tử một. Shellsort là một biến thể của sắp xếp chèn hiệu quả hơn cho các danh sách lớn hơn Sắp xếp lựa chọn[sửa]Sắp xếp lựa chọn là một sắp xếp so sánh tại chỗ. Nó có độ phức tạp O(n2), làm cho nó không hiệu quả trong các danh sách lớn và thường hoạt động kém hơn so với sắp xếp chèn tương tự. Sắp xếp lựa chọn được chú ý vì tính đơn giản của nó và cũng có lợi thế về hiệu suất so với các thuật toán phức tạp hơn trong một số tình huống nhất định Thuật toán tìm giá trị nhỏ nhất, hoán đổi nó với giá trị ở vị trí đầu tiên và lặp lại các bước này cho phần còn lại của danh sách. Nó không quá n lần hoán đổi và do đó rất hữu ích khi việc hoán đổi rất tốn kém Sắp xếp hiệu quả[sửa]Các thuật toán sắp xếp chung thực tế hầu như luôn dựa trên thuật toán có độ phức tạp thời gian trung bình (và nói chung là độ phức tạp trong trường hợp xấu nhất) O(n log n), trong đó phổ biến nhất là sắp xếp theo khối, sắp xếp hợp nhất và sắp xếp nhanh. Mỗi cái đều có ưu điểm và nhược điểm, trong đó quan trọng nhất là việc triển khai sắp xếp hợp nhất đơn giản sử dụng không gian bổ sung O(n) và việc triển khai quicksort đơn giản có độ phức tạp trong trường hợp xấu nhất là O(n2). Những vấn đề này có thể được giải quyết hoặc cải thiện với chi phí của một thuật toán phức tạp hơn Mặc dù các thuật toán này có hiệu quả tiệm cận trên dữ liệu ngẫu nhiên, nhưng để có hiệu quả thực tế trên dữ liệu trong thế giới thực, các sửa đổi khác nhau được sử dụng. Đầu tiên, chi phí hoạt động của các thuật toán này trở nên quan trọng đối với dữ liệu nhỏ hơn, do đó, thuật toán lai thường được sử dụng, thường chuyển sang sắp xếp chèn khi dữ liệu đủ nhỏ. Thứ hai, các thuật toán thường hoạt động kém trên dữ liệu đã được sắp xếp hoặc dữ liệu gần như được sắp xếp – đây là những điều phổ biến trong dữ liệu trong thế giới thực và có thể được sắp xếp trong thời gian O(n) bằng các thuật toán thích hợp. Cuối cùng, chúng cũng có thể không ổn định và sự ổn định thường là một thuộc tính mong muốn theo một cách nào đó. Do đó, các thuật toán phức tạp hơn thường được sử dụng, chẳng hạn như Timsort (dựa trên sắp xếp hợp nhất) hoặc introsort (dựa trên quicksort, quay trở lại heapsort) Hợp nhất sắp xếp[sửa]Hợp nhất sắp xếp tận dụng lợi thế của việc dễ dàng hợp nhất các danh sách đã được sắp xếp thành một danh sách được sắp xếp mới. Nó bắt đầu bằng cách so sánh mỗi hai phần tử (i. e. , 1 với 2, rồi 3 với 4. ) và hoán đổi chúng nếu cái đầu tiên đến sau cái thứ hai. Sau đó, nó hợp nhất từng danh sách kết quả gồm hai thành danh sách bốn, rồi hợp nhất các danh sách bốn đó, v.v.; . Trong số các thuật toán được mô tả ở đây, đây là thuật toán đầu tiên chia tỷ lệ tốt cho các danh sách rất lớn, bởi vì thời gian chạy trong trường hợp xấu nhất của nó là O(n log n). Nó cũng dễ dàng áp dụng cho danh sách, không chỉ mảng, vì nó chỉ yêu cầu truy cập tuần tự, không truy cập ngẫu nhiên. Tuy nhiên, nó có độ phức tạp không gian O(n) bổ sung và liên quan đến một số lượng lớn các bản sao trong các triển khai đơn giản Hợp nhất sắp xếp đã chứng kiến sự gia tăng tương đối gần đây về mức độ phổ biến đối với các triển khai thực tế, do việc sử dụng nó trong thuật toán phức tạp Timsort, được sử dụng cho thói quen sắp xếp tiêu chuẩn trong các ngôn ngữ lập trình Python và Java (kể từ JDK7). Hợp nhất sắp xếp chính nó là thói quen tiêu chuẩn trong Perl, trong số những thứ khác, và đã được sử dụng trong Java ít nhất là từ năm 2000 trong Heapsort [ chỉnh sửa ]Heapsort là phiên bản sắp xếp lựa chọn hiệu quả hơn nhiều. Nó cũng hoạt động bằng cách xác định phần tử lớn nhất (hoặc nhỏ nhất) của danh sách, đặt phần tử đó ở cuối (hoặc đầu) danh sách, sau đó tiếp tục với phần còn lại của danh sách, nhưng hoàn thành nhiệm vụ này một cách hiệu quả bằng cách sử dụng cấu trúc dữ liệu được gọi là . Khi danh sách dữ liệu đã được tạo thành một đống, nút gốc được đảm bảo là phần tử lớn nhất (hoặc nhỏ nhất). Khi nó được loại bỏ và đặt ở cuối danh sách, heap được sắp xếp lại để phần tử lớn nhất còn lại di chuyển đến thư mục gốc. Sử dụng heap, việc tìm phần tử lớn nhất tiếp theo mất thời gian O(log n), thay vì O(n) để quét tuyến tính như trong sắp xếp lựa chọn đơn giản. Điều này cho phép Heapsort chạy trong thời gian O(n log n) và đây cũng là trường hợp phức tạp nhất Sắp xếp nhanh[sửa]Quicksort là thuật toán chia để trị dựa trên phép toán phân vùng. để phân vùng một mảng, một phần tử được gọi là trục được chọn. Tất cả các phần tử nhỏ hơn trục được di chuyển trước nó và tất cả các phần tử lớn hơn được di chuyển sau nó. Điều này có thể được thực hiện hiệu quả trong thời gian tuyến tính và tại chỗ. Các danh sách con nhỏ hơn và lớn hơn sau đó được sắp xếp đệ quy. Điều này mang lại độ phức tạp thời gian trung bình là O(n log n), với chi phí thấp và do đó, đây là một thuật toán phổ biến. Việc triển khai hiệu quả sắp xếp nhanh (với phân vùng tại chỗ) thường là các sắp xếp không ổn định và hơi phức tạp, nhưng là một trong những thuật toán sắp xếp nhanh nhất trong thực tế. Cùng với việc sử dụng không gian O(log n) khiêm tốn, quicksort là một trong những thuật toán sắp xếp phổ biến nhất và có sẵn trong nhiều thư viện lập trình tiêu chuẩn Lưu ý quan trọng về quicksort là hiệu suất trong trường hợp xấu nhất của nó là O(n2); . Do đó, vấn đề phức tạp nhất trong sắp xếp nhanh là chọn một yếu tố trục tốt, vì các lựa chọn trục liên tục kém có thể dẫn đến hiệu suất O(n2) chậm hơn đáng kể, nhưng lựa chọn tốt các trục sẽ mang lại hiệu suất O(n log n), tối ưu tiệm cận. Ví dụ: nếu ở mỗi bước, trung vị được chọn làm trục thì thuật toán sẽ hoạt động trong O(n log n). Tuy nhiên, việc tìm trung vị, chẳng hạn như bằng thuật toán chọn trung vị của trung vị là thao tác O(n) trên các danh sách chưa được sắp xếp và do đó xác định chính xác chi phí đáng kể với việc sắp xếp. Trong thực tế, việc chọn một trục ngẫu nhiên gần như chắc chắn mang lại hiệu suất O(n log n) Nếu việc đảm bảo hiệu suất O(n log n) là quan trọng, thì có một sửa đổi đơn giản để đạt được điều đó. Ý tưởng, do Musser, là đặt giới hạn về độ sâu tối đa của đệ quy. Nếu vượt quá giới hạn đó, thì việc sắp xếp được tiếp tục bằng thuật toán heapsort. Musser đề xuất rằng giới hạn phải là 1+2⌊log2(n)⌋{\displaystyle 1+2\lfloor \log _{2}(n)\rfloor }, gần đúng . Sắp xếp vỏ [ chỉnh sửa ]Shellsort, khác với sắp xếp bong bóng ở chỗ nó di chuyển các phần tử đến nhiều vị trí hoán đổi Shellsort được phát minh bởi Donald Shell vào năm 1959. Nó cải thiện khi sắp xếp chèn bằng cách di chuyển các phần tử ra khỏi thứ tự nhiều hơn một vị trí cùng một lúc. Khái niệm đằng sau Shellsort là sắp xếp chèn thực hiện trong thời gian O(kn){\displaystyle O(kn)}, trong đó k là khoảng cách lớn nhất giữa hai phần tử không đúng vị trí. Điều này có nghĩa là nhìn chung, chúng hoạt động trong O(n2), nhưng đối với dữ liệu hầu hết được sắp xếp, chỉ có một vài phần tử không đúng chỗ, chúng hoạt động nhanh hơn. Vì vậy, bằng cách sắp xếp các phần tử đầu tiên ở xa và dần dần thu hẹp khoảng cách giữa các phần tử cần sắp xếp, cách sắp xếp cuối cùng sẽ tính toán nhanh hơn nhiều. Một triển khai có thể được mô tả là sắp xếp chuỗi dữ liệu trong một mảng hai chiều và sau đó sắp xếp các cột của mảng bằng sắp xếp chèn. Độ phức tạp thời gian trong trường hợp xấu nhất của Shellsort là một vấn đề mở và phụ thuộc vào chuỗi khoảng trống được sử dụng, với độ phức tạp đã biết nằm trong khoảng từ O(n2) đến O(n4/3) và Θ(n log2 n). Điều này, kết hợp với thực tế là Shellsort tại chỗ, chỉ cần một lượng mã tương đối nhỏ và không yêu cầu sử dụng ngăn xếp cuộc gọi, khiến nó trở nên hữu ích trong các tình huống mà bộ nhớ ở mức cao, chẳng hạn như trong các hệ thống nhúng Sắp xếp bong bóng và các biến thể[sửa | sửa mã nguồn]Sắp xếp bong bóng và các biến thể như Sắp xếp lược và sắp xếp cocktail là các thuật toán sắp xếp đơn giản, kém hiệu quả. Chúng thường được thấy trong các văn bản giới thiệu do dễ phân tích, nhưng chúng hiếm khi được sử dụng trong thực tế Sắp xếp bong bóng[sửa]Sắp xếp bong bóng, thuật toán sắp xếp liên tục duyệt qua một danh sách, hoán đổi các mục cho đến khi chúng xuất hiện theo đúng thứ tự Sắp xếp bong bóng là một thuật toán sắp xếp đơn giản. Thuật toán bắt đầu từ đầu tập dữ liệu. Nó so sánh hai phần tử đầu tiên và nếu phần tử đầu tiên lớn hơn phần tử thứ hai, nó sẽ hoán đổi chúng. Nó tiếp tục làm điều này cho từng cặp phần tử liền kề cho đến hết tập dữ liệu. Sau đó, nó bắt đầu lại với hai phần tử đầu tiên, lặp lại cho đến khi không có sự hoán đổi nào xảy ra ở lượt cuối cùng. Thời gian trung bình và hiệu suất trong trường hợp xấu nhất của thuật toán này là O(n2) nên ít được sử dụng để sắp xếp các tập dữ liệu lớn, không có thứ tự. Sắp xếp bong bóng có thể được sử dụng để sắp xếp một số lượng nhỏ các mục (trong đó tính kém hiệu quả của phương pháp tiệm cận không phải là một hình phạt cao). Sắp xếp bong bóng cũng có thể được sử dụng hiệu quả trên một danh sách có độ dài bất kỳ gần được sắp xếp (nghĩa là các phần tử không bị lạc chỗ đáng kể). Ví dụ: nếu bất kỳ số lượng phần tử nào không đúng vị trí chỉ bởi một vị trí (e. g. 0123546789 và 1032547698), trao đổi của sắp xếp bong bóng sẽ lấy chúng theo thứ tự ở lượt đầu tiên, lượt thứ hai sẽ tìm tất cả các phần tử theo thứ tự, do đó, việc sắp xếp sẽ chỉ mất 2n thời gian Sắp xếp lược [ chỉnh sửa ]Sắp xếp lược là một thuật toán sắp xếp tương đối đơn giản dựa trên sắp xếp bong bóng và được thiết kế ban đầu bởi Włodzimierz Dobosiewicz vào năm 1980. Sau đó nó được tái khám phá và phổ biến bởi Stephen Lacey và Richard Box với một bài báo trên Tạp chí Byte xuất bản vào tháng 4 năm 1991. Ý tưởng cơ bản là loại bỏ các giá trị rùa hoặc các giá trị nhỏ ở gần cuối danh sách, vì trong sắp xếp bong bóng, những giá trị này làm chậm quá trình sắp xếp rất nhiều. (Rabbit, các giá trị lớn ở đầu danh sách, không gây ra vấn đề gì trong sắp xếp bong bóng) Nó thực hiện điều này bằng cách ban đầu hoán đổi các phần tử có khoảng cách nhất định với nhau trong mảng, thay vì chỉ hoán đổi các phần tử nếu chúng liền kề với nhau . Do đó, nếu Shellsort có thể được coi là một phiên bản tổng quát của sắp xếp chèn hoán đổi các phần tử cách nhau một khoảng nhất định, thì sắp xếp lược có thể được coi là cách tổng quát hóa tương tự được áp dụng cho sắp xếp bong bóng Sắp xếp trao đổi[sửa]Sắp xếp trao đổi đôi khi bị nhầm lẫn với sắp xếp bong bóng, mặc dù các thuật toán trên thực tế là khác biệt. Sắp xếp trao đổi hoạt động bằng cách so sánh phần tử đầu tiên với tất cả các phần tử phía trên nó, hoán đổi chỗ cần thiết, do đó đảm bảo rằng phần tử đầu tiên đúng với thứ tự sắp xếp cuối cùng; . Nó thiếu lợi thế mà sắp xếp bong bóng có trong việc phát hiện trong một lần nếu danh sách đã được sắp xếp, nhưng nó có thể nhanh hơn so với sắp xếp bong bóng theo một hệ số không đổi (ít hơn một lần vượt qua dữ liệu được sắp xếp; tổng số so sánh bằng một nửa) trong . Giống như bất kỳ cách sắp xếp O(n2) đơn giản nào, nó có thể khá nhanh đối với các tập dữ liệu rất nhỏ, mặc dù nói chung, sắp xếp chèn sẽ nhanh hơn Các loại phân phối [ chỉnh sửa ]Sắp xếp phân phối đề cập đến bất kỳ thuật toán sắp xếp nào trong đó dữ liệu được phân phối từ đầu vào của chúng đến nhiều cấu trúc trung gian, sau đó được thu thập và đặt trên đầu ra. Ví dụ: cả sắp xếp nhóm và flashsort đều là thuật toán sắp xếp dựa trên phân phối. Các thuật toán sắp xếp phân phối có thể được sử dụng trên một bộ xử lý hoặc chúng có thể là một thuật toán phân tán, trong đó các tập hợp con riêng lẻ được sắp xếp riêng trên các bộ xử lý khác nhau, sau đó được kết hợp. Điều này cho phép sắp xếp bên ngoài dữ liệu quá lớn để vừa với bộ nhớ của một máy tính Sắp xếp đếm[sửa]Sắp xếp đếm được áp dụng khi mỗi đầu vào được biết là thuộc về một tập hợp cụ thể, S, các khả năng. Thuật toán chạy trong O(. S. + n) thời gian và O(. S. ) bộ nhớ trong đó n là độ dài của đầu vào. Nó hoạt động bằng cách tạo một mảng số nguyên có kích thước. S. và sử dụng ngăn thứ i để đếm số lần xuất hiện của phần tử thứ i của S trong đầu vào. Sau đó, mỗi đầu vào được tính bằng cách tăng giá trị của ngăn tương ứng. Sau đó, mảng đếm được lặp lại để sắp xếp tất cả các đầu vào theo thứ tự. Thuật toán sắp xếp này thường không được sử dụng vì S cần phải nhỏ hợp lý để thuật toán có hiệu quả, nhưng nó cực kỳ nhanh và thể hiện hành vi tiệm cận tuyệt vời khi n tăng. Nó cũng có thể được sửa đổi để cung cấp hành vi ổn định Sắp xếp thùng[sửa]Sắp xếp nhóm là một thuật toán sắp xếp chia để trị tổng quát hóa sắp xếp đếm bằng cách phân vùng một mảng thành một số nhóm hữu hạn. Mỗi nhóm sau đó được sắp xếp riêng lẻ, sử dụng thuật toán sắp xếp khác hoặc bằng cách áp dụng đệ quy thuật toán sắp xếp nhóm Sắp xếp nhóm hoạt động tốt nhất khi các thành phần của tập dữ liệu được phân bổ đồng đều trên tất cả các nhóm Sắp xếp cơ số[sửa]Radix sort là một thuật toán sắp xếp các số bằng cách xử lý các chữ số riêng lẻ. n số gồm k chữ số, mỗi số được sắp xếp trong thời gian O(n · k). Sắp xếp cơ số có thể xử lý các chữ số của mỗi số bắt đầu từ chữ số có nghĩa nhỏ nhất (LSD) hoặc bắt đầu từ chữ số có nghĩa nhất (MSD). Trước tiên, thuật toán LSD sắp xếp danh sách theo chữ số ít quan trọng nhất trong khi vẫn giữ nguyên thứ tự tương đối của chúng bằng cách sử dụng sắp xếp ổn định. Sau đó, nó sắp xếp chúng theo chữ số tiếp theo, v.v. từ ít quan trọng nhất đến quan trọng nhất, kết thúc bằng một danh sách được sắp xếp. Mặc dù sắp xếp cơ số LSD yêu cầu sử dụng sắp xếp ổn định, nhưng thuật toán sắp xếp cơ số MSD thì không (trừ khi muốn sắp xếp ổn định). Sắp xếp cơ số MSD tại chỗ không ổn định. Thông thường, thuật toán sắp xếp đếm được sử dụng nội bộ bởi sắp xếp cơ số. Phương pháp sắp xếp kết hợp, chẳng hạn như sử dụng sắp xếp chèn cho các thùng nhỏ, cải thiện đáng kể hiệu suất của sắp xếp cơ số Mô hình sử dụng bộ nhớ và sắp xếp chỉ mục[sửa | sửa mã nguồn]Khi kích thước của mảng được sắp xếp tiếp cận hoặc vượt quá bộ nhớ chính khả dụng, do đó đĩa (chậm hơn nhiều) hoặc không gian hoán đổi phải được sử dụng, mẫu sử dụng bộ nhớ của thuật toán sắp xếp trở nên quan trọng và thuật toán có thể khá . Trong trường hợp này, tổng số lần so sánh trở nên (tương đối) ít quan trọng hơn và số lần các phần bộ nhớ phải được sao chép hoặc hoán đổi sang và từ đĩa có thể chi phối các đặc tính hiệu suất của thuật toán. Do đó, số lần vượt qua và nội địa hóa của phép so sánh có thể quan trọng hơn số lần so sánh thô, vì việc so sánh các phần tử lân cận với nhau xảy ra ở tốc độ bus hệ thống (hoặc, với bộ nhớ đệm, thậm chí ở tốc độ CPU), so sánh Ví dụ: thuật toán sắp xếp nhanh đệ quy phổ biến cung cấp hiệu suất khá hợp lý với RAM đầy đủ, nhưng do cách đệ quy mà nó sao chép các phần của mảng nên nó trở nên kém thực tế hơn nhiều khi mảng không vừa với RAM, vì nó có thể gây ra một số lỗi. . Trong trường hợp đó, một thuật toán khác có thể thích hợp hơn ngay cả khi nó yêu cầu nhiều phép so sánh hơn Một cách để giải quyết vấn đề này, hoạt động tốt khi các bản ghi phức tạp (chẳng hạn như trong cơ sở dữ liệu quan hệ) đang được sắp xếp theo một trường khóa tương đối nhỏ, là tạo một chỉ mục vào mảng rồi sắp xếp chỉ mục, thay vì toàn bộ. . (Sau đó, một phiên bản được sắp xếp của toàn bộ mảng có thể được tạo bằng một lượt, đọc từ chỉ mục, nhưng thường thì điều đó là không cần thiết, vì chỉ mục được sắp xếp là đủ. ) Vì chỉ mục nhỏ hơn nhiều so với toàn bộ mảng, nên nó có thể dễ dàng nằm gọn trong bộ nhớ mà toàn bộ mảng sẽ không, loại bỏ hiệu quả vấn đề tráo đổi ổ đĩa. Quy trình này đôi khi được gọi là "sắp xếp thẻ" Một kỹ thuật khác để khắc phục vấn đề kích thước bộ nhớ là sử dụng sắp xếp bên ngoài, ví dụ: một trong những cách là kết hợp hai thuật toán theo cách tận dụng sức mạnh của từng thuật toán để cải thiện hiệu suất tổng thể. Chẳng hạn, mảng có thể được chia thành các phần có kích thước phù hợp với RAM, nội dung của từng phần được sắp xếp bằng thuật toán hiệu quả (chẳng hạn như quicksort) và kết quả được hợp nhất bằng cách hợp nhất k-way tương tự như đã sử dụng trong . Điều này nhanh hơn so với thực hiện sắp xếp hợp nhất hoặc sắp xếp nhanh trên toàn bộ danh sách Cũng có thể kết hợp các kỹ thuật. Để sắp xếp các tập hợp dữ liệu rất lớn vượt quá nhiều bộ nhớ hệ thống, thậm chí chỉ mục có thể cần được sắp xếp bằng thuật toán hoặc tổ hợp các thuật toán được thiết kế để hoạt động hợp lý với bộ nhớ ảo, tôi. e. , để giảm số lượng trao đổi cần thiết Các vấn đề liên quan bao gồm (sắp xếp một chuỗi trong một lượng nhất định của thứ tự chính xác), sắp xếp một phần (chỉ sắp xếp k phần tử nhỏ nhất của danh sách hoặc tìm k phần tử nhỏ nhất nhưng không có thứ tự) và lựa chọn (tính toán phần tử nhỏ thứ k). Những điều này có thể được giải quyết không hiệu quả bằng cách sắp xếp tổng thể, nhưng tồn tại các thuật toán hiệu quả hơn, thường được suy ra bằng cách tổng quát hóa một thuật toán sắp xếp. Ví dụ đáng chú ý nhất là quickselect, liên quan đến quicksort. Ngược lại, một số thuật toán sắp xếp có thể được rút ra bằng cách áp dụng lặp lại thuật toán lựa chọn; Một dạng ngược lại của thuật toán sắp xếp là thuật toán xáo trộn. Đây là những khác biệt cơ bản vì chúng yêu cầu một nguồn số ngẫu nhiên. Xáo trộn cũng có thể được thực hiện bằng thuật toán sắp xếp, cụ thể là sắp xếp ngẫu nhiên. gán một số ngẫu nhiên cho từng phần tử của danh sách và sau đó sắp xếp dựa trên các số ngẫu nhiên. Tuy nhiên, điều này thường không được thực hiện trong thực tế và có một thuật toán xáo trộn đơn giản và hiệu quả nổi tiếng. xáo trộn Fisher–Yates Thuật toán sắp xếp không hiệu quả để tìm thứ tự trong nhiều tình huống. Thông thường, khi các phần tử không có chức năng so sánh đáng tin cậy (các tùy chọn có nguồn gốc từ cộng đồng như hệ thống bỏ phiếu), việc so sánh rất tốn kém (thể thao) hoặc khi không thể so sánh theo cặp tất cả các phần tử cho tất cả các tiêu chí (công cụ tìm kiếm). Trong những trường hợp này, vấn đề thường được gọi là xếp hạng và mục tiêu là tìm ra kết quả "tốt nhất" cho một số tiêu chí theo xác suất được suy ra từ so sánh hoặc xếp hạng. Một ví dụ phổ biến là trong cờ vua, nơi người chơi được xếp hạng theo hệ thống xếp hạng Elo và thứ hạng được xác định bởi hệ thống giải đấu thay vì thuật toán sắp xếp |
