1.bubbleSort.md

Bubble Sort

Bubble Sort is also a simple and intuitive sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing two elements at a time, and swapping them if they are in the wrong order. The work of visiting the sequence is repeated until no more exchanges are needed, that is, the sequence has been sorted. The name of this algorithm comes from the fact that the smaller elements are slowly "floated" to the top of the sequence by swapping.

As one of the simplest sorting algorithms, bubble sort gives me the same feeling that Abandon appears in a word book, every time it is first on the first page, so it is the most familiar. There is also an optimization algorithm for bubble sort, which is to set up a flag. When the elements are not exchanged during a sequence traversal, it is proved that the sequence is already in order. But this improvement doesn't do much to improve performance.

1. Algorithm steps

1. Compare adjacent elements. If the first is bigger than the second, swap the two of them.

2. Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. After this step, the last element will be the largest number.

3. Repeat the above steps for all elements except the last one.

4. Continue to repeat the above steps for fewer and fewer elements each time, until there are no pairs of numbers to compare.

2. Animated demo

3. When is the fastest

When the input data is already in positive order (it is already in positive order, what is the use of bubble sort I want you to do).

4. When is the slowest

When the input data is in reverse order (write a for loop to output data in reverse order, why use your bubble sort, am I free).

5. JavaScript code implementation

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) { // pairwise comparison of adjacent elements
                var temp = arr[j+1]; // element swap
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

6. Python code implementation

def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

7. Go code implementation

func bubbleSort(arr []int) []int {
length := len(arr)
for i := 0; i < length; i++ {
for j := 0; j < length-1-i; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
return arr
}

8. Java code implementation

public class BubbleSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // Copy arr without changing the parameter content
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        for (int i = 1; i < arr.length; i++) {
            // Set a flag, if it is true, it means that there is no exchange in this loop, that is, the sequence to be sorted is already in order, and the sorting has been completed.
            boolean flag = true;

            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;

                    flag = false;
                }
            }

            if (flag) {
                break;
            }
        }
        return arr;
    }
}
```

## 9. PHP Code

```php
function bubbleSort($arr)
{
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j+1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $tmp;
            }
        }
    }
    return $arr;
}
```