[Bubble sort] sorts by continuously comparing and swapping adjacent elements. This process is similar to bubbles rising from the bottom to the top.
The bubble process can be simulated using element swapping operations: starting from the leftmost end of the array and traversing to the right, compare adjacent elements one by one. If the "left element > right element", swap them. After the traversal is completed, the largest element will be moved to the rightmost end of the array.
Bubble sort algorithm process:
- First, perform "bubble" on n elements, swap the largest element of the array to the correct position.
- Next, perform "bubble" on the remaining n-1 elements, swap the second largest element to the correct position.
- Repeat this process, after n-1 rounds of "bubble", the top n-1 largest elements will be swapped to the correct positions.
- The remaining element is definitely the smallest element, so no sorting is needed, and the array is sorted.
/* Bubble Sort */
void BubbleSort(int[] nums) {
// Outer loop: the unsorted interval is [0, i]
for (int i = nums.Length - 1; i > 0; i--) {
// Inner loop: swap the largest element in the unsorted interval [0, i] to the rightmost end of the interval
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
(nums[j + 1], nums[j]) = (nums[j], nums[j + 1]);
}
}
}
}
Efficiency optimization: If no swap operation is performed in a round of "bubble", it means that the array has been sorted, and the result can be returned directly. Therefore, a flag flag can be added to monitor this situation, and return immediately once it occurs.
/* Bubble Sort (Flag Optimization) */
void BubbleSortWithFlag(int[] nums) {
// Outer loop: the unsorted interval is [0, i]
for (int i = nums.Length - 1; i > 0; i--) {
bool flag = false; // Initialize the flag
// Inner loop: swap the largest element in the unsorted interval [0, i] to the rightmost end of the interval
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// Swap nums[j] and nums[j + 1]
(nums[j + 1], nums[j]) = (nums[j], nums[j + 1]);
flag = true; // Record the swapped elements
}
}
if (!flag) break; // No elements were swapped in this round of bubble, directly break out
}
}