1. stability ( important )
Two equal data , If after sorting , The sorting algorithm can ensure that its relative position does not change , Then we call the algorithm a sort algorithm with stability .
for example : Backstage of a treasure mall , You need to sort by order amount , The original order is arranged in chronological order , The original time sequence after sorting is required to remain unchanged , Stability .
In this case, we need to use a stable sorting algorithm to sort the order amount in ascending order , Ensure that the order of other information does not change .
2. classification :
Inner sorting : Sorting by putting all data to be sorted into memory at one time , Sorting based on comparison between elements . Including seven sorts
Outer sort ： You need to exchange data between internal and external memory for many times before proceeding . Include bucket sorting , Cardinality sort , Count sort , Very high requirements for data sets , Can only be used in specific occasions
be careful : Write sort code , It is important to note how variables are defined , And the definitions of unsorted intervals and sorted intervals .
1. Select sort :
Select a maximum or minimum value from the unordered range each time , Stored in the first or last position of the unordered section ( Elements at this location and order ), Until all the data is sorted .
Code examples are as follows :
About selecting sorting , We can further optimize the sorting for two-way selection :
2. Insert sort :
Divide the set into two intervals : A sorted interval , An interval to be sorted , Then select an element from the range to be sorted each time and insert it into the sorted range , Until the entire array is ordered
The biggest difference between insert sort and select sort is that : When inserting and sorting the currently traversed elements > When precursor element , At this time, the inner layer cycle can be ended in advance , In extreme scenarios , When a set is a completely ordered set , Insert the inner loop of sorting without going once , The time complexity becomes O(n), Therefore, insertion sort is often used as one of the optimization means of high-order sorting algorithm .
3. Shell Sort : Zoom out incremental sort
Select an integer first (gap,gap Generally, half of the array length or 1/3), First sort the array to be sorted by gap grouping , Use insert sort between groups , After sorting , Zaijiang gap/2 perhaps /3. Repeat the above process , until gap=1, When gap=1 Hour , The entire array has been adjusted to be almost orderly , This is the best time to use insert sorting , Finally, you can use one insertion sort on the entire array .
4. Merge sort :
Continuously split the original array , Until each subarray has only one element , End of phase I , Return and act 1 End of this phase
and : Combine two adjacent arrays into an ordered array , Until the entire array is ordered , Merge sort is a stable nlogn Sorting algorithm
Optimization of merge sort :
a. When the left and right subintervals have completed the subfunction , The left and right sections are in order , If at this time arr[mid]<arr[mid]+1
arr[mid] Is already the maximum value of the left interval ,arr[mid] + 1 It is already the minimum value of the right range , This means that the whole interval is in order , No need to execute merge process .
b. Between cells , We can use insert sort directly to optimize , No need to split the element all the way to 1 position ,r-l<=15, Using insert sort performance is good , Can reduce the number of recursion of merging
Application of merging : Sorting processing of massive data
Suppose the data to be sorted now is 100G, But the memory is only 1GB, How to sort this 100GB Data ?
1. Take this 100GB Data of are stored in 200 Of files ( Stored on hard disk ), Every file is 0.5G
2. Separate this 200 Files are read into memory in turn , Sort them using any of the internal sorting algorithms , You can get 200 Ordered files
3. For this 200 Files merge Operation is OK .
How to operate ?
this 200 Small files have been ordered , Take it out every time 200 The first element of a file is placed in memory , Internal sort this 200 The minimum value of the small value is written back to the first line of the large file , Repeat the above process , Until this 200 All contents of files can be written to large files
5. Quick sort :
First, introduce the zoning idea of fast platoon :
Reference value selection for fast exhaust , At the beginning, we choose the first element as the partition point by default , If in extreme cases , An array is a completely ordered array , At this time, the left and right partitions are seriously unbalanced , Binary tree degenerates into single branch tree , The tree structure degenerates into a linked list , The process of recursion is actually traversing an array ,O(N^2) Algorithm for , So when we select the reference value , Use the method of random selection or how many numbers to go to the center , Generally, three numbers are taken from the middle , On a set with a large number of repeating elements , Fast platoon will still degenerate , At this time, we use two-way fast platoon or three-way fast platoon .
Technology