1. Bubble Sort
Bubble sort is derived from observations in daily life, where small bubbles in soda often float to the top.
The sorting idea is to perform pairwise comparisons of adjacent elements, sinking the larger numbers and letting the smaller numbers rise. After one pass, the largest (or smallest) value will be arranged at one end. The entire process resembles bubbles rising, hence the name bubble sort.
Bubble sort is a basic, comparison-based sorting method.
For a sequence of length n (valid values stored at indices
1 ~ n):
① Scan the sequence n – 1 times
② During the i-th (1 ≤ i ≤ n – 1) scan, compare the two adjacent elements, i.e., compare a[j] with a[j + 1], where 1 ≤ j ≤ n – i
③ Each timewhen comparing, if a[j] > a[j + 1], swap them; otherwise, do nothing.
④ If during a scanno elements were swapped, it indicates that the sequence is already sorted, and subsequent operations can stop.
2. Selection Sort
In the unsorted interval, find thesmallest element and swap it with the first element of that interval. For a sequence of length n, it requires n-1 timesto select the minimum value and swap it with the correct position element. It requiresextra space to store the minimum element found each time.
Each round only performs one swap, reducing unnecessary element movements. In the i-th round, the i-th smallest number is selected.
For a sequence of length n (valid values stored at indices 1 ~ n):
① Scan the sequence n-1 times
② During the i-th (1 ≤ i ≤ n-1) scan, find the smallest element a[pos] among a[i], a[i+1], …, a[n]
③ Swap a[i] with a[pos]
3. Insertion Sort
Analogous to cutting in line, where others are already lined up by height, the new person must find the right position to cut in based on their height.
This sorting method is called insertion sort.
The basic idea of insertion sort: each time, insert the next element into the correct position in the sorted sequence.
For a sequence of length n (valid values stored at indices 1 ~ n):
① Scan the sequence n-1 times
② In the i-th round, the (i + 1)-th element needs to be inserted into the sorted sequence formed by the first i elements.
a. Store the (i + 1)-th element in a temporary variable t
b. Compare the j-th element with t (j decreases from i to 1, in reverse)
c. If the j-th element’s value > t, move that element one position back
d. Otherwise, find the insertion position as j+1 and place the value of t at position j+1
4. Quick Sort
It usesdivide and conquer strategy to split a large sequence into two smaller sequences, and then recursively sort these two smaller sequences.
The core is to select apivot value, and through one pass of sorting, partition the sequence into two independent parts, where the left sub-sequence contains all numbers ≤ pivot, and the right part contains all numbers ≥ pivot, with no guarantee of order within the sub-sequences.
Continue sorting the two sub-sequences until all are sorted.
One pass of sorting requires selecting a pivot and partitioning.
For a sequence of length n (valid values stored at indices 1 ~ n):
① Select a pivot, choosing an element from the array to be the pivot.
② Complete one pass of quick sort, using two pointers, one scanning from the left end to the right, and the other from the right end to the left:
a. The left pointer left looks for the first element ≥ pivot, while the right pointer right looks for the first element ≤ pivot.
b. After finding, swap the values of these two elements. Repeat the process until left > right.
③ Recursively sort the left sub-array (indices start to right) and the right sub-array (indices left to end).
5. Counting Sort
Similar toheight sorting, where people of height 150cm stand in one line, 151cm in another line, … up to 189cm, and 190cm in another line. Then combine them from front to back to form a single line. This is counting sort.
Count the occurrences of the same element, and then sort based on these counts..
For a sequence of length n (valid values stored at indices 1 ~ n):
① Find the maximum value W in the array a to be sorted, and determine the length of the count array c, which should be W + 1.
② Initialize the count array c, setting the occurrence count of each element to 0.
③ Traverse the array a to be sorted, counting the occurrences of each element value i and storing it in count array c[j].
④ Traverse the count array c, finding elements with values greater than 0, and output the corresponding index based on the count.
Note: The index of the count array corresponds to the number to be sorted, and the value of the count array corresponds to the number of occurrences of that number.
