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 .